h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

Cardinality of infinite sets is defined by its correlation with the cardinality of the natural numbers, so the two are sort of interlocked.

The cardinality of the set of the square roots of natural numbers is aleph-nought. Just because there exists one obvious correlation that isn't one-to-one doesn't mean that there isn't a less obvious correspondence that _is_ one-to-one. It won't look nice, but here is one possible example:

if n is even, let f(n) = sqrt(n/2)
if n is odd, let f(n) = -sqrt((n-1)/2)

It's clear that every natural number gets mapped to a square root of a natural number, but it's not immediately obvious that every square root of a natural number is mapped to from a natural number. But it _is_ true. For example, suppose I wanted to know what mapped to +sqrt(7)...well that would be f(14)=sqrt(14/2). In fact, for any +sqrt(x), f(2x)=+sqrt(2x/2)=+sqrt(x). So let's choose a negative example. How about -sqrt(5)...well that's just f(11)=-sqrt((11-1)/2). In fact, for any -sqrt(x), f(2x+1)=-sqrt((2x+1-1)/2)=-sqrt(x).

Do you get what I'm driving at? You need to do more than "double" the original set. Of course, I use the word "double" VERY loosely. You need to be a little more clever than that to increase the cardinality.

2*aleph-0 = aleph-0

It all works on this definition, which for two sets A and B, tells you when |A| <= |B| :

(|A| reads as 'cardinality of A', and <= means 'less than or equal')

|A| <= |B| if you can find some function from A to B which is injective.

What this means is that you need to find some rule which takes something in A to something in B, in such a way that you never get 2 things in A going to the same thing in B. So youre sortof making a copy of A fit into B.

Now, lets write aleph-0 as {0, 1, 2, 3, 4, ...}
and I suppose we can write 2*aleph-0 as {0a, 0b, 1a, 1b, 2a, 2b, 3a, 3b, ...}

aleph-0 <= 2*aleph-0 by having our function take each 'n' in aleph-0 to 'na' in 2*aleph-0. So 5747 -> 5747a
Its pretty obvious that its injective too.

Also, 2*aleph-0 <= aleph-0 by having the function take 'na' to '2*n' and 'nb' to '2*n+1'. So 23a -> 46 and 23b -> 47.
Again its injective. So we conclude that aleph-0 = 2*aleph-0.

Phew. Anyone notice the mistake in the original article:

"no one had ever decided what the square root
of a negative number was, they created a whole new set of numbers, all multiples of the square root of one."

It wants to be: "all multiples of the square root of /negative/ one."

An equivalent but slightly simpler definition of cardinality says merely that 2 objects have the same cardinality if and only if you can find a bijection between the two sets (the bijection and its inverse act as the two injections you've described).

By the way, I can't believe I let that typo slide and that no one noticed it until now. I'll see what I can do about fixing an already submitted article.

True, but generally easier to find 2 injections than one bijection.

The typo, sortof suggests that nobody is actually getting that far...
BTW, you might have some competition for getting to the interesting maths entries
(Though I can't think of anything right now on right level other than numbers...maybe symmetry?)

Hey, maybe that will spur me on to write more. Feel free to write about other subjects in math. There are so many that it'd be a shame if I was the only mathematical h2g2 reporter. Although that has a certain ring to it...H2G2's Math Researcher. Anyway, I'm more likely to discuss some of the more advanced and misunderstood fields _or_ some of the really basic substructures of math itself. Some things in math are so basic that no one thinks to talk about them. If I do another one it will probably be about predicate logic. And then I might do one about Arithmetic. If I write some advanced entries, I might discuss abstract algebra, number theory, analysis, or graph theory.

Feel free to write about symmetry; it wasn't something I was planning on doing, and I'd like to see it. Oh, just don't use the non-existent word "symmetrical". That irks me so much.

Hmm. Looking at the discussions following this entry on numbers, infinity seems like a good one to tackle. See if I get time this weekend.

> Here's where it gets REALLY weird. It's easy to show that the set of real numbers ( R ) can't have cardinality
> aleph-nought. However, it is IMPOSSIBLE to
> prove that R has cardinality aleph-one. It's also impossible to prove that R has cardinality BIGGER than aleph-one.

Really? I just checked my notes for set theory, which has |R| = 2^aleph-0

Writing an entry on infinity - seems you've covered large amounts of it here already, so perhaps its yours if you want to do it. Or maybe you're sick of writing about it?

If you can show me the proof (i.e. a bijection from the real numbers to the power set of the natural numbers), I'll believe you. Perhaps you're right, but I'd like to see the proof.

The way I have it in my notes is by two injections - one from 2^N -> R, one from R->P(Q)
2^N and P(Q) have the same cardinality, though you could construct injections direct from P(N) -> R and from R -> P(N) using the following injections, and the bijections which tell you that 2^N and P(Q) have the same cardinality.
You could then, if you want, apply the Schroder Bernstein thm to derive a bijection.

(I'll use 'N' for aleph-0 interchangeably, and Q is rationals)

Define g:R->P(Q) injective by

g(r) = {q in Q: q<r}
This is injective, because suppose r1 < r2. Then there exists q in Q: r1<q R. (2^N is the set of all functions from N to {0,1} )
by

H(f) = 0.[f(0)][f(1)][f(2)].... (decimal expansion)

This is injective since if a real number has no '9's in its decimal expansion, then the expansion uniquely determines the number. We could do this more precisely with Cauchy sequences or something, but this gives the idea.

You seem to like large numbers, mmaybe you can help. How long would it take to travel 108 million light years at a speed of 1 million miles per hour? I asked Jeeves, but he was no help. My calculator does not handle enough digits and I can't find a pencil.

2.29*10^18 seconds.

Thank you for your reply. Can you translate that into years?

That surely would be doing someone else's homework. Hmm, having checked your page, maybe its not. Ok, though its really not hard...

I get 7.26*10^10 years, I.e. 72.6 billion years.

well i have to admit the thing about the cardinality of R threw me for a loop as well--how is aleph one defined?? and is R the next-biggest set after aleph null?

as far as the square roots of the naturals, the cardinality is the same as that of N. so there are in essence the same number of naturals, integers, rationals, even numbers, multiples of 367, and digits of pi, even though we would intuitively think these were all different cardinalities.

but shouldn't there be two naturals for every even natural, and two integers for every natural number?? actually, NO.
this owes to the infiniteness of the sets. twice as much as infinity is still infinity; ten times as much as infinity is still infinity; 1 billion times as much as infinity is still (you got it) infinity. no matter what the physicists try to tell you, you shouldn't conceptualize infinity as something really, really big--the very idea that you can get your hands around the "bigness" places bounds on the situation--but rather as something which is continually *growing*, nonstop, forever.

the proof of my claim above owes to something called cantor's diagonalization process, which is a clever method of pairing the numbers from the set in question with the naturals. it turns out that you can make a real number, written as a sequence of digits, that is different from ANY sequence of integers i give you, so we know the cardinality of the reals can't be aleph null. it is helpful to think of the real line as "denser" than the rationals--between any two real numbers, no matter how close together, there are more numbers than there are integers.

what makes calculus so neat is that we see infinity being 'tamed'--we're adding together an infinite number of itty-bitty (read: finitely thin) rectangles, and they not only sum to a real number, but one that is easy to calculate with elegantly simple formulas. personally i have a bad habit of snickering at people who say calculus was 'invented' [rather than 'discovered'] but i suppose this is a matter of philosophy.

at any rate 2*aleph nought is, indeed, aleph nought.

i would love to hear about the proof of non-provability for the cardinality of R, that's something i haven't yet encountered.
if i'm wrong on anything above i apologize, i'm trying to study for an analysis test.

Alright. Your proof seems waterproof to me. I'll have to take this up with someone more knowledgeable than myself. Quite clearly |R|=|P(R)|. Maybe they're defining aleph-1 differently than I thought. I check back after I do some research.

Cantor's Diagonalization argument is a proof that the real numbers have a cardinality greater than that of the natural numbers. It's a pretty simple one to understand if you draw some nice pictures. It doesn't however determine the cardinality of the reals, merely that it's bigger than that of the natural numbers. I think the biggest confusion is saying things like 2 times infinity is infinity. What does one mean by "2 times infinity"? Not what we normally mean by multiplication because multiplication is not defined for infinity. It's defined for complex numbers, but that doesn't include any number called "infinity". So two times infinity isn't infinity. What one can say is that if you take a set with infinite cardinality, and you form another set which has two elements for every element in the original set, then you'll still be able to find a bijection between the two. I know that's a mouthful, but that's the closest you can come to multiplication when dealing with infinity.

Which is basically what you're saying. Infinity isn't something that's really, really, unbelievably big. That would imply that it's a number, that it has (as you said) a bound. And that's simply not what we mean when we discuss infinity.

|R| = |P(R)| ? Not sure you mean that. Theres a proof somewhere that no set can be as large as its power set. Quite neat and short IIRC.

What the heck is a bijection? I'm only doing A-level maths you know

BTW I've been reading the comments here, and I find them interesting (when I can understand them, that is). As I have said before, I find it impossible to believe that |R| can't be defined. I'd like to see that proof.

Thanks!

I posted a reply to this, but it didn't seem to go through. Indeed I did mean |R|=|P(N)|