1
$\begingroup$

Suppose $\mathcal{M}$ is an infinite structure which has the property that every type that is realised is realised uniquely. Also assume that every element of $\mathcal{M}$ is definable but there is no single constant bounding the quantifier depth of the defining formulae.

Q1)When does $Th(\mathcal{M})$ admit quantifier elimination?

Q2) When is $Th(\mathcal{M})$ decidable?

$\endgroup$
8
  • $\begingroup$ Hi, regarding "every element of $\mathcal{M}$ is definable but there is no single constant bounding the quantifier depth of the defining formulae" -- do you have an example of such an $\mathcal M$"? $\endgroup$ Mar 8, 2014 at 5:00
  • 1
    $\begingroup$ How about a pointwise definable model of ZFC? (projecteuclid.org/…) $\endgroup$ Mar 8, 2014 at 5:50
  • $\begingroup$ That's good, how about a decidable example... $\endgroup$ Mar 8, 2014 at 6:24
  • $\begingroup$ Not sure this works, but: how about a disjoint union of a bunch of finite graphs $G_n$ (with each $G_n$ "attached" to an element of a disjoint copy of $\mathbb{N}$, just so we effectively have predicates for each $G_n$), where each $G_n$ has every element definable in at most $n$ many quantifiers? Something like that might have a decent chance of being decidable, if the $G_n$s are chosen carefully. $\endgroup$ Mar 8, 2014 at 6:51
  • 1
    $\begingroup$ Come think of it, “there is no single constant bounding the quantifier depth of the defining formulae” trivially implies that there is no bound on the complexity of formulas up to equivalence in $\mathrm{Th}(\mathcal M)$, hence the answer to Q1 is never. $\endgroup$ Mar 8, 2014 at 14:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.