Cantor subtlety.

gistfile1.txt

Cantor's diagonal argument
==========================

Disclaimer: IANAL (I Am Not A Logician). But sometimes I play one on TV.

I'm using the terminology/notation here from

  http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#An_uncountable_set
  
The cartoon version of the argument is this:

1. Suppose there is an enumeration of T: T = (s_0, s_1, ...).
2. Define s as shown in the article, digit by digit (an inductive
   construction).
3. Walk through all natural numbers:
   Does s match s_0? No; they differ in the first digit.
   Does s match s_1? No; they differ in the second digit.
   and so forth.
4. Therefore, s doesn't match anything in the enumeration of T!
   Contradiction! We're done here!

This argument is fishy. Note we define s inductively, digit by digit. If we
are given a particular value of s beforehand, step 3 is straightforward: we
have a concrete value of s. If s is in T, then since T is enumerable, we
have some k such that s = s_k. We can then do our comparisons in step 3; no
problem.

But that's not really what we're doing. We're definining s by some infinite
process (define the first digit, define the second digit, define the third
digit, and so forth), and then jumping ahead to "the end" and taking the
infinite sequence that results.

If you don't think that is at least worth commenting on, consider this: the
set {0,1}* of all finite sequences of binary digits is countable; the set
{0,1}^N of all infinite sequences of binary digits is not. Now take an
enumeration of {0,1}*. If you build s inductively, then at any point in
that construction, you have constructed a finite number of digits so far, say
d digits. Let's call that truncation of s to its first d digits s[d]. s[d],
being a finite sequence of binary digits, *is* in {0,1}*, which is a
countable set. And suppose that your T is an enumeraton of {0,1}* (which is
easy to construct: first you enumerate all length-0 seqs, then all length-1 seqs,
then all length-2 seqs, and so forth).

It's only once you get to the limit of s=s[omega] that you get a number that
is not actually in your enumeration, and it's not *obvious* that taking the
eventual result of an infinite construction is a well-defined thing at all. I
think there is a way to make this kind of argument watertight, but it does
require some heavy machinery, and it's not at all intuitive.

However: that does not mean that Cantor's diagonal argument is highly
technical or tricky. It is not; it's not the diagonal argument that's
causing problems, it's the form in which we've cast it that causes problems.
Instead, let's take the core of the argument and be less sloppy in how we
formalize it.

First of, infinite sequence of digits. What does that mean? The precise definition
of this is that an infinite sequence 'a' of digits { 0, 1 } is a function

  a : N -> { 0,1 }
  
Okay.
  
1. Suppose there is an enumeration of T: T = (s_0, s_1, ...).
2. We can *define* s as shown in the article. We are looking at infinite
   sequences of things. Clearly, s is an infinite sequence of digits { 0, 1 },
   meaning a function

     s : N -> { 0, 1 }
   
   In fact, we've given an explicit way to compute s(n) for any n, as long as
   we have the enumeration. I hope that is not controversial so far.
   
   Note that we have *defined* a function here; we are not *evaluating* it
   anywhere yet. This is a function; it is a mathematical object; we can
   talk about it, and reason about it, without writing down its value
   everywhere.
3. T is (defined as) the set of all infinite sequences of 0s and 1s, i.e. the set
   of all functions mapping N -> { 0, 1 }. s is such a function. Ergo, s is in T.
4. We asserted in step 1 that we have an enumeration of T; s is in T; so there must
   be some k such that s = s_k.
5. We now evaluate s(k). By construction, s(k) = 1 - s_k(k) != s_k(k). So
   s and s_k differ in the k'th position (and potentially earlier), so they cannot
   be equal. (Our definition of functional equality is precisely that they agree
   everywhere). Contradiction.

Note that this proof does *not* use any inductive reasoning: we have a set T with
elements that have a defining property; we define a thing, s; we show that s has T's
defining property, so it is in T; T has an enumeration, so given an element we can
ask "where is this in the list"; we look at that element in the list and verify that
nope, this can't be it, so we have our contradiction.

In your last step 4, don't you mean we have some k such that s = T_k instead of we have some k such that s = s_k ?