FOM: Re: finite axiomatization and conservative...

A.P. Hazen a.hazen at
Tue May 1 01:52:21 EDT 2001

Neil Tennant asks two questions:
(1) Who showed that
	Any r.e. first order theory is the restriction to its language of a
		          finitely axiomatizable theory.  ?
<<<This is sort of a converse to Craig's Theorem, that the restriction to a
sublanguage of any axiomatized system has a, perhaps non-finite,
axiomatization IN the sublanguage.>>> Kleene, "Finite axiomatizability of
theories in the predicate calculus using additional predicate symbols,"
published as (the second of) his "Two Papers on the Predicate Calculus" (=
Memoirs of the American Mathematical Society, #10), 1952.
(2) Do any interesting restrictions on the theory to be recovered force the
finitely axiomatized theory to be higher order?
   No, the construction is very general.  (Simplified argument sketch.
Assume the theory you want to recover has only infinite models.  Add enough
new predicates to allow yourself to interpret, say, Robinson Arithmetic.
Now add a description of the recursive enumeration of the sentences of the
theory to be recovered, using your favorite Gödel-numbering for Turing
machines.  Now add "reflection" machinery allowing you  to say that if a
sentence is generated by the enumerator, then THAT SENTENCE.)
   (Kleene refers to Craig, and was perhaps inspired by his work. Note that
the Craig's "official" theorem-- what I gave above is the "philosophy of
science" version about doing without theoretical terms-- is: any r.e.
theory is recursively axiomatizable in first-order logic (shown by a
construction that doesn't add to the language).  Kleene's theorem
strengthens this by changing "recursive" to "finite," but has to accept new
Allen Hazen
Philosophy Department
University of Melbourne
(interested in logic, logical metaphysics, philosophy of mathematics, etc.)

More information about the FOM mailing list