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:

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

Using these rules, we can get results like

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

where $\mathfrak{c}$ is the cardinality of the real numbers, and $\aleph_0<\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 independent 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 > \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 > \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>\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 > \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|} > |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| > |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| > |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}>\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.