FOM: Re: FOM Church's Theory - an argument against(?)

[A.J. Franco de Oliveira]

 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