FOM: the blind spot about theory-completeness and categoricity

[Neil Tennant]

I have been researching the origins of logicians' grasp of the
concepts of theory-completeness and categoricity, and have uncovered
what I regard as an absolutely inexplicable "blind spot" that lasted,
roughly, from 1918 to 1933. I'd like to know from fellow fom-ers
whether they know of any literature that can throw light on the
conundrum.

The blind spot in question was the failure to realize that one would
not be able simultaneously to maximize deductive power (to achieve
theory-completeness) and expressive/descriptive power (to achieve
categoricity). Let us call this the Ineffability Theorem.

In 1910, Veblen and Young's first volume of Projective Geometry
clearly stated the concept of categoricity in a way that distinguishes
it from semantic theory-completeness. (There may well be even earlier
definitions of categoricity; but theirs will certainly do. And their
book was widely read.)

In his Habilitationsschrift of 1918, Bernays clearly stated the
completeness conjecture for finitary proof for first-order logic.  So
the subsequent collaboration with Hilbert, leading in due course to
Hilbert and Ackermann's Grundzuege in 1928, would certainly have been
informed by a grasp of the distinction between logical consequence and
deducibility, and between satisfiability and consistency.
(Here I am endebted to Wilfried Sieg, and to Bill Tait for suggesting
that I contact Wilfried.)

All one needs is the two *concepts* (1) completeness of a system of
finitary proof, and (2) categoricity of a set of sentences---and the
Ineffability Theorem follows easily. One does NOT need either a strong
completeness theorem or the compactness theorem. (For the technical
confirmation I am endebted to Harvey Friedman and Steve Simpson.)

In 1920 Skolem gave his improvement of Lowenheim's theorem, showing
that any model of a first-order theory would have a countable
elementary submodel.  Thus uncountable models could not be captured at
first-order, not even by a *complete* first-order theory.

So the suspicion should have been aroused that *maybe*, just *maybe*,
there could be countable models of Th(N) not isomorphic to N.

Yet as late as 1927, in his paper 'Eigentliche und uneigentliche
Begriffe', we find no lesser a figure than Carnap completely
conflating the properties of theory-completeness
(Entscheidungsdefinitheit) and categoricity (Monomorphie), maintaining
explicitly that they coincided. (I conclude that Carnap could not have
known, at this time, of Skolem's 1920 result.)

Only in 1927/28 did Tarski prove that the set of first-order sentences
Th(omega,<) has models of order-type omega+(omega*+omega).tau, tau any
order type.

Still, no-one pointed out that even if we could characterize the
complete theory Th(N), it would (or even: perhaps *could*) have
non-standard models.

Then in 1929 Godel proved the completeness and compactness of
first-order logic; and about a year later proved the incompleteness of
first-order arithmetic. 

In 1933-4, without appealing to Godel's compactness result, Skolem
proved the existence of non-standard models for Th(N).

In his 1935 review of Skolem's papers, Godel himself failed to point
out that the existence of non-standard models for any subtheory of
Th(N) would follow almost immediately from his own compactness theorem.
(Here I am grateful to Sol Feferman for mentioning Vaught's historical
note in the Godel Collected Works.)

Only much later does Malcev give the now standard argument, using
compactness, for the existence of non-standard models for arithmetic
(by introducing a new name a and laying down the infinitely many
inequalities ~a=k*, k* any numeral). 

What I called the Ineffability Theorem above can be proved by the same
kind of argument, and can be generalized to any countable intended
model all of whose elements is definable. The result is: if M is such
a model, there is no complete and categorical subtheory of Th(M).

Note that the ineffability theorem is indifferent to whether one uses
a first-order language or a higher-order language; and can be
established without knowing that first-order logic is complete, and
without knowing that second-order logic is incomplete.

What I would dearly like to know is whether this "blind spot" was
genuine and widespread, or whether there was *any* logician publishing
at that time, no matter how little-known or in how remote a place, who
said or published anything during the years 1918-1933 that could be
taken as evidence of a suspicion that theory-completeness and categoricity
could not simultaneously be achieved (no matter what logic and
language one used).

Neil Tennant

PS For those who might be interested, my paper on this topic is
nearing completion, and I would be most interested in having feedback.
I can't turn it into a downloadable file without considerable and
aggravating effort. So if you send me your snail mail address (to
tennant.9 at osu.edu) I shall send you hard copy when the paper is ready.
Those with whom I have already been corresponding and to whom a copy
has been promised need not reply! The current, tentative title is
'Mathematics: Intuition and Structure'. As you will be able to tell
from the above acknowledgements, I really do not think this paper
would have come about without the stimulation and resources provided
by fom. So season's greetings, tinged with gratitude, to Steve, for
getting it all going!