Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Cantor's first proof in DETAILS
Replies: 34   Last Post: Dec 1, 2012 10:56 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Zaljohar@gmail.com

Posts: 2,665
Registered: 6/29/07
Cantor's first proof in DETAILS
Posted: Nov 12, 2012 4:05 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Apologies beforehand for this long proof, and for any possible errors,
typos, mistakes that most possibly would be there with such a long
draft. I'v written this with the intention to give what I think it to
be the complete story of Cantor's first proof. So the following is my
view of this proof, it came from reading on-line proofs other than the
original one, since I don't have the original article of Cantor.
References given below.

If a mistake in this proof is noticed, then please feel free to
outline it.

CANTORS FIRST PROOF OF UNCOUNTABILITY OF REALS
--------------------------------------------------------------------------------

Statement: There is no bijection between the set N of all naturals
and the set R of all reals.

Proof:
We prove that for every injection (x_n) from N to R, there
exist a real J such that J not in the range of (x_n).

Notation: for every x_i, i shall be called the place of x_i in (x_n),
while x is the value of x_i. Whenever mentioned in this article
symbols < , > , = and =/= are comparisons of the values of entries of
sequences mentioned, while the places of those entries shall be
compared by "lies before" , "lies after" , is the first entry, is the
last entry, in the same place, etc..

(x_n) is said to have the Intermediate Value property (IVP) iff
for every two entries x_i,x_j of (x_n) there exist an entry x_k
of (x_n) such that: x_i < x_k < x_j or x_i > x_k > x_j

If (x_n) don't possess IVP, then it is easy to find J.

If (x_n) possess IVP, then we construct sequences (a_n), (b_n)
in the following manner:

Let a_0 = x_0
Let b_0 be the first entry in (x_n) such that b_0 > a_0.
Let a_i+1 be the first entry in (x_n) such that a_i < a_i+1 < b_i.
Let b_i+1 be the first entry in (x_n) such that a_i+1 < b_i+1 < b_i.

We notice that for every i,j: j>i -> (a_j > a_i) & (b_j < b_i)
i.e. (a_i) is an increasing sequence, and (b_i) is a decreasing
sequence.

We also notice that for every i: a_i < b_i
since a_0 < b_0, and since by definition
for all i. a_i+1 < b_i+1, then by
induction:

for all i: a_i < b_i.

From that we have the following result:

Result 1: for all i. for all a_i. Exist a_i+1 (a_i < a_i+1).
Result 2: for all i. for all b_i. Exist b_i+1 (b_i+1 < b_i)

Result 3: for all i,j: a_i < b_j
Proof: either i=j, or i<j or i>j
if i=j then a_i < b_i & b_i = b_j so by identity a_i < b_j
if i<j then a_i < a_j & a_j < b_j then by transitivity a_i < b_j
if i>j then a_i < b_i & b_i < b_j then by transitivity a_i < b_j

Define (lies before): for all i,k. a_i lies before x_k in (x_n) iff
Exist m. a_i = x_m & m < k

Define (lies after): for all i,k. a_i lies after x_k in (x_n) iff
Exist m. a_i = x_m & k < m.

Similar definitions applies to b_i.

Result 4: for all i: b_i lies after a_i in (x_n)

Proof: b_0 lies after a_0 by definition.
for all i. i>0 -> a_i-1 < b_i < b_i-1
But also i>0 -> a_i-1 < a_i < b_i-1
Now if we suppose that b_i lies before a_i in (x_n)
then a_i will no longer be the first item in (x_n)
that is > a_i-1 and < b_i-1, unless b_i lies at
the same place of a_i in (x_n). which is impossible
since a_i < b_i and (x_n) is an injection.

Result 5: for all i: a_i+1 lies after b_i in (x_n)

Proof: a_1 lies after b_0 in (x_n).
i >0 -> a_i < b_i < b_i-1
i>0 -> a_i < a_i+1 < b_i-1
Now if a_i+1 lies before b_i in (x_n), then
b_i would no longer be the first item in (x_n)
that is > a_i and < b_i-1, unless a_i+1 and b_i
lie at the same place in (x_n), which is impossible
since a_i+1 < b_i and (x_n) is an injection.

Result 6: for all i: a_i+1 lies after a_i & b_i+1 lies after b_i
Since at each i. a_i+1 lies after b_i which lies after a_i
then by transitivity a_i+1 lies after a_i
Similarly b_i+1 lies after a_i+1 which lies after b_i.

Informally as i increase each a_i,b_i is coming from a deeper
and deeper place in (x_n).

Define (external): for all k. x_k external in (x_n) iff
x_k an item of (x_n) &
x_k not an item of (a_n) &
x_k not an item of (b_n).

Result 7: For every x_k. x_k external in (x_n) ->
Exist i. (a_i lies before x_k in (x_n) & a_i+1 lies after x_k in
(x_n))

Proof: x_0 (which is a_0) lies before x_k, and if the above
doesn't hold then for every a_i lying before x_k in (x_n)
a_i+1 would lie also before x_k in (x_n), since the place
of each a_i is a natural number and so is k, then this would
entail the existence of infinitely many naturals before k
which is absurd.

Define : a_i is last of (a_n) lying before x_k in (x_n) iff
(a_i lies before x_k in (x_n) & ~ (a_i+1 lies before x_k in (x_n)))

Result 8: For all k. x_k external in (x_n) ->
for all i. (a_i is last of (a_n) lying before x_k in (x_n) ->
b_i lies before x_k in (x_n) or b_i lies after x_k in (x_n))

Proof: properties of natural numbers, and definition of external.

Define (intervene): for all k,i. x_k intervene a_i,b_i in (x_n) iff
x_k is external in (x_n) &
a_i is last of (a_n) lying before x_k in (x_n) &
b_i lies after x_k in (x_n).

Define (passed): for all k,i. x_k passed a_i,b_i in (x_n) iff
x_k is external in (x_n) &
a_i is last of (a_n) lying before x_k in (x_n) &
b_i lies before x_k in (x_n).

Result 9: for all k. x_k is external in (x_n) ->
Exist i. x_k intervene a_i,b_i in (x_n) or x_k passed a_i,b_i in
(x_n).

Proof: Results 7.8 and definitions above.

Lemma 1: for all k,i. x_k intervene a_i+1,b_i+1 in (x_n) ->
x_k < a_i+1 or x_k > b_i

Proof: if not then x_k would be an item of (x_n) that is
> a_i+1 & < b_i and since it lies before b_i+1 in
(x_n) then this violates the definition of b_i+1.

Lemma 2: for all k,i. x_k passed a_i,b_i in (x_n) ->
x_k < a_i or x_k > b_i

Proof: if not then x_k would be an item of (x_n)
that is > a_i & < b_i and since it lies before a_i+1
in (x_n) then this violates the definition of a_i+1.


let L be the least upper bound on (a_n), that is

(for all i. a_i =< L) & for all X. (for all i. a_i =< X) -> L =< X.

Theorem 1. for all i. a_i =/= L

Proof: assume there exist t such that a_t = L
then a_t+1 > a_t, but from definition of L we
must have L >= a_t+1, and since L=a_t
thus we'll arrive at a_t >= a_t+1 > a_t
which is absurd.

Theorem 2. for all i. L < b_i

Proof: assume there exist r such that b_r =< L
then b_r+1 < L and b_r+1 >= a_i for all i
thus L is not the "least" upper bound of (a_n).
A contradiction.

Theorem 3: for all i,j: a_i < L < b_j

Proof: Definition of L and Theorem 1,2.


Theorem 4. for all i. x_i =/= L

Proof:
Suppose that x_k = L, then x_k is external in (x_n) (Th.1,2)

for all i If x_k intervene a_i+1,b_i+1 in (x_n), then
x_k < a_i+1 or x_k > b_i , But a_i+1 < L < b_i.
A contradiction.

If x_k intervene a_0,b_0, then x_k < a_0
But a_0 < L and L=x_k.
A contradiction.

If x_k passed a_i, b_i in (x_n), then
x_k < a_i or x_k > b_i, But a_i < L < b_i.
A contradiction.

Let J=L

QED

Corollary:
For every injection (x_n*) from N* to R, where
N* is bijective to N. Then (x_n*) misses a real
from its range.

Proof: Let (g(n*)) be a bijection from N* to N.
Define (x_n) as {y_n| Exist n*: y_n* in (x_n*) & g(n*) = n}
so range of (x_n) = range of (x_n*)
But domain of (x_n) is N.
So (x_n) is an injection from N to R.
Thus it misses a real. (above proof),
so (x_n*) misses a real too, since it has
the same range of (x_n).

QED

References:

[1] http://www.math.jhu.edu/~wright/Cantor_Pick_Phi.pdf


[2]http://www.proofwiki.org/wiki/Real_Numbers_are_Uncountable/
Cantor's_First_Proof


[3]http://en.wikipedia.org/wiki/Cantor's_first_uncountability_proof


Zuhair


Date Subject Author
11/12/12
Read Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/12/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/12/12
Read Re: Cantor's first proof in DETAILS
Charlie-Boo
11/12/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/13/12
Read Re: Cantor's first proof in DETAILS
Charlie-Boo
11/15/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
12/1/12
Read Re: Cantor's first proof in DETAILS
Frederick Williams
11/12/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/12/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/12/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/12/12
Read Re: Cantor's first proof in DETAILS
Shmuel (Seymour J.) Metz
11/12/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/13/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/13/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/13/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/13/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/13/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/13/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/13/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/13/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/13/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/13/12
Read Re: Cantor's first proof in DETAILS
Shmuel (Seymour J.) Metz
11/13/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/13/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/13/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/14/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/14/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/14/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/14/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/14/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/16/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/16/12
Read Re: Cantor's first proof in DETAILS
Uirgil
11/16/12
Read Re: Cantor's first proof in DETAILS
Zaljohar@gmail.com
11/16/12
Read Re: Cantor's first proof in DETAILS
LudovicoVan
11/13/12
Read Re: Cantor's first proof in DETAILS
Shmuel (Seymour J.) Metz

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.