```Date: Nov 12, 2012 4:05 AM
Author: Zaljohar@gmail.com
Subject: Cantor's first proof in DETAILS

Apologies beforehand for this long proof, and for any possible errors,typos, mistakes that most possibly would be there with such a longdraft. I'v written this with the intention to give what I think it tobe the complete story of Cantor's first proof. So the following is myview of this proof, it came from reading on-line proofs other than theoriginal 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 tooutline it.CANTORS FIRST PROOF OF UNCOUNTABILITY OF REALS--------------------------------------------------------------------------------Statement: There is no bijection between the set N of all naturalsand the set R of all reals.Proof:We prove that for every injection (x_n) from N to R, thereexist 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 articlesymbols < , > , = and =/= are comparisons of the values of entries ofsequences mentioned, while the places of those entries shall becompared by "lies before" , "lies after" , is the first entry, is thelast entry, in the same place, etc..(x_n) is said to have the Intermediate Value property (IVP) ifffor every two entries x_i,x_j of (x_n) there exist an entry x_kof (x_n) such that: x_i < x_k < x_j or x_i > x_k > x_jIf (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_0Let 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 decreasingsequence.We also notice that for every i: a_i < b_isince a_0 < b_0, and since by definitionfor all i. a_i+1 < b_i+1, then byinduction: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_jProof: either i=j, or i<j or i>jif i=j then a_i < b_i & b_i = b_j so by identity a_i < b_jif i<j then a_i < a_j & a_j < b_j then by transitivity a_i < b_jif i>j then a_i < b_i & b_i < b_j then by transitivity a_i < b_jDefine (lies before): for all i,k. a_i lies before x_k in (x_n) iffExist m. a_i = x_m & m < kDefine (lies after): for all i,k. a_i lies after x_k in (x_n) iffExist 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-1But also i>0 -> a_i-1 < a_i < b_i-1Now 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 atthe same place of a_i in (x_n). which is impossiblesince 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-1i>0 ->  a_i < a_i+1 < b_i-1Now if a_i+1 lies before b_i in (x_n), thenb_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_ilie at the same place in (x_n), which is impossiblesince 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_iSince at each i. a_i+1 lies after b_i which lies after a_ithen by transitivity a_i+1 lies after a_iSimilarly 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 deeperand deeper place in (x_n).Define (external): for all k. x_k external in (x_n) iffx_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 abovedoesn'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 placeof each a_i is a natural number and so is k, then this wouldentail the existence of infinitely many naturals before kwhich 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) iffx_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) iffx_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_iProof: 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_iProof: 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+1in (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  =/= LProof: assume there exist t such that a_t = Lthen a_t+1 > a_t, but from definition of L wemust have L >= a_t+1, and since L=a_tthus we'll arrive at a_t >= a_t+1 > a_twhich is absurd.Theorem 2. for all i. L < b_iProof: assume there exist r such that b_r =< Lthen  b_r+1 < L and b_r+1 >= a_i for all ithus L is not the "least" upper bound of (a_n).A contradiction.Theorem 3: for all i,j: a_i < L < b_jProof: Definition of L and Theorem 1,2.Theorem 4. for all i. x_i =/= LProof: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), thenx_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_0But a_0 < L and L=x_k.A contradiction.If x_k passed a_i, b_i in (x_n), thenx_k < a_i or x_k > b_i, But a_i < L < b_i.A contradiction.Let J=LQEDCorollary:For every injection (x_n*) from N* to R, whereN* is bijective to N. Then (x_n*) misses a realfrom 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 hasthe same range of (x_n).QEDReferences:[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_proofZuhair
```