Log in

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
[mood |blankblank]

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:

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. 

[User Picture]From: jializz
2006-10-20 03:34 pm (UTC)
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)
(Reply) (Thread)
From: anagrammed
2006-10-22 04:36 am (UTC)
haha yup yup you can contribute all your puzzles and nonograms etc.!:D we'll wait for yangzhe and dengying to second and third this.
(Reply) (Parent) (Thread)
[User Picture]From: stupidpot
2006-10-23 12:58 pm (UTC)
oh yes of course you can join! (i can't figure out how to invite though, i think you have to request to join before we accept!) i didn't even realise there were posts here! updates dont get sent to my inbox! ! !
(Reply) (Parent) (Thread)
From: anagrammed
2006-10-24 02:58 am (UTC)
you can invite anyone if you sign in and click on 'manage invites' on the bar on the top of the screen. you need maintainer status though (which you have). yup so i invited jiali
(Reply) (Parent) (Thread)