# Proof that aleph null is the smallest transfinite number?

The wikipedia page on the cardinal numbers says that $\aleph_0$, the cardinality of the set of natural numbers, is the smallest transfinite number. It doesn't provide a proof. Similarly, this page makes the same assertion, again without a proof.

How does one prove there is no smaller transfinite number? Equivalently (I think), why is there no smaller infinite set than the natural numbers?

-

This is a consequence of the following theorem:

Suppose that $A$ is a set of integers, then either $A$ is finite, or $|A|=|\Bbb N|$.

Since we define $\aleph_0$ to be the cardinality of $\Bbb N$, this means that every infinite subset of a set of size $\aleph_0$ is itself of size $\aleph_0$, and so there cannot be a smaller infinite cardinal.

Note that the above proves that $\aleph_0$ is a minimal element of the infinite cardinals. There is no smaller. To prove that it is in fact the smallest of the infinite cardinals we need to use some other set theoretical assumptions (e.g. every two cardinals are comparable) which are commonly assumed throughout mathematics nowadays.

The proof of the aforementioned theorem is simple, by the way. Suppose that $A$ is infinite, then the map $a\mapsto |\{a'\in A\mid a'<a\}|$ is a bijection between $A$ and $\Bbb N$. The proof of that is by induction.

-
Curious that you did not mention the key use of the axiom of choice... –  Andres Caicedo Oct 6 '13 at 21:16
@Andres: I thought about it, but I feel that it might cause more damage than help to someone inexperienced with infinite sets. I'm still tempted to make that edit. –  Asaf Karagila Oct 6 '13 at 21:17
As a parenthetical remark, at least. –  Andres Caicedo Oct 6 '13 at 21:21
When you're right, you're right. :-) –  Asaf Karagila Oct 6 '13 at 21:24
I found a related question here. Is the "every two cardinals are comparable" assumption the same as $2^{\aleph_\alpha} = \aleph_{\alpha+1}$? How does it relate to the axiom of choice? Further reading would be as welcome as a concrete answer :-) –  statusfailed Oct 6 '13 at 22:43
show 1 more comment

This really comes down to definitions. It is not uncommon to define "finite" to mean "a cardinality strictly less than that of $\mathbb N$", in which case what you're looking for is just what the definition says and allows no further proof.

If you want more than that (and what you want is actually a proof from definite axioms and definitions, rather than just an informal argument that it's probably about right), then you need to start by choosing a particular different definition of "finite" to prove things about.

-
I have not seen that "not uncommon" definition in practice anywhere, or in any of a large number of standard sources. –  Andres Caicedo Oct 6 '13 at 21:28
@AndresCaicedo: It's usually written with $\omega$ instead of $\mathbb N$, and after having proved that the cardinalities strictly smaller than an initial ordinal are exactly the cardinalities of its elements. –  Henning Makholm Oct 6 '13 at 21:31
No, it is not. Finite means "of the same size as a natural number". One then can prove that this notion has the property you state. Yes, natural numbers are the elements of $\omega$. Yes, membership among ordinals is commonly denoted by $<$. No, this is not the same as what you said, as in this context $n<\omega$ simply means "$n$ is an element of $\omega$", not "$n$ has size strictly smaller than $\omega$". –  Andres Caicedo Oct 6 '13 at 21:34

$\Bbb N$ is the union of all finite ordinals $[n]:=\{0,1,2,\dots,n-1\}$.

Hence, if a set $A$ is not finite, then each $[n]$ embeds into it. In particular, we can define embeddings $f_n:[n]\hookrightarrow A$ on top of each other, i.e. satisfying $f_n(k)=f_{n-1}(k)$ for all $k<n-1$. But that altogether (considering $\bigcup_nf_n$) gives an embedding of $\Bbb N$ into $A$, so that $\aleph_0\le |A|$.

-
The part after "Hence," is unclear. –  Asaf Karagila Oct 6 '13 at 21:15
Well a set $M$ is infinite if for every finite subset $U \subsetneq M$ there exists a $x \in M, x\notin U$. Consequently, you will be able to construct a sequence $(x_n)_{n \in \mathbb{N}}$ of distinct elements in $M$. Therefore $|M| \ge \aleph_0$
This is not true as written. Replace $\subsetneq$ with $\subseteq$, and it will be fine now. –  Andres Caicedo Oct 6 '13 at 21:30
One property of cardinals says that if there is an injection $f:A \to B$ then the cardinality of $A$ is less than or equal to the cardinality of $B$. If $B$ is infinite, then you can choose any $b_1 \in B$ and define $f(1) = b_1$, and then choose different $b_2 \in B$ so that $f(2) = b_2$, and so forth and you will get an injection $f:{\mathbb N} \to B$ if $B$ is infinite (because for every $n$, you have infinitely many choices left in $B$ for $f(n)$). So $|B| \geq |{\mathbb N}|$ if $B$ is infinite, thus $| \mathbb{N}|$ is the smallest infinite cardinal.