[FOM] Cantor's argument

[William Tait]

On Sunday, February 2, 2003, at 05:42  PM, Giuseppina Ronzitti wrote:

> Alasdair Urquhart wrote:
>
>> Dean Buckner presents a "non-mathematical"
>> application of Cantor's diagonal argument.
>> He seems to think it shows that there is
>> a problem with the diagonal method.
>>
>> For clarity, let me restate the argument.
>> We assume that we have a listing of concepts
>> C_1, C_2, C_3, ... .  Let us assume that
>> by "concept" we mean "predicate applying to
>> the natural numbers."  Now consider the diagonal
>> concept defined by:
>>
>>         D(n) <--> ~C_n(n).
>>
>> If this concept is in the list, say D = C_k,
>> then we have D(k) <--> C_k(k), but also
>> D(k) <--> ~C_k(k), a contradiction.
>>
>> About this argument, we can say the following.
>> First, it is completely constructive, and quite
>> unproblematic from the intuitionistic point of
>> view.
>
> As far as I understand, you also need the assumption that each 
> predicate
> C_n be decidable, which intuitionistically needs not to be the case. If
> one discharges this assumption,  no contradiction arises.
>

I don't see that, Giuseppina. Assume  that D is C_n for some n. This  
yields D(n) <=> -D(n). So the assumption that D(n) yields the 
contradiction D(n) and -D(n). Thus, we have proved (constructively) 
-D(n). From this, D(n). Hence, a contradiction. So, -[there is an n 
such that D = C_n].

Of course, another question is what can one do with the diagonal 
argument in constructive mathematics.

Bill Tait