FOM: contradiction-free vs consistent
Raatikainen Panu A K
Praatikainen at Elo.Helsinki.FI
Wed Feb 17 10:07:03 EST 1999
In his reply to Tragesser, Simpson wrote:
>"In Robert's defense, it occurs to me that one could try to dispute
>G"odel's completeness theorem on Brouwerian grounds, because the
>models of T that are produced are not always `unique' or
>`mathematically specific' or `constructive' in various senses. For
>instance, even if we assume that T is recursively axiomatizable and
>consistent, then it is well known (Kleene) that there always exists
>a Delta^0_2 definable model of T, but there does not always exist a
>Delta^0_1 (i.e. recursive or computable) model of T. "
What I find in this case interesting is that every Delta^0_2 set is
still "constructive" (and only they are) in the sense that it can be
generated by "a trial and error machine" (see Putnam, JSL 1965); this
machine model is otherwise like Turing machine, exept that a machine
is given an integer, and the machine then prints out a finite sequence
of "yesses" and "nos"; the last "yes" or "no" is always to be the
correct answer. But one gives up the requirement that it is possible
to tell (effectively) if the computation has terminated.
This notion is in my mind highly natural (and constructive, I think),
and it is indeed the basis of so-called Formal Learning Theory. But
here its relevance is in the fact that every (axiomatizable)
consistent theory has a model that can be generated by a trial and
error procedure and is ( in that sense) constructible.
In think this point supports Simpson's initial critical observations
that precede the above-quoted "second thoughts".
By the way, I would be very interested in hearing comments and
opinions on the foundational and philosophical status of T&E
procedures in general.
Department of Philosophy
Universify of Helsinki
E-mail: panu.raatikainen at helsinki.fi
More information about the FOM