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?

Solution 1:

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.

Solution 2:

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.