
Cantor's first proof in DETAILS
Posted:
Nov 12, 2012 4:05 AM


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 online 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_i1 < b_i < b_i1 But also i>0 > a_i1 < a_i < b_i1 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_i1 and < b_i1, 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_i1 i>0 > a_i < a_i+1 < b_i1 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_i1, 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

