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: Problem with Cantor's diagonal argument
Replies: 65   Last Post: Mar 4, 2002 1:36 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Nico Benschop

Posts: 1,708
Registered: 12/6/04
Re: Problem with Cantor's diagonal argument
Posted: Feb 15, 2002 6:46 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



Nico Benschop wrote:
>
> Henry wrote:

> >
> > While reading Paul Erdos' story in "My brain is open" I found
> > Cantor's diagonal argument which he used to 'prove' that the
> > decimals between 0 and 1 are uncountable. [...]

>
> [...]
> His diagonal argument to show this is very simple, and has little
> to do with reals on [0,1) which is special interpretation, but
> everything with strings over some alphabet A of at least 2 symbols.
> In fact he shows that whatever list of (binary) strings of lentgh k
> you take (for finite k there are 2^k): any square k x k table of
> such strings has a diagonal that is a string (length k) which is
> not in that listing if you 'swap bitwise' all bits in the diagonal.
> For k=6 there are 2^6= 64 binary strings, and take any selection of 6:
>
> 0 1 1 1 0 0 Diagonal: 0 1 0 0 0 1 (left top to right bottom)
> 1 1 0 1 0 1 swapped: 1 0 1 1 1 0 is not a row in this 6 x 6 table,
> 0 1 0 1 0 1 because it differs in each position
> 1 0 1 0 1 0 from each row, at that position!
> 0 0 0 0 0 0
> 1 1 1 0 1 1
>
> This holds for finite k, no matter how large, and in fact:
> -------- _independent_ of length k ------
> hence (by some axiom) also for infinite k,
> called omega w, the countable ('linear') infinite of Peano's naturals,
> or the integers, including the negative, which also are countable.


Re: finite Cantor Diagonals (CD) as generative principle:

Rather than just *one* extra diagonal, I just wondered for the
finite case of order k: is there a minimum number (maybe < k ?) of
such k x k binary tables which, by permuting rows of each table,
generate as CD's *all* 2^k binary strings of length k ?

There are k! > 2^k (k>3) permutations, but not all generate different
diagonals. A table like the next (k=6) seems to be very 'prolific':
0 0 0 0 0 1 Note: a diagonal entry is not changed if its row
0 0 0 0 1 1 is replaced by a row with the same entry
0 0 0 1 1 1 in that column. E.g: pair swapping involes
0 0 1 1 1 1 4 entries: in rows i,j and cols i,j -
0 1 1 1 1 1 producing a new CD only if the row distance
1 1 1 1 1 1 (symm.difference) \neq 0 there.

Or equivalently: its symmetric image (while also columns may be used):
1. 1 0 0 0 0 0 If 'weight' w(i) is the number of 1's in row i,
2. 1 1 0 0 0 0 and R(w) the set of all k_strings of weight w,
3. 1 1 1 0 0 0 then symmetric analysis would require to
4. 1 1 1 1 0 0 generate all Ranks R(w) for w=0..k
5. 1 1 1 1 1 0 E.g. swap rows (2,3): CD= 0 0 1 0 0 0
6. 1 1 1 1 1 1 or if i<j swap (i,j): CD= 1 in place j, rest 0
\ So swaps yield ranks R(1), and also R(k-1) by
taking -CD (bitwise inverse CD).

Q: Does an m_cycle permution yield CD \in R(m-1) ?
Like (1,2,3) --> 1 1 1 0 ... CD= 0 1 1 0 0 0
1 0 0 0 ...
1 1 0 0 ...
1 1 1 1 0 .
\ ...etc
> [...]
> So exponentiation (^) is really something else, compared with (+) (*).
> In fact, while arithmetic (+) and (*) are both associative and
> commutative operations, while (^) is repeated (*), which itself is
> repeated (+), notice that (^) is neither associative nor commutative!
>
> -- NB - http://home.iae.nl/users/benschop/cantor.htm
> http://home.iae.nl/users/benschop/sgrp-flt.htm







Date Subject Author
2/13/02
Read Problem with Cantor's diagonal argument
Henry
2/13/02
Read Re: Problem with Cantor's diagonal argument
Andy Berget
2/14/02
Read Re: Problem with Cantor's diagonal argument
Mike Oliver
2/14/02
Read Re: Problem with Cantor's diagonal argument
Doug Norris
2/14/02
Read Re: Problem with Cantor's diagonal argument
Keith Keller
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/14/02
Read Re: Problem with Cantor's diagonal argument
Mike Oliver
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dave Seaman
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dave Seaman
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/14/02
Read Re: Problem with Cantor's diagonal argument
Bob Kolker
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dave Seaman
2/14/02
Read Re: Problem with Cantor's diagonal argument
Seth Dutter
2/14/02
Read Re: Problem with Cantor's diagonal argument
mareg@mimosa.csv.warwick.ac.uk
2/14/02
Read Re: Problem with Cantor's diagonal argument
Nico Benschop
2/14/02
Read Re: Problem with Cantor's diagonal argument
mareg@mimosa.csv.warwick.ac.uk
2/14/02
Read Re: Problem with Cantor's diagonal argument
Willondon
2/14/02
Read Re: Problem with Cantor's diagonal argument
Henry
2/14/02
Read Re: Problem with Cantor's diagonal argument
magidin@math.berkeley.edu
2/15/02
Read Re: Problem with Cantor's diagonal argument
Doug Magnoli
2/14/02
Read Re: Problem with Cantor's diagonal argument
mareg@mimosa.csv.warwick.ac.uk
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/14/02
Read Re: Problem with Cantor's diagonal argument
Nico Benschop
2/15/02
Read Re: Problem with Cantor's diagonal argument (re finite case)
Nico Benschop
2/15/02
Read cancel <3C6CD566.97EA8F20@chello.nl>
Nico Benschop
2/15/02
Read Re: Problem with Cantor's diagonal argument
Nico Benschop
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dave Seaman
2/14/02
Read Re: Problem with Cantor's diagonal argument
Herman Jurjus
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dave Seaman
2/15/02
Read Re: Problem with Cantor's diagonal argument
Jon and Mary Frances Miller
2/15/02
Read Re: Problem with Cantor's diagonal argument
Torkel Franzen
2/15/02
Read Re: Problem with Cantor's diagonal argument
Virgil
2/15/02
Read Re: Problem with Cantor's diagonal argument
Harlan Messinger
2/15/02
Read Re: Problem with Cantor's diagonal argument
Virgil
2/15/02
Read Re: Problem with Cantor's diagonal argument
Harlan Messinger
2/15/02
Read Re: Problem with Cantor's diagonal argument
Virgil
2/18/02
Read Re: Problem with Cantor's diagonal argument
Harlan Messinger
2/18/02
Read Re: Problem with Cantor's diagonal argument
Virgil
2/19/02
Read Re: Problem with Cantor's diagonal argument
Harlan Messinger
2/19/02
Read Re: Problem with Cantor's diagonal argument
Virgil
2/19/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
3/4/02
Read Re: Problem with Cantor's diagonal argument
Alexey Dejneka
3/4/02
Read Re: Problem with Cantor's diagonal argument
Torkel Franzen
3/4/02
Read Re: Problem with Cantor's diagonal argument
Alan Stern
2/16/02
Read Re: Problem with Cantor's diagonal argument
Chip Eastham
2/20/02
Read Re: Problem with Cantor's diagonal argument
SRK
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dale Hurliman
2/14/02
Read Re: Problem with Cantor's diagonal argument
Randy Poe
2/14/02
Read Re: Problem with Cantor's diagonal argument
Henry
2/14/02
Read Re: Problem with Cantor's diagonal argument
Randy Poe
2/14/02
Read Re: Problem with Cantor's diagonal argument
Wade Ramey
2/14/02
Read Re: Problem with Cantor's diagonal argument
nospam@auerbachatunity.ncsu.edu
2/14/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/15/02
Read Re: Problem with Cantor's diagonal argument
Chris Menzel
2/15/02
Read Re: Problem with Cantor's diagonal argument
Dudley Brooks
2/14/02
Read Re: Problem with Cantor's diagonal argument
Phil Carmody
2/14/02
Read Re: Problem with Cantor's diagonal argument
Harlan Messinger
2/14/02
Read Re: Problem with Cantor's diagonal argument
Jim Heckman
2/15/02
Read Re: Problem with Cantor's diagonal argument
Randy Poe
2/15/02
Read Re: Problem with Cantor's diagonal argument
LarryLard
2/18/02
Read Re: Problem with Cantor's diagonal argument
Harlan Messinger
2/14/02
Read Re: Problem with Cantor's diagonal argument
George Greene
2/15/02
Read Re: Problem with Cantor's diagonal argument
Duran Castore
2/18/02
Read Re: Problem with Cantor's diagonal argument
Jonathan Hoyle

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.