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

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 ]
Charlie-Boo

Posts: 1,588
Registered: 2/27/06
Re: Cantor's first proof in DETAILS
Posted: Nov 13, 2012 7:52 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Nov 12, 12:00 pm, Zuhair <zaljo...@gmail.com> wrote:
> On Nov 12, 5:09 pm, Charlie-Boo <shymath...@gmail.com> wrote:
>
>
>
>
>

> > 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
>
> What the references are for then? you'll get the informal level of
> this argument there.
> To go explicate every bit and piece informally as well as formally
> would be really taxing.
>
> Zuhair


The first link has no high level description, the second link is empty
and the 3rd one does not show a parallel proof at a high level.

I can hardly imagine a person writing a proof without first developing
it at a high level then working out the details. Like any good
programmer, one can include the high level in parallel with the
details. If you want to be a bad programmer, then you have raised the
cost of one contributing (analogous to mainintain someone else's
software) which is your decision. Good luck. :)

C-B


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.