The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Problem with Cantor's diagonal argument

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Feb 15 2002, 6:46 am
Newsgroups: sci.math, sci.logic
From: Nico Benschop <n.bensc...@chello.nl>
Date: Fri, 15 Feb 2002 12:46:00 +0100
Subject: Re: Problem with Cantor's diagonal argument

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!