Philosophy of Mathematics/Cardinality

Given the set {10, 56, 29, 72}, I ask you: how many elements are in this set?

In order to answer this question, you likely looked at the element "10" and thought "1", for "56", "2", and so on, until you ended up with the set {1, 2, 3, 4}. From this you concluded that the set had four elements.

Recall a common construction for the natural numbers:

• ∅ is 0
• {∅} is 1
• {∅, {∅}} is 2
• {∅, {∅}, {∅, {∅}}} is 3

and so on.

This construction is convienent precisely because the number of elements, that is, the 'cardinality' of the set is identical to our intuiton of what a natural number is.

So then, the symbols |A|=|B| mean that there exists a one-to-one mapping from A onto B.

{10, 56, 29, 72}
  |   |   |   |
  v   v   v   v
{ 1,  2,  3,  4}

This is the meaning of the notion of cardinality.

Infinite Sets

It seems obvious that we can find a cardinality for any finite set. But what of infinite sets?

The procedure for proving two infinite sets have the same cardinality involves setting up a mapping between the two sets and proving that it is one-to-one.

For example: Prove |Q|=|N|, if Q is the set of rational numbers and N is the set of natural numbers.

Recall that the rational numbers are the set of all numbers in the form $-1^{n}{\frac {a}{b}}$

Since n, a, and b are all natural numbers, we can use a Gödel numbering scheme to map each rational number onto a natural number:

$f(n,a,b):N^{3}\rightarrow N=2^{n}3^{a}5^{b}$

And such a mapping is one-to-one by the fundamental theorem of arithmetic.

This is a rather powerful result. It should be clear that any set whose elements can be totally expressed as a finite set of natural numbers has the same cardinality as that of the natural numbers. Because of this, the cardinality of the natural numbers has a special name, $\aleph _{0}$ (Aleph-Null). Sets that have cardinality $\aleph _{0}$ are called countable or denumerable.

Some sets have even greater cardinality than N, however. The set of real numbers, for instance, is even greater.