||[Oct. 20th, 2006|08:28 pm]
Here's a pretty neat proof that we cannot list all the real numbers in a countable list using reductio ad absurdum. Generally attributed to Georg Cantor, one of the pioneers of set theory. Stole it from my new calculus book, which opens with a
horribly technical chapter on set theory.
A countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. [note that is irrelevant to proof: if you want to prove a set is countable, you can show that there is a one-to-one correspondence between that set and the set of natural numbers, i.e. a bijection. Converse applies too.]
Let us consider the interval (0,1). Assume we can list all the real numbers in (0,1) in a countably infinite column. Also assume that all real numbers x in this interval can be written in a unique decimal expansion of the form
where x an integer from 0 to 9, inclusive.
Now we list out all the real numbers:
Okay now form a real number α where α = 0.α1α2α3...αn
where α1=x1+1if 0 x1 <5 and α1=x1-1 if 5 x1 9
The restriction prevents α from having any any 0s or 9s in its expansion so that it stays within the range (0,1)
However, the expansion for α differs from each of the listed expansions in at least one place (e.g. α differs from x in at least the first decimal place).
There is a contradiction with our initial assumption that we have listed all the real numbers in a countably infinite list.
It follows that we thus cannot list all real numbers in a countable list.
This leads on to show that there is no one-to-one correspondence between (0,1) and the set of positive integers. The set of real numbers is not equivalent to any subset of natural numbers. Hence, the cardinality of the set of natural numbers is less than the cardinality of the set of real numbers.