[FOM] Cantor's argument
William Tait
wwtx at earthlink.net
Mon Feb 3 00:20:23 EST 2003
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
More information about the FOM
mailing list