set theory 
[Oct. 20th, 200608:28 pm]
Mathematicus Ridiculus

[  mood 
  blank  ]  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 onetoone 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
x= 0.x_{1}x_{2}x_{3}...x_{n} where x an integer from 0 to 9, inclusive.
Now we list out all the real numbers: x=0.x_{1}x_{2}x_{3}...x_{n}y=0.y_{1}y_{2}y_{3}...y_{n}etc.
Okay now form a real number α where α = 0.α_{1}α_{2}α_{3}...α_{n}where α_{1}=x_{1}+1if 0 x_{1 }<5 and α_{1}=x_{1}1 if 5 x_{1} 9 and α_{2}=x_{2}+1
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.
Further notes: This leads on to show that there is no onetoone 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. 

