FOM: Re: FOM Church's Theory - an argument against(?)
A.J. Franco de Oliveira
francoli at mail.eunet.pt
Mon Mar 19 18:08:25 EST 2001
at 12:51 29-01-2001 -0800, Charlie Silver wrote:
> I don't understand what would constitute a proof of Church's
> Thesis, since the notion of an effectively computable function is an
> intuitive concept, not a mathematical one. I can understand what a
> disproof might look like. suppose someone were to present a function
> that seemed intuitively effectively computable but wasn't recursive.
> if this view became widespread in the mathematical community (that
> the given non-recursive function was intuitively effectively computable),
> then church's thesis would be thought false.
I have an argument against C'sT, precisely in the other direction,
which goes back to a talk that I gave in 1989 at a meeting in Lisbon
(in honor of the late portuguese locician Hugo Ribeiro, logic professor
in the USA).
Consider first the following (later I shall come back to C'sT):
1) "Turing computable (TC)", or some equivalent, is a
formalized mathematical notion which pressuposes a mathematical
notion of natural number. Now this, in any usual sense, is abstract,
impredicative in nature, and imbedded in some theory of sets;
2) "effectively computable (EC)" is an intuitive notion resting
on the intuitive notion of natural number which, as we know, we cannot
hope to establish that it corresponds exactly to any usual formal
counterpart;
3) most people (logicians and mathematicians) that I know claim that
they understand what is meant by "natural number" in both
senses 1 and 2. I, for one, do not share this optimism, on three different
grounds:
a) shifting the question to finite sets, I would not be surprised
if the same people would also admit that they understand what
finite sets are, since they would certainly accept that finite sets are
precisely the sets whose cardinals are natural numbers, but I
an unhappy with the fact that in order to prove that Dedekind-finite
implies finite one needs the axiom of choice; more importantly:
b) historically, natural numbers were not always thought of in
the same way as in the post-Dedekind era; Euler, for one, used
freely the idea of an infinite natural number (a number, we may say,
that is larger than any effectively or intuitively countable one),
an alien or non-standard natural number. Dedekind tried to rule them out
by means of his induction axiom (a theorem in ZF), as we know (see his
Letter to Keffersteen, in van Heijenoort, 98-103), but did he really do so?
Just imagine, if you will, the possibility that in the universe of sets,
all sets that contain 0 (or 1) and are closed under (set-theoretic)
successor also contain alien elements. Then the smallest such set,
N, must also contain such things.
c) going back to point 1, there is also the question of "which
theory of sets"? before 1976 I would not have thought of posing
this question with regard to this discussion, although, of course,
I knew of non-standard models of arithmetic, etc. But E. Nelson's
Internal Set Theory IST (a conservative extension of ZFC and a framework for
nonstandard analysis) shows that already in the set N
(the "same" N as in ZFC, but in which we can "see more" things, thanks
to the new primitive concept "x is standard", alongside
"belongs") there are nonstandard elements.
4) going back to C'sT, then, and supposing that the formalised notion
of TC in done inside IST and not ZF(C) - why not? - what, then, if
a programm that computes a numerical function is of infinite lenght,
or the function has a nonstandard number of arguments? Certainly
such a function should not count as EC, unless, of course, one
accepts the infinite natural numbers as equally intuitive as
the usual finite ones. But if this is the case, then I cannot think
of a reason to doubt C'sT and we are back to square one (or zero).
AJFO
A.J Franco de Oliveira
Departamento de Matemática - CLAV
Universidade de Évora
R. Romão Ramalho
7001 ÉVORA
francoli at mail.Eunet.pt
francoli at dmat.uevora.pt
More information about the FOM
mailing list