[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?
Yes.
> 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