[FOM] Cantor's argument

[Giuseppina Ronzitti]

William Tait wrote:

> 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].

Perhaps I am wrong, anyhow the argument seems to be as follows: no predicate
in the list C_0, C_1, C_2, ... is decidable; defining D = C_n we agree that D
is not decidable as well. Thus ~\forall n [D(n) v ~D(n)] and thus in
particular  ~\forall n [C_n(n) = D(n) = ~C_n(n) ] .

G. Ronzitti
Genova, Italy
Europe