What is the difference between cardinal and ordinal numbers?

[Greg Bernhardt]

In the https://www.physicsforums.com/showthread.php?t=507003" , we have looked at various types of infinities. In the last section of that post, we have said when we regarded two sets to have equal size (or equal cardinality). We will now flesh out this concept a bit.

Comparing sizes of sets.
In the last part of the previous post, we proposed a definition deciding when two sets have the same size. This definition was

Two sets A and B have the same cardinality if there is a one-to-one correspondence between A and B. We denote this by |A|=|B|.​

Note that we have not yet given meaning to |A| and |B|. Right now, we will just introduce |A|=|B| as a notation. We will give a deeper meaning behind this notation later on.

A set of the same cardinality as {1,...,n} is called finite and is said to have n elements. For example {{1},{2,3}} has 2 elements. The empty set is also called finite and is said to have 0 elements. A set which is not of the same cardinality as a finite set, is called infinite.

An important infinite set is the set of natural numbers $\mathbb{N}=\{0,1,2,3,4,5,...\}$. A set of the same cardinality as of $\mathbb{N}$ is called countably infinite. Infinite sets that are not countable are called uncountable. Intuitively, a set is countably infinite if we can give every element of the set a number. I.e. there is a zeroth element, there is a first element, there is a second element,... The crucial part is that the natural numbers suffice for this process.

The integers are countable
Many important sets are countably infinite. Take $\mathbb{Z}$, the integers, for example. At first, it might not be obvious why this is countable. In fact, we can try numbering it as follows:

The zeroth element is 0, the first element is 1, the second element is 2,..., the n'th element is n,...
​

but then we have not given every element of $\mathbb{Z}$ a number. For example, we have not given -1 a number. However, with some clever reasoning, we can see that following numbering suffices:

The zeroth element is 0, the first element is 1, the second element is -1, the third element is 2, the fourth element is -2,...
​

In general, if n is odd then the n'th element is (n+1)/2 and if n is even then the n'th element is -n/2.

So the integers form a countable set. What about the rational numbers $\mathbb{Q}$?

The rational numbers are countable
Before we show this, we need some more terminology. We already know how to say that sets have an equal cardinality, but we can not yet say what it means for a set A to have smaller cardinality than a set B. We will do this now:

We say that a set A has a smaller cardinality than a set B if there exists a subset $B^\prime\subseteq B$ such that |A|=|B'|. We will denote this as $|A|\leq |B|$.
​

Again, when we write $|A|\leq |B|$, then this is just a notation. We have not yet given meaning to |A| and |B|.

Now, to show that the rational numbers are countable, we can limit our self to the positive rational numbers (just apply the reasoning of above to prove the general case). To give an easy proof that the positive rational numbers are countable, we will need the following fundamental result:

The theorem of Cantor-Bernstein-Schroder: Say that we have sets A, B and C such that $|A|\leq |B|\leq |C|$. If $|A|=|C|$, then also $|A|=|B|$.
​

This theorem is trivial in the finite case, but requires some ingenious method in the infinite case. The proof of this theorem can be found in any good book on set theory.

We will apply this theorem on the natural numbers (which we will take as A) and the positive rational numbers (that we shall take as B). The set that we will pick as C is the set of all couples of natural numbers, i.e. the set

$$\begin{array}{cccccc} (0,0) & (0,1) & (0,2) & (0,3) & (0,4) & ...\\ (1,0) & (1,1) & (1,2) & (1,3) & (1,4) & ...\\ (2,0) & (2,1) & (2,2) & (2,3) & (2,4) & ...\\ (3,0) & (3,1) & (3,2) & (3,3) & (3,4) & ...\\ (4,0) & (4,1) & (4,2) & (4,3) & (4,4) & ...\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}$$

To apply the theorem of Cantor-Bernstein-Schroder, we need to show that this set is countable. But how in Earth can one show such a thing? It was Cantor that was the first to have found a truly marvelous proof of this fact. What he did is to look at the diagonals of the above set, and this would supply him with an ordering. So what he did was:

The first element is (0,0), the second element is (0,1), the third element is (1,0), the fourth element is (0,2), the fifth element is (1,1), the sixth element is (2,0), the seventh element is (0,3),...
​

So this indeed shows that C is countable and that |A|=|C|. So by applying Cantor-Bernstein-Schroder, we have that the rational numbers are countable.

The real numbers are uncountable
A set which is truly bigger then $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Q}$ are the real numbers (denoted by $\mathbb{R}$). This was again shown by Cantor and it is one of the most famous proofs in entire mathematics. What he actually shows is that [0,1] is uncountable, but the theorem of Cantor-Bernstein-Schroder shows that this implies $\mathbb{R}$to be uncountable.

Now, how does Cantor show [0,1] to be uncountable? It goes as follows, say we have a numbering of all the real numbers as:

• The zeroth element is $0.d_{0,0}d_{0,1},d_{0,2}d_{0,3}d_{0,4}...$
• The first element is $0.d_{1,0}d_{1,1},d_{1,2}d_{1,3}d_{1,4}...$
• The second element is $0.d_{2,0}d_{2,1},d_{2,2}d_{2,3}d_{2,4}...$
• The third element is $0.d_{3,0}d_{3,1},d_{3,2}d_{3,3}d_{3,4}...$
• The fourth element is $0.d_{4,0}d_{4,1},d_{4,2}d_{4,3}d_{4,4}...$
• ...
• The n'th element is $0.d_{n,1},d_{n,2}d_{n,3}d_{n,4}...$
• ...

The idea of Cantor was to take the diagonal number $0.d_{0,0}d_{1,1}d_{2,2}d_{3,3}d_{4,4}...$. What we do is change this number slightly: if $d_{i,i}$ is not 4, then we change it to a 4 and if it is a 4 then we change it to a 5.
For example, the number 0.12345654321... is changed to 0.44454445444. This new number, which we denote by $0.c_0c_1c_2c_3c_4...$, is not contained in our numbering. Indeed, it does not equal our zeroth element, since by definition $c_0\neq d_{0,0}$. It does not equal our first element, since $c_1\neq d_{1,1}$. In general, it does not equal our n'th element since $c_n\neq d_{n,n}$, etc. But this is a contradiction since we have assumed all the reals to be numbered.

The continuum hypothesis
So, what we have established is

$$|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|<|\mathbb{R}|$$

A natural question is whether there exists a set C between the rationals and the reals such that

$$|\mathbb{Q}|<|C|<|\mathbb{R}|$$

For years, this was one of the most important unsolved questions in mathematics, but it was finally resolved by Kurt Gödel and Paul Cohen. The answer is not what one should expect. The answer is that it cannot be proved that there is such a set C and it cannot be proved that there isn't such a set C. It's not that we're not smart enough to prove it, it's that the usual axioms of set theory are too weak to prove or disprove the existence of C.

If we want, we can make an axiom that says that such a set C does exist, but it is as valid to make an axiom that says that the set C does not exist. These two axioms lead to two very different kinds of mathematics, but they are both equally valid.The following forum members have contributed to this FAQ:
bcrowell
Hurkyl
micromass
Redbelly98

 

[micromass]

Follow up:

Cardinal and ordinal numbers
https://www.physicsforums.com/showthread.php?t=510966