What is the Significance of Aleph Zero in Mathematics?

[chroot]

All right math geeks, lay it on me. What the hell is aleph zero? Is this the right symbol for it: \aleph_0?

- Warren

 

[master_coda]

Basically, \aleph_0 is the "size" (or more rigorously, the cardinality) of the set of natural numbers.

If \aleph_0 just referred to the cardinality of the natural numbers, it wouldn't be very useful. But if we know that \mathbb{N} has cardinality \aleph_0, we can show that other sets also have cardinality \aleph_0 by finding a bijection between those other sets and the natural numbers.

Thus we can show that other common sets have cardinality \aleph_0 such as the set of all integers or the set of all rational numbers. But then there are other sets that don't have cardinality \aleph_0 such as the set of all subsets of \mathbb{N} or the set of all real numbers.

 

[chroot]

So... a set with cardinality \aleph_0 has countably many elements?

What is the cardinality of the set of real numbers? They are uncountably infinite, right?

Also, I've seen people use \aleph_0 like a number -- they'' even say stuff like 2^{\aleph_0}. This just doesn't make any sense to me. Is it a number? If not, what is it?

- Warren

 

[NateTG]

Originally posted by chroot
All right math geeks, lay it on me. What the hell is aleph zero? Is this the right symbol for it: \aleph_0?

- Warren

Aleph zero is the cardinality of countable infinities. Any infinite set which has the property that there is a bijection from N to the set has cardinality \aleph_0.

Familiar sets with that cardinality include:
Natural Numbers
Integers
Rational Numbers

Sets with cardinality \aleph_0 are called countable because they can be enumerated by using the bijection from N.

 

[master_coda]

Originally posted by chroot
So... a set with cardinality \aleph_0 has countably many elements?

What is the cardinality of the set of real numbers? They are uncountably infinite, right?

Also, I've seen people use \aleph_0 like a number -- they'' even say stuff like 2^{\aleph_0}. This just doesn't make any sense to me. Is it a number? If not, what is it?

- Warren

Yes, a set is countably infinite if and only if it has cardinality
\aleph_0.

It isn't really a number, at least not in the same sense that the natural numbers or real numbers are. But you can still do some arithmetic with them. For example, 2^{\aleph_0} is the cardinality of the set of all subsets of \mathbb{N}, i.e. the power of set \mathbb{N}.

There are some rules for cardinal arithmetic. Given two sets A,B and their cardinal numbers \lvert A\rvert,\lvert B\rvert, we know that:

<br /> \begin{align*}<br /> \lvert A\rvert+\lvert B\rvert&amp;=\lvert(A\cup B)\rvert \\<br /> \lvert A\rvert\cdot\lvert B\rvert&amp;=\lvert(A\times B)\rvert \\<br /> {\lvert A\rvert}^{\lvert B\rvert}&amp;=\lvert(\text{ set of all functions from B to A })\rvert<br /> \end{align*}<br />

Using these rules, we can get results like

<br /> \begin{align*}<br /> \aleph_0+1&amp;=\aleph_0 \\<br /> 2\aleph_0&amp;=\aleph_0 \\<br /> 2^{\aleph_0}&amp;&gt;\aleph_0 \\<br /> \aleph_0^{\aleph_0}&amp;=\mathfrak{c}<br /> \end{align*}<br />

where \mathfrak{c} is the cardinality of the real numbers, and \aleph_0&lt;\mathfrak{c}.

 

[NateTG]

Originally posted by chroot
So... a set with cardinality \aleph_0 has countably many elements?

What is the cardinality of the set of real numbers? They are uncountably infinite, right?

Also, I've seen people use \aleph_0 like a number -- they'' even say stuff like 2^{\aleph_0}. This just doesn't make any sense to me. Is it a number? If not, what is it?

- Warren

For cardinal aritmetic, you can consider 2^{\aleph_0} to be the cardinality of the set of all functions f:\mathbb{N} \rightarrow \{0,1\} or equivalently the cardinality of the set of all countable sequences containting {1,0} as elements.

In set theory A^B is the set of all functions f:A \rightarrow B. A function f:A \rightarrow B is a set of ordered pairs:
f={(a,b)} with the property that for every a \in A there is one, and only one ordered pair (a,b) \in f that contains a.

For example
2^2=|\{0,1\}^{\{A,B\}}|
and
\{0,1\}^{\{A,B\}}
contains
(code tag used for spacing)

{
   {(0,A),(1,A)}
   {(0,A),(1,B)}
   {(0,B),(1,A)}
   {(0,B),(1,B)}
}

So there are four suitable functions, and
2^2=4
as might be expected.

For some people 2^A means the power set of A which is the set of all subsets of A. There is a natural bijection between the set of all functions f:A \rightarrow \{0,1\} and the power set of a, so it works out ok.

 

[Hurkyl]

Minor correction; A^B is the set of all functions from B to A, and exponentiation for cardinal numbers is defined as |A|^{|B|}= |A^B|.


\aleph_1 is defined to be the smallest cardinal number larger than \aleph_0, et cetera. The "continuum hypothesis" states that \aleph_1 = \mathfrak{c} \; (= |\mathbb{R}|). This statement is independant of the other axioms of set theory (i.e. cannot be proven nor disproven).

 

[NateTG]

Originally posted by Hurkyl
Minor correction; A^B is the set of all functions from B to A, and exponentiation for cardinal numbers is defined as |A|^{|B|}= |A^B|.

Obviously, I still need to be more careful...

 

[Hurkyl]

That one always bugs me too; whenever I want to use it I have to sit and think about it a couple minutes to make sure I have it going the right way.

I spent 10 minutes trying to decide if my post was accurate before I hit post.

 

[master_coda]

I even managed to make the same mistake. Which is really sad since I just looked it up before I typed it to make sure I didn't make a mistake.

 

[chroot]

Okay so \aleph_0 = | \mathbb{Z} | = | \mathbb{N} | = | \mathbb{Q} | and \aleph_1 = | \mathbb{R} |.

Is it acceptable to say that \aleph_1 &gt; \aleph_0? Or that the cardinality of the reals is larger than the cardinality of the integers?

I'm not sure I understand where the \mathfrak{c} came from if \aleph_1 \equiv \mathfrak{c}.

Is there an \aleph_2, ad infinitum? This all seems funny to me, that these cardinal numbers obey different sorts of rules than normal numbers. I haven't gotten my head around it yet.

- Warren

 

[master_coda]

Originally posted by chroot
Okay so \aleph_0 = | \mathbb{Z} | = | \mathbb{N} | = | \mathbb{Q} | and \aleph_1 = | \mathbb{R} |.

Is it acceptable to say that \aleph_1 &gt; \aleph_0? Or that the cardinality of the reals is larger than the cardinality of the integers?

I'm not sure I understand where the \mathfrak{c} came from if \aleph_1 \equiv \mathfrak{c}.

Is there an \aleph_2, ad infinitum? This all seems funny to me, that these cardinal numbers obey different sorts of rules than normal numbers. I haven't gotten my head around it yet.

- Warren

It is acceptable to say that \aleph_1&gt;\aleph_0. And you can construct an infinite number of alephs, so \aleph_2, or even \aleph_{\aleph_0} if perfectly valid.

The notation \mathfrak{c}=\lvert\mathbb{R}\rvert is actually the more standard notation. The idea that \aleph_1=\mathfrak{c} is still not really decided. We can't prove that it's true or false, so to use it we have to assume it as an axiom, which most people aren't willing to do. In fact it seems that now most mathematicians believe that opposite, that we should assume \aleph_1\neq\mathfrak{c}. It's kind of like the old 0^0=? issue.

 

[ahrkron]

Originally posted by chroot
Is it acceptable to say that \aleph_1 &gt; \aleph_0?

Yes, by definition. \aleph_1 is defined as the smallest cardinal larger than \aleph_0.

I'm not sure I understand where the \mathfrak{c} came from

This is a name for the cardinality of the reals.

We know that the cardinality of R is larger than that of N, and that \aleph_1 is also greater than |\mathbb{N}|. Whether they (\mathfrak{c} and |\mathbb{R}|)) are the same is not a consequence of their definitions.

Is there an \aleph_2, ad infinitum?

Yes. The cardinality of the power set of A is always larger than that of A, even for infinite sets.

I still remember how dizzy I felt the first time I got to this point.

 

[chroot]

If \aleph_0 \equiv | \mathbb{Z} | and \aleph_0^{\aleph_0} \equiv \aleph_1 \equiv | \mathbb{R} |, what is \aleph_2?

Is it \aleph_0^{\aleph_0^{\aleph_0}}?

Or \aleph_0^{2 \aleph_0}?

What kind of set has cardinality \aleph_2?

If \aleph_0 means "countably infinite" and \aleph_1 means "uncountably infinite," what does \aleph_2 mean?

- Warren

 

[Hurkyl]

\aleph_1 = \mathfrak{c} is unprovable, that's why. Mathematicians prefer to make as few assumptions as possible, and for most applications the continuum hypothesis isn't necessary.

And yes, there are \aleph_2, \aleph_3, and so on for any natural number subscript. I don't know if there is a labelling standard beyond that; e.g. I don't know if people use \aleph_{\aleph_0}.

And yes, cardinal numbers obey different rules from "normal" numbers. (For one, they're not normal numbers. ) They're a very difficult thing to define in their full generality (and I don't know how); the class of cardinal numbers is "too big" to fit in a set.

 

[ahrkron]

Originally posted by Hurkyl
the class of cardinal numbers is "too big" to fit in a set.

Can you expand a little on this? I remember reading that after \aleph_2, \aleph_3, etc., which form a countably infinite set, there was another way of "jumping" to the next class of infinities, but I have completely forgot about that jump.

 

[Hurkyl]

Assuming the generalized continuum hypothesis, \aleph_2 = 2^{\aleph_1} = 2^{\mathfrak{c}}. I think some examples of a set with the cardinality 2^{\mathfrak{c}} are the set of all real functions and the set of curves in the n-space.

But like the continuum hypothesis, the generalized continuum hypothesis is unprovable (I think that even if you assume CH you still can't prove GCH)

If you don't assume GCH, then all you can say is that \aleph_2 is the smallest cardinal number bigger than \aleph_1.

 

[Hurkyl]

Can you expand a little on this?

Assume there exists a set S of all cardinal numbers. For every cardinal number x, there exists a set X_x such that |X_x| = x.

Define T := \bigcup_{x \in S} X_x. We must have |T| \in S, so it's clear that |T| must be the largest cardinal number.

However, 2^{|T|} &gt; |T|, which is a contradiction.

Therefore there is no set of all cardinal numbers.

(P.S.: as I'm thinking about it, I think there are some nasty subtle details in this proof that I'm skimming over...)

 

[NateTG]

Consider this:
|2^A| &gt; |A|
is strict for
A \neq 0

Let G be a mapping A \rightarrow \{0,1\}^A. Then for every a \in A, G(a) is a function A \rightarrow \{0,1\}
Now, construct f:A \rightarrow \{0,1\} in the following way:
f(a)= 1 if G(a)(a)=0 and 0 otherwise.
Clearly f is not in the range of G since G(a)(a) \neq f(a) \forall a \in A
Therefore there are no surjective mappings A \rightarrow \{0,1\}^A, and no bijections can exist.

Proving the other direction is easy:
G(a)(b)=1 \iff a=b is an injective function.

This proves that there are 'infinitely large' infinities.

 

[master_coda]

Actually, you can say that \aleph_2 is the cardinality of the set of all ordinal numbers of cardinality no greater than aleph-one.

I have seen the notation \aleph_{\aleph_0}, although I don't know how commonly it's used. It's also sometimes written \aleph_\omega. But it's also one of the few cardinals where you can prove that \aleph_{\aleph_0}\neq\mathfrak{c} without using the continuum hypothesis.

 

[chroot]

Originally posted by Hurkyl
Therefore the set of all cardinal numbers cannot exist.

*mumbles* mommy.. mommy.. make it stop.

- Warren

 

[master_coda]

Originally posted by NateTG
Consider this:
|2^A| &gt; |A|
is strict for
A \neq 0

Let G be a mapping A \rightarrow \{0,1\}^A. Then for every a \in A, G(a) is a function A \rightarrow \{0,1\}
Now, construct f:A \rightarrow \{0,1\} in the following way:
f(a)= 1 if G(a)(a)=0 and 0 otherwise.
Clearly f is not in the range of G since G(a)(a) \neq f(a) \forall a \in A
Therefore there are no surjective mappings A \rightarrow \{0,1\}^A, and no bijections can exist.

Proving the other direction is easy:
G(a)(b)=1 \iff a=b is an injective function.

This proves that there are 'infinitely large' infinities.

Isn't that just Cantor's diagonal method?

 

[NateTG]

Originally posted by master_coda
Isn't that just Cantor's diagonal method?

Yep - but this is the grown-up version

 

[lethe]

Originally posted by chroot
What the hell is aleph zero?

usually, when speaking, we say "aleph naught", not "aleph zero"

 

[uart]

Question ? Some people above are referring to \aleph_1 as being equal \aleph_0^{\aleph_0}. But why isn't \aleph_1 equal to 2^{\aleph_0}, since I've seen it shown that this is the next cardinal greater than \aleph_0 ?

 

[master_coda]

Originally posted by uart
Question ? Some people above are referring to \aleph_1 as being equal \aleph_0^{\aleph_0}. But why isn't \aleph_1 equal to 2^{\aleph_0}, since I've seen it shown that this is the next cardinal greater than \aleph_0 ?

It hasn't been shown that 2^{\aleph_0} is the next cardinal greater than \aleph_0. It can't be shown - since 2^{\aleph_0}=\mathfrak{c}, the idea that 2^{\aleph_0}=\aleph_1 is just a restatement of the continuum hypothesis.

 

[uart]

Originally posted by master_coda
It hasn't been shown that 2^{\aleph_0} is the next cardinal greater than \aleph_0. It can't be shown - since 2^{\aleph_0}=\mathfrak{c}, the idea that 2^{\aleph_0}=\aleph_1 is just a restatement of the continuum hypothesis.

I've found this thread interesting and informative but there must be something fundamental that I'm not understanding here. I don't know much about this area, previously all I knew was that there were different cardinalities for "countable infinities" versus "uncountable infinities".

So I've learned that \aleph_0 is the cardinality of the natural numbers and that things like 2\,\aleph_0 and 3\,\aleph_0 etc, as well as \aleph_0^2 and \aleph_0^3 etc still have the same cardinality (aleph0) because they can be put in a 1-1 relation with the natural numbers.

But since 2^{\aleph_0} can't be put into a 1-1 relation with the natural numbers then doesn't that mean that 2^{\aleph_0} is larger than \aleph_0 ? And if that is the case then why do you need to go all the way to \aleph_0^{\aleph_0} to find the next thing bigger when 2^{\aleph_0} is bigger already ?

Can you see why I'm confused?

 

[master_coda]

Originally posted by uart
But since 2^{\aleph_0} can't be put into a 1-1 relation with the natural numbers then doesn't that mean that 2^{\aleph_0} is larger than \aleph_0 ? And if that is the case then why do you need to go all the way to \aleph_0^{\aleph_0} to find the next thing bigger when 2^{\aleph_0} is bigger already ?

I can certainly understand your confusion...this isn't really the most intuative subject.

Yes, in fact 2^{\aleph_0}&gt;\aleph_0. In fact, we also have 2^{\aleph_0}=3^{\aleph_0}={\aleph_0}^{\aleph_0}=\mathfrak{c}. All of those cardinalities are actually the same. So if all you want is an example of a cardinality that is larger than \aleph_0, you can use any one.

But what we don't know is if the cardinality of 2^{\aleph_0} is the next largest. In other words, what is the smallest cardinality larger than \aleph_0? We call that cardinality \aleph_1.

 

[HallsofIvy]

But since can't be put into a 1-1 relation with the natural numbers then doesn't that mean that is larger than \aleph_0^{\aleph_0} ? And if that is the case then why do you need to go all the way to to find the next thing bigger when is bigger already ?

You have a right to be confused! Except for uart's

Some people above are referring to \aleph_0^{\aleph_0} as being equal .

I have never seen anyone refer to \aleph_0^{\aleph_0}!

 

[master_coda]

Originally posted by HallsofIvy
I have never seen anyone refer to \aleph_0^{\aleph_0}!

Since {\aleph_0}^{\aleph_0}=\mathfrak{c} I don't see why anyone would use it when they can just use \mathfrak{c} (or any of the other, more common, cardinalities that it's equivalent to).

But it's certainly a valid cardinality. It's the cardinality of the set of all functions f\colon A\rightarrow B where A and B are countably infinite sets.

 

[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 &gt;\aleph_j if i&gt;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&lt;\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 &gt;\aleph_j if i&gt;j.

There are results based on the continuum hypothesis. Since it is independant 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 independance 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-&gt;A&#039; 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&#039; 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.