# What the hell is aleph zero?

1. Dec 4, 2003

### chroot

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

- Warren

2. Dec 4, 2003

### Ambitwistor

Re: Aleph0?

Yes, that's the right symbol. It's the cardinality of the integers.

3. Dec 4, 2003

### master_coda

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

If $\aleph_0$ just refered 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.

4. Dec 4, 2003

### chroot

Staff Emeritus
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

5. Dec 4, 2003

### NateTG

Re: Aleph0?

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.

6. Dec 4, 2003

### master_coda

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*} \lvert A\rvert+\lvert B\rvert&=\lvert(A\cup B)\rvert \\ \lvert A\rvert\cdot\lvert B\rvert&=\lvert(A\times B)\rvert \\ {\lvert A\rvert}^{\lvert B\rvert}&=\lvert(\text{ set of all functions from B to A })\rvert \end{align*}

Using these rules, we can get results like

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

where $\mathfrak{c}$ is the cardinality of the real numbers, and $\aleph_0<\mathfrak{c}$.

Last edited: Dec 4, 2003
7. Dec 4, 2003

### NateTG

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)
Code (Text):

{
{(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.

Last edited: Dec 4, 2003
8. Dec 4, 2003

### Hurkyl

Staff Emeritus
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).

Last edited: Dec 4, 2003
9. Dec 4, 2003

### NateTG

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

10. Dec 4, 2003

### Hurkyl

Staff Emeritus
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.

11. Dec 4, 2003

### 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.

12. Dec 4, 2003

### chroot

Staff Emeritus
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

13. Dec 4, 2003

### master_coda

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.

Last edited: Dec 4, 2003
14. Dec 4, 2003

### ahrkron

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

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.

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.

15. Dec 4, 2003

### chroot

Staff Emeritus
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

Last edited: Dec 4, 2003
16. Dec 4, 2003

### Hurkyl

Staff Emeritus
$\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.

17. Dec 4, 2003

### ahrkron

Staff Emeritus
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.

18. Dec 4, 2003

### Hurkyl

Staff Emeritus
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$.

19. Dec 4, 2003

### Hurkyl

Staff Emeritus
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...)

Last edited: Dec 4, 2003
20. Dec 4, 2003

### 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.