[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