[FOM] Hanf's conjectures on finite axiomatizability

Santiago Bazerque sbazerque at fibertel.com.ar
Wed Jul 14 22:01:06 EDT 2004


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

Well, I was refering to the lemma concerning proofs of elementary
equivalence by way of counting isomorphism types of spheres of finite
radius, that I belive was presented in that paper and is now known under
the name of "Hanf's theorem". Since membership to most complexity
classes has been shown to be equivalent to query-expressibility in some
logic, the previous result on the locality of first order properties is
sometimes useful, I belive.

Most books using this lemma give credit to Hanf's 1965 paper (for
example, Neil Immerman's "Descriptive complexity", pp 100-103).

regards,
Santiago



More information about the FOM mailing list