
Re: Problem with Cantor's diagonal argument
Posted:
Feb 15, 2002 6:46 AM


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(k1) by taking CD (bitwise inverse CD).
Q: Does an m_cycle permution yield CD \in R(m1) ? 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/sgrpflt.htm

