Another way of looking at the alephs

English: Georg Cantor
English: Georg Cantor (Photo credit: Wikipedia)

This is another insight gained from Wheels, Life and Other Mathematical Amusements– this time about the transfinite numbers.

The smallest transfinite number, so -called \aleph_0 is that of the countable infinity, or the counting numbers (the integers). Start at 1 (or 0) and keep going.

But how many sets can one make from the counting numbers? Well we know that for a set with n members there are 2^n possible subsets including the empty set \emptyset and the original set itself. Therefore we have 2^{\aleph_0} subsets of the integers.

So how big is 2^{\aleph_0}? The same size as the continuum, Georg Cantor‘s hypothesised \aleph_1 (i.e., the next biggest transfinite number) – though this hypothesis has never been proved and work continues on demonstrating there is a smaller transfinite number between \aleph_0 and the cardinality of the continuum.

Normally one sees the continuum explained as uncountable via the “diagonalisation argument” but the book makes a slightly different, if ultimately equivalent proof via contradiction:

Take all the subsets and assign an integer to each one.

If the integer is assigned to the subset containing the integer  which it has been assigned then label it ‘blue’, if the integer is assigned to a subset it does not contain then label it ‘red’.

So all the red integers themselves form a subset of the original set, can it be matched to a blue integer? No because then it would match to a subset that contained the integer, but as its red it cannot.

So can it then be matched with a red element? No because then a red element would be matched with a red element and should therefore be blue … a contradiction.

If you think about this for a bit you will also see it is directly equivalent to the diagonalisation argument and thus the cardinality of the subsets of the countable numbers is the same as that of the continuum.


One response to “Another way of looking at the alephs”

%d bloggers like this: