[FOM] Hanf's conjectures on finite axiomatizability
Santiago Bazerque
sbazerque at fibertel.com.ar
Thu Jul 8 18:37:01 EDT 2004
In his 1965 paper "Model-Theoretic methods in the study of elementary
logic" Hanf raises the following question:
Does there exist a finitely axiomatizable undecidable theory with
countably many complete extensions?
Conjecture I. Every axiomatizable theory is isomorphic to a finitely
axiomatizable theory.
Conjecture II. Every finitely axiomatizable theory with countably many
complete extensions is isomorphic to a finitely axiomatizable theory
formulated with a finite number of unary predicates.
He points out that Conjecture I implies a positive answer and conjecture
II a negative answer to the problem given above. Hanf is considering
purely relational first order theories, and defines theories T,K to be
isomorphic iff there exists a recursive one-to-one function mapping the
sentences of T to those of K that preserves implications valid in each
theory.
I couldn't find an answer to Hanf's question, has it remained an open
problem all along from 1965?
regards,
Santiago Bazerque
ps. Even though the techniques developed by Hanf in this paper seem to
be well known in the realm of descriptive complexity, I feel that the
main results (i.e. the existence of a consistent, decidable theory which
cannot be shown to be consistent in Peano Arithmetic; the fact that
there exists a fintely axiomatizable, decidable theory H such that for
any axiomatizable theory T, the disjoint union of T and H is recursively
isomorphic to a finitely axiomatizable theory F) are not quite as
popular as perhaps they diserve to be. Is this just a newcomer's wrong
impression? :-)
pps. The proper reference is W. Hanf, "Model-Theoretic methods in the
study of elementary logic", in Addison, Henkin and Tarski, eds. "The
theory of models", 1965, North Holland, 105-135.
More information about the FOM
mailing list