[FOM] Re: Comment on Church's Thesis

[Timothy Y. Chow]

On Mon, 12 Jan 2004, Alexander M Lemberg wrote:
> Well, I must be missing something, because I don't see the difference
> between what you are saying here and what I said. Maybe you can clarify
> the difference.

On the standard view, no strictly mathematical argument depends on
Church's thesis.  Your objection, as I understood it, was to draw an
analogy:

Undecidability proof : Church's thesis :: Cantor's proof : actual infinity

My response is that the correct "dictionary" between the two sides is:

Undecidability proof   <->   Cantor's proof
Effective method       <->   Actual infinity
Turing machine         <->   Set-theoretic infinity
Church's Thesis        <->   Infinity Thesis

Here the "Infinity Thesis" is something like, "The informal concept of
actual infinity is correctly captured by its formalization in set theory."

Sazonov was saying that the undecidability proof doesn't depend on
Church's Thesis, and that it *couldn't*, because the proof is strictly
mathematical while Church's Thesis isn't.  By analogy, if Cantor's proof
appealed to the Infinity Thesis directly, then your criticism would be
valid.  But it doesn't; it simply uses the set-theoretic concept directly,
just as the undecidability proof uses the Turing machine concept directly.
So your objection is met.

Tim