Date: Nov 12, 2012 9:09 AM Author: Charlie-Boo Subject: Re: Cantor's first proof in DETAILS On Nov 12, 4:05 am, Zuhair <zaljo...@gmail.com> wrote:

> 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

This is very sloppy. You need to give a high level explanation

first. Otherwise, people have to waste time going through formalisms

when the problem is with the logic and can be exposed by examining the

logic alone. You immediately go into your formalisms. This is like

trying to figure out someone's computer programs without the specs

(higher level) or documentation (redundant statements that serve only

to clarify by expressing something in a different way.)

C-B