FOM: From philosophy to `applied' model theory

urquhart@cs.toronto.edu urquhart at cs.toronto.edu
Wed Jun 28 16:10:54 EDT 2000


This is a brief follow-up to Steve Simpson's posting in
which he raises some questions about "axioms of infinity."
Church's "Introduction to Mathematical Logic" does contain
a section (Section 57 in the chapter on Second-Order Logic) that
is entitled "Axiom of infinity."  It discusses the general
definition of axioms of infinity, and observes that it follows
from work of Mostowski 1938 and Trachtenbrot 1950 that there
is no weakest axiom of infinity.  This is a corollary of Trachtenbrot's
1950 result that the decision problem for satisfiability in finite
models is unsolvable.

The literature on decidable prefix classes contains implicitly 
a lot of material on axioms of infinity.  In particular, the key
step in Goldfarb's proof that the Goedel class with identity is
unsolvable is the construction of an axiom of infinity 
(JSL Vol. 49, pp. 1237-1252).  However, I haven't been able to
find any kind of result such as that conjectured by Steve to 
the effect that "any finitely axiomatizable theory with only
infinite models must interpret one of a small finite number of such
theories."  Somehow, this picture seems too optimistic to me,
although it does not appear to be completely ruled out by Trachtenbrot's
result.  Does anyone know anything about this?

--Alasdair






More information about the FOM mailing list