[FOM] Simple historical question

[Richard Zach]

> A question which I suspect some of the historically knowledgeable 
> members of the list may be able to answer easily:
> 
> To whom should we rightly give first credit for the result/observation 
> that Th(N,0,S,+,*,<) is undecidable?

Assigning credit is always a tricky issue.  Of course, Church was the
first to prove that certain number-theoretical problems are recursively
unsolvable.  But for the full result you are asking about a number of
other things are important.  Bill Tait pointed out one: you need a
convincing analysis of computability and a proof that general
recursiveness (which Church used) is coextensive with computability
according to that analysis.  By most accounts, Turing gave such an
analysis.  But there are other things.  For one, I don't think anyone
(except perhaps Tarski, but if he did, I don't think he published it
then) talked or thought of theories in the sense required (set of
sentences in some signature true in a certain structure) in the 1930s or
maybe even in the 1940s.  This has partly to do with the notion of
"truth in a model" not being available at the time; "theory" in this
sense is not a concept used until later (I'm away from my books and
files, so I can't look up the references, but there's a paper by Vaught
on model theory before 1945 which would probably settle this).  Church
certainly didn't think about theories in this sense. At the very end of
the JSL paper he does talk about theories which "allow certain
comparatively simple methods of definition and proof" and states that
the Entscheidungsproblem for such theories is undecidable.  But by this
he means axiomatic theories such as Principia. The last sentence of his
paper reads, "In particular, if the system of Principia Mathematica be
\omega-consistent, its Entscheidungsproblem is unsolvable."  Now what is
one to make of the "if PM is \omega-consistent" if not that he wasn't
convinced that it is?  And how could he fail to be convinced of this
unless he didn't realize that the axioms of PM are true in the intended
interpretation?  Also note that the methods used by Goedel and Church
don't work unless you have a primitive recursive set of axioms, so you
couldn't use them directly to prove undecidability of Th(N) even if you
already understand what "the set of formulas true in N" is.

I think this is another instance of an implication which is easy/obvious
to us not being at all obvious to the people working when the concepts
in questions were first worked out.

I don't have an answer to the question "who first stated the result in
print" but I wouldn't be surprised if it wasn't until  Tarski,
Mostowski, Robinson, /Undecidable theories/ (1953).

-RZ