4
$\begingroup$

In order to prove (the non trivial part of) Chang-Los-Suszko's theorem [1], I'm struggling with the following lemma :

Lemma. Let $T$ be a $\mathcal L$-theory and $T_{\forall\exists}$ the set of $\forall\exists$-sentences consequences of $T$. Then for every model $\mathfrak M \models T_{\forall\exists}$, there exists $\mathfrak N \models T$ such that $\mathfrak M \subseteq \mathfrak N$ and where the inclusion is essentially closed.

I recall here that an inclusion $\mathfrak M \subseteq \mathfrak N$ is essentially closed if for every quantifier-free formula $\varphi(\bar x, \bar y)$, and for every tuple $\bar m$ of elements of $M$, one has $$ \mathfrak N \models \exists \bar x \varphi(\bar x,\bar m) \quad \text{implies} \quad \mathfrak M \models \exists \bar x \varphi(\bar x,\bar m) .$$

My thought was to get $\mathfrak N$ by showing that the $\mathcal L_M$-theory $$ T \cup \Delta(\mathfrak M) \cup \{ (\exists \bar x\varphi(\bar x,\bar m)) \to \varphi(\bar a_{\varphi(\bar x, \bar m)},\bar m) : \varphi \ \text{quantifier-free}, \bar m \in M \} $$ is consistent, where $\Delta(\mathfrak M)$ is the simple diagram of $\mathfrak M$, and where $\bar a_{\varphi(\bar x, \bar m)}$ is a choice of a tuple of elements of $M$ such that $\mathfrak M \models \varphi(\bar a_{\varphi(\bar x,\bar m)},\bar m)$ if it exists and else is arbitrary. And to do so, of course I would use compactness and only show that the $$ T \cup \{ \psi(\bar m) \wedge \bigwedge_{i=1}^n\left((\exists \bar x\varphi_i(\bar x,\bar m_i)) \to \varphi(\bar a_{\varphi(\bar x, \bar m_i)},\bar m_i) \right)\} $$ are consistent (with $\psi$ and the $\varphi_i$ quantifier-free). Here I'm kind of stuck…

I want to express the latter formula (between the braces) as some $\exists \bar z \forall \bar t \chi(\bar z,\bar t)$ with $\chi$ quantifier-free : then $\mathfrak M$ will satisfy it and so prevent $T$ from showing its negation, yielding a model $\mathfrak N$ of $T$ satisfying $\exists \bar z \forall \bar t \chi(\bar z,\bar t)$. CQFD.

It does not seem far from reach but I just can't compute that $\chi$. I hope someone can give me a hint (or tell me that I'm completely off).


[1] For those who wonder, Chang-Los-Suszko's theorem states that a theory $T$ is inductive (i.e. its class of models is closed under taking increasing union) if and only if $T$ admits a $\forall\exists$-axiomatization.

$\endgroup$
4
$\begingroup$

Hint: Let's slightly modify the construction. Show that $$T \cup \Delta(M) \cup \{\forall x \phi(x, \bar m) : M \models \forall x \phi(x, \bar m), \phi \text { quantifier free}\}$$ is consistent.

$\endgroup$
  • $\begingroup$ Thanks, I think I got it now. Just to be sure, can you check it ? Should one make conjunctions, one can assume a finite fragment of your theory to be included in $T \cup \{\psi(\bar m') \wedge \forall \bar x \varphi(\bar x,\bar m)$ with $M$ a model of the latter formula. Then $M \models \exists \bar y \, \bar y' \forall \bar x (\psi(\bar y') \wedge \varphi(\bar x, \bar y))$, preventing $\forall \bar y \, \bar y' \exists \bar x (\neg \psi(\bar y') \vee \neg \varphi(\bar x, \bar y))$ to be consequence of $T$, so there is a model of our finite fragment. […] $\endgroup$ – Pece Feb 4 '14 at 18:07
  • $\begingroup$ […] Hence there is a model of your theory and such a model $N$ contains $M$ as a substructure (because model $\Delta(M)$) and if $N \models \exists \bar x \varphi(\bar x, \bar m)$ then $N \not \models \forall \bar x \neg \varphi(\bar x, \bar m)$ and so necessarily $M \not \models \forall \bar x \neg \varphi(\bar x, \bar m)$ either (by the latter part of your theory). Which conclude that $N$ is an eventually closed extension of $M$. $\endgroup$ – Pece Feb 4 '14 at 18:10
  • $\begingroup$ That is exactly how you proceed. $\endgroup$ – Levon Haykazyan Feb 4 '14 at 18:17
  • $\begingroup$ Ok, so my mistake was to force a witness in $M$ for every witness in $N$, while you make sure there is no witness in $N$ when there is no in $M$. Thank you again. $\endgroup$ – Pece Feb 4 '14 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.