“a set is a Many that allows itself to be thought of as a One" – george cantor
introduction
this is a quick overview of
cantor’s diagonal proof for all my friends who could not take real analysis in college and had to study social sciences or some other easy classes to prepare for law or business schools. it is also considered to be the mona lisa of mathematical proofs, that is, one of the most beautiful proofs in math of all times.
it illustrates in a profound manner that we can make very precise statements about infinity, and even though the world might infinite and complex, human mind will always understand so long it takes time to think about and build an appropriate image or model of it.
simple infinity and its mirror images
most of us would agree that the set of so-called natural numbers – 1, 2, 3…. – are infinite. moreover, it also seems that we can still count them the way we would anything we see in the natural numbers, for example, the way my younger brother used to count his girl friends before he goth married (though some would be argued this set was not finite and definitely not countable).
indeed mathematicians would say here that the set is countably infinite. most people are happy to accept that, even though we never actually verify that but our mind is convinced at least.
but what does come a bit of a surprise was that the ratios of various integers – the so-called rational numbers – are actually also countably infinite and actually the same size as the set of natural numbers since we can construct a one-to-one mapping or mirror image – or bijection to use the precise mathematical vocabulary - between the two sets.
but can all sets of numbers mapped to this countably infinite set of natural numbers or are there possibly sets that are greater, that are uncountably infinite?
beyond simple infinity: cantor’s diagonal proof
cantor's original proof shows that the interval of all real numbers [0,1] is uncountably infinite. We know that if we can show a one-to-one mapping of these numbers to the set of natural integers, it must be countable. We will just attempt to do that and will discover that [0,1] is actually larger and therefore uncountable, that is, even more infinite in some sense. In fact, it turns out that there are hierarchies of infinity, we can order them. the aleph numbers are a series of numbers used to represent the cardinality (or size) of infinite sets. they are named after the symbol used to denote them, the Hebrew letter aleph. thus, the set of natural numbers is called aleph-null, the set of real numbers aleph-one and so forth.
the proof itself is quite beautiful so i encourage you to follow the argument below, but those who are afraid of math or straining their can skip to the epilogue of this article, or continue to vogue.com to avoid any strenuous thought.
proof
cantor’s proof by contradiction proceeds as follows:
assume (for the sake of argument) that the interval [0,1] is countably infinite.
we may then enumerate all numbers in this interval as a sequence, ( r1, r2, r3, ... )
we already know that each of these numbers may be represented as a decimal expansion.
we arrange the numbers in a list (they do not need to be in order). in the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we pick the one ending in nines. assume, for example, that the decimal expansions of the beginning of the sequence are as follows:
r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...
we shall now construct a real number x in [0,1] by considering the kth digit after the decimal point of the decimal expansion of rk. the digits we will consider are underlined and in bold face, illustrating why this is called the diagonal proof.
r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...
from these digits we define the digits of x as follows.
if the kth digit of rk is 5 then the kth digit of x is 4
if the kth digit of rk is not 5 then the kth digit of x is 5
the number x is clearly a real number (since all decimal expansions represent real numbers) in [0,1]. For the above sequence, for example, we obtain the following decimal expansion:
x = 0 . 4 5 5 5 5 5 4 ...
hence we must have rn = x for some n, since we have assumed that ( r1, r2, r3, ... ) enumerates all real numbers in [0, 1].
however, because of the way we have chosen 4's and 5's as digits in step (6), x differs in the nth decimal place from rn, so x is not in the sequence ( r1, r2, r3, ... ).
this sequence is therefore not an enumeration of the set of all reals in the interval [0,1]. this is a contradiction, which is what was to be shown.
hence the assumption (1) that the interval [0,1] is countably infinite must be false.
epilogue
george cantor is remembered today as a monumental figure in mathematics, the principal author of set theory. since this is now used as the universal language in all parts of mathematics, he can arguably viewed as one of the founding fathers of this discipline.
towards the end of his life he begin writing about literature, attempting to prove that francis bacon was the true author of shakespeare's works, and religion in which he developed his concept of the 'absolute infinite' which he equated with god. he was impoverished during World War I and died in a mental hospital in halle, germany.
No comments:
Post a Comment