1
$\begingroup$

I found this example in "A Course in Model Theory", but don't seem to figure out why it is true.

Let $L$ be a language having a unary predicate $P_s$ for each (finite) binary string $s \in \{0,1\}^*$ and let $Tree$ be the theory saying that the $P_s$ form a binary decomposition of the universe. That is, for every binary string $s\in\{0,1\}^*$ the theory $Tree$ contains the sentences:

$\forall x P_{\langle\rangle}(x)$

$\exists x P_s(x)$

$\forall x ((P_{s0} (x) \vee P_{s1} (x)) \iff P_s (x))$

$\forall x \neg(P_{s0}(x) \wedge P_{s1} (x))$

Show that $Tree$ has quantifier elimination and that $Tree$ is complete.

$\endgroup$
2
  • 2
    $\begingroup$ Do you have any thoughts on this problem why it hold? Is there any method you think should be applied here? $\endgroup$
    – Ove Ahlman
    Apr 20, 2016 at 9:52
  • $\begingroup$ In the same spirit as Ove's comment, have you seen a proof of quantifier elimination for any theory? What was the strategy in that proof, and where do you have trouble applying it in this case? $\endgroup$
    – Alex Kruckman
    Apr 22, 2016 at 0:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .