No account? Create an account
 set theory - Mathematicus Ridiculus [entries|archive|friends|userinfo] Mathematicus Ridiculus

 [ userinfo | livejournal userinfo ] [ archive | journal archive ]

set theory [Oct. 20th, 2006|08:28 pm]
Mathematicus Ridiculus
 mathphiles[anagrammed]
 [ 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 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

x= 0.x1x2x3...xn

where x an integer from 0 to 9, inclusive.

Now we list out all the real numbers:
x=0.x1x2x3...xn
y=0.y1y2y3...yn
etc.

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
and α2=x2+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 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. From: 2006-10-20 03:34 pm (UTC) (Link)
hello mathphiles! you know, if anyone were to stumble upon this site, i think they'll be more inclined to think that this is some draco site. -.-
haha anyway can i join? i probably won't contribute much though. x) From: 2006-10-23 12:58 pm (UTC) (Link) 