[FOM] Hanf's conjectures on finite axiomatizability

Stephen G Simpson simpson at math.psu.edu
Fri Jul 9 10:33:00 EDT 2004

Santiago Bazerque writes:
 > 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.

Hanf later announced a proof of this.  I think Hanf never published a
proof, but this theorem and much more are proved in Peretyatkin's
book, which appeared in English translation a few years ago.

 > 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? :-)

I for one agree with you.  This work of Hanf and Peretyatkin ought to
be more widely known.

Hanf's method is quite interesting, involving tilings of the plane,
etc.  I think Peretyatkin's method is different, but I have not
studied it carefully.

How do Hanf's techniques show up in descriptive complexity?

-- Steve

More information about the FOM mailing list