[FOM] Re: The Myth of Hypercomputation
Timothy Y. Chow
tchow at alum.mit.edu
Tue Feb 17 14:04:54 EST 2004
Toby Ord wrote:
>1. You may have been pointing to this yourself, but there is an
>important issue regarding what we mean by 'definable' here. For
>example, it is possible (if apparently unlikely) that such a constant
>may code some set that is not definable within, say, ZFC but is easily
>definable from our context (such as truth within ZFC). This is the same
>for all fixed notions of definability as we can always diagonalize out
>in an 'obvious' manner. It seems that the notion of definability we
>would like here should be closed under such obvious diagonalizations,
>but no such notion is available.
What do you mean by "definable from our context (such as truth within
ZFC)"? I am guessing that you mean something like this: Let phi(x)
be the formula "x is a real number," or "x is a subset of omega" if
you prefer. Let psi(x) be a formula in the first-order language of
set theory with one free variable. We say that "psi defines a real
number" if "there exists a unique x such that phi(x) and psi(x)" is
a theorem of ZFC. This notion of definability depends on ZFC; if
we choose a stronger system with more theorems, then more formulae
psi are going to "define real numbers." Since one can always apply
Goedel's theorem to "diagonalize out" of theories like ZFC, there is
no way to get rid of the dependence on the theory chosen.
If this is what you mean, then one "way out" is to replace ZFC with the
set of all true sentences of first-order set theory. Then we can say that
"psi defines a real number" if "there exists a unique x such that phi(x)
and psi(x)" is a true sentence. This provides a "context" that might be
called "our context" and can't be "diagonalized out of." Of course, the
problem is that we don't have any good method of telling whether an
arbitrary sentence, such as the continuum hypothesis, is true (though
maybe you hold out hope that someday a hypercomputer will answer all such
questions?---I would actually be very interested in your thoughts on this
question). But it does show that one has to be careful what one means by
"being able to diagonalize out of any fixed notion of definability."
Tim
More information about the FOM
mailing list