What is the Significance of Aleph Zero in Mathematics?

[HallsofIvy]

Since ${\aleph_0}^{\aleph_0}=\mathfrak{c}$

Where did you get that? I was under the impression ${2}^{\aleph_0}= \mathfrak{c}$ and that the assertion that this was equal to ${\aleph_1}$ was the "continuum hypothesis" but I will say again that I have never seen ${\aleph_0}^{\aleph_0}$ before

 

[master_coda]

Originally posted by HallsofIvy
Where did you get that? I was under the impression ${2}^{\aleph_0}= \mathfrak{c}$ and that the assertion that this was equal to ${\aleph_1}$ was the "continuum hypothesis" but I will say again that I have never seen ${\aleph_0}^{\aleph_0}$ before

Well, take two sets A and B with $\lvert A\rvert=\lvert B\rvert=\aleph_0$. Then the cardinality of the set of all functions from A to B is ${\lvert B\rvert}^{\lvert A\rvert}={\aleph_0}^{\aleph_0}$.

 

[Hurkyl]

Here's a bijection between $2^{\mathbb{Z}^+}$ and $\mathbb{N}^{\mathbb{Z}^+}$:

Let $a$ be a one-based infinite sequence of 0's and 1's (i.e. an element of $2^{\mathbb{Z}^+}$. We can construct a unique one-based infinite sequence of natural numbers $b$ (an element of $(\mathbb{N})^{\mathbb{Z}^+}$ as follows:

Let $b_n$ be the location of the $n$-th one in $a$. If $a$ does not have $n$ ones, then $b_n$ is zero.

This operation is clearly invertible, thus it is a bijection between the two sets.

Thus, $2^{\aleph_0} = {\aleph_0}^{\aleph_0}$.

 

[suyver]

This is a facinating thread, though very hard for me to follow!

I understand that $\aleph_0$ refers to the set of all countable numbers, and it can typically be assumed (even though it can't be proven) that $\aleph_1$ refers to the set of all uncountable numbers. Now, I also learned that there is a whole series of these aleph's: $\aleph_i >\aleph_j$ if $i>j$.

One question that I had, when I was reading this is the following: What do these larger alephs refer to? For example, is $\aleph_2$ just the collection of numbers in the complex plane? That would seem somewhat reasonable to me, as I don't think there is a 1-1 correspondence between R and C and the latter is clearly greater.

Also, what would $\aleph_\infty$ refer to, and are such things ever used in mathematics?

Cool stuff!

 

[master_coda]

I should mention that C and R have the same cardinality. There is a bijection between the reals and the complex numbers.

Anyway, a lot of the numbers $\aleph_\alpha$ don't actually refer to a meaningful set. Almost all the sets you normally work with will have cardinality $\aleph_0$ or cardinality $2^{\aleph_0}$.

However, the formal definition of $\aleph_2$ is:

$$\aleph_2=\inf\lbrace\lambda\in\mathrm{ON}\colon\aleph_1<\lambda\rbrace$$

Where ON is the set of ordinal numbers.

 

[NateTG]

Originally posted by suyver
I understand that $\aleph_0$ refers to the set of all countable numbers, and it can typically be assumed (even though it can't be proven) that $\aleph_1$ refers to the set of all uncountable numbers. Now, I also learned that there is a whole series of these aleph's: $\aleph_i >\aleph_j$ if $i>j$.

There are results based on the continuum hypothesis. Since it is independent of the usual axioms of set theory, applying it is usually similar to applying the axiom of choice -- it's a good idea to explicitly point out what you're doing.

One question that I had, when I was reading this is the following: What do these larger alephs refer to? For example, is $\aleph_2$ just the collection of numbers in the complex plane? That would seem somewhat reasonable to me, as I don't think there is a 1-1 correspondence between R and C and the latter is clearly greater.

Well, because of the independence of the continuum w.r.t. the usual axioms, I'm not sure that I can give descriptions of the $$\aleph$$'s other than $$\aleph_0$$.

However, a familiar infinity that has cardinality $$\geq \aleph_2$$ is the set of all real functions.

 

[NateTG]

Nitpicking

Originally posted by Hurkyl
Here's a bijection between $2^{\mathbb{Z}^+}$ and $\mathbb{N}^{\mathbb{Z}^+}$:

Let $a$ be a one-based infinite sequence of 0's and 1's (i.e. an element of $2^{\mathbb{Z}^+}$. We can construct a unique one-based infinite sequence of natural numbers $b$ (an element of $(\mathbb{N})^{\mathbb{Z}^+}$ as follows:

Let $b_n$ be the location of the $n$-th one in $a$. If $a$ does not have $n$ ones, then $b_n$ is zero.

This operation is clearly invertible, thus it is a bijection between the two sets.

Thus, $2^{\aleph_0} = {\aleph_0}^{\aleph_0}$.

Acutally, that isn't quite correct. For example, the sequence "1,1,1,1,1,..." in $(\mathbb{N})^{\mathbb{Z}^+}$ does not have an inverse in your function. (In general, there is a problem if the n-th number in the sequence of integers is less than n, or if there are any non-zero digits following a zero.)

I think this approach works.

First I want to eliminate all of the $$a$$ that have finitely many zeros:

Let $$f:A->A'$$ be defined as follows:
If a sequence $$a$$ has a non-zero repeating tail, then $$f(a)$$ is the same squence with the next non-one repeating tail.

For example, ...100100100... is changed to ...101101101... , ...110110110... is changed to ...000100010001..., and ...010010010... is changed to ...011011011...

This is a bit ugly, but bijective.

I can now operate on $$f(a)=a'$$ so I can assume thatthere are infinitely many 0's in the sequence. Consider the squence as a stream of natural numbers encoded as follows:
0 -> 0
100 -> 1
101 -> 2
11000 -> 3
11001 -> 4
.
.
The general form is that d consecitive ones followed by a zero, and then d binary digits is converted to the number expressed in the binary digits + 2^d-1.

Clearly this is well-defined (since there are infinitely many 0's) , surjective and injective.

Composing the two gives a bijectiont that proves the equality.

 

[Hurkyl]

Just to be picky, I'd like to point out there is no "the set of ordinal numbers"; they form a proper class.


And good catch, Nate, I can't imagine how I could have possibly thought that was an invertible operation.

 

[master_coda]

Originally posted by Hurkyl
Just to be picky, I'd like to point out there is no "the set of ordinal numbers"; they form a proper class.

Yeah, I forgot about that. When I think of set theory I think of ZFC, and the definition of aleph-2 that I used is from NBG set theory.

I'm pretty sure there's an equivalent formulation using ZFC set theory, but I don't know what it is. I'm sure it's much uglier though.

 

[Hurkyl]

Do you know of a good online reference for NBG?

Anyways, while you can't form a set of all ordinal numbers, I think you can form sets consisting of initial segments of ordinal numbers, so you can inf over a sufficiently large initial segment.

Alternatively, "inf" can be rewritten as a logical formula, so (I think) there is no problem with the spirit of that definition.

 

[master_coda]

Originally posted by Hurkyl
Do you know of a good online reference for NBG?

No, I don't. All the sites I've seen that even mention it just give an unspecific overview. For a good reference you'll probably need to find a book.

 

[suyver]

Originally posted by NateTG
However, a familiar infinity that has cardinality $$\geq \aleph_2$$ is the set of all real functions.

Just to check that I understand: for many types of infinity (such as the set of all real functions that you described) it is only possible to give a lower bound for their $$\aleph_i$$ and not really give the exactly right one? It seems that only with additional assumptions one can do this. Is that roughly correct?

If that is correct, then how can one ever hope to say anything about $$\aleph_\infty$$ ?

 

[master_coda]

Often it isn't actually necessary to know the actual cardinality of a set, in terms of aleph numbers. A lot of times we usually just care if a set is countable or uncountable. If the uncountable set has cardinality $\aleph_1$ or $\aleph_{17}$ or $\aleph_{\aleph_0}$ isn't usually important.