2
$\begingroup$

Setting

Definition: A theory $\pmb{T}$ has a $\forall\exists$-axiomatization if it can be axiomatized by sentences of the form $$\forall v_1\ldots \forall v_n \exists w_1 \ldots \exists w_n ~~ \phi(\bar{v},\bar{w})$$ where $\phi$ is a quantifier free $\mathcal{L}$-formula.

I am doing a multi-step proof to show $T$ has $\forall\exists$-axiomatization.

Step one: suppose whenever $(\mathcal{M}_i : i \in \mathbb{I})$ is a chain of models of $\pmb{T}$, then I showed that: $$\mathcal{M} = \bigcup \mathcal{M}_i \models \pmb{T}.$$

Looking ahead: Now I am showing the converse also holds. Suppose whenever $(\mathcal{M}_i, i \in \mathbb{I})$ is a chain of models of T, then $\bigcup \mathcal{M}_i$ is a model of T. Let $\Gamma = \{ \phi : \phi \text{ is a $\forall\exists$-sentence and $\pmb{T} \models \phi$}\}$. Let $\mathcal{M} \models \Gamma$. I will show $\mathcal{M} \models T$.

Step two: Now I want to show that there is $\mathcal{N} \models \pmb{T}$ such that if $\psi$ is an $\exists\forall$-sentence and $\mathcal{M} \models \psi$, then $\mathcal{N} \models \psi$.

My Attempt at step two

We construct the theory $\pmb{T}^{*} = diag_{\forall}(\mathcal{M}) \cup \pmb{T}$, where $diag_{\forall}$ is the set of for all sentences satisfied by $\mathcal{M}$. If $\pmb{T}^{*}$ is satisfiable then let $\mathcal{N} \models \pmb{T}^{*}$.

Now we show $\pmb{T}^{*}$ is consistent. By compactness, it suffices show some finite subset of $\pmb{T}^{*}$ is satisfiable. Let $\pmb{T}^{*'} = diag_{\forall}' \cup \pmb{T}'$, where $diag_{\forall}'$ and $\pmb{T}'$ are finite subsets of $diag_{\forall}$ and $\pmb{T}$. Next let: $$\gamma = \forall \bar{v} \exists \bar{w} \phi(\bar{v},\bar{w}) \in \pmb{T}', \quad \theta = \forall \bar{x} \rho(\bar{x}) \in diag_{\forall}'.$$

Since $\pmb{T}$ is consistent, we can assume $\mathcal{N} \models \pmb{T}$, therefore $\mathcal{N} \models \gamma(\bar{a},\bar{b})$ for some $\bar{a},\bar{b} \in \mathbb{N}$. Now we show for each $\theta \in diag_{\forall}'$:

$$\mathcal{N} \models \gamma \Rightarrow \mathcal{N} \models \theta.$$

So we have:

$$\mathcal{N} \models \gamma ~~\Rightarrow~~ \mathcal{N} \models \forall \bar{v} \exists \bar{w} \phi(\bar{v},\bar{w}) ~~\Rightarrow~~ \mathcal{N} \models \forall \bar{v} \phi(\bar{v},\bar{b}) ~~~ \text{for some } \bar{b} \in \mathbb{N} ~~\Rightarrow~~\\ \mathcal{N} \models \forall \bar{x} \rho(\bar{x}) ~~\Rightarrow~~ \mathcal{N} \models \theta.$$

Where we simply renamed $\phi$ as $\rho$ and $\bar{v}$ as $\bar{x}$. Thus each $\pmb{T}^{*'}$ is consistent so $\pmb{T}^{*}$ is consistent, so $\mathcal{N} \models \pmb{T}^{*}$.

Next we show if $\mathcal{N} \models \pmb{T}$ and $\mathcal{M} \models \psi$, then $\mathcal{N} \models \psi$. Let $\psi = \exists \bar{v} \forall \bar{w} \sigma(\bar{v},\bar{w})$ where $\sigma$ is quantifier free. Then: $$\mathcal{M} \models \exists \bar{v} \forall \bar{w} \sigma(\bar{v},\bar{w}) ~~\Rightarrow~~ \mathcal{M} \models \forall \bar{w} \sigma(\bar{a},\bar{w}) \text{ for some } \bar{a} \in \mathbb{M}.$$

And since $\mathcal{N} \models diag_{\forall}(\mathcal{M})$, we have:

$$\mathcal{N} \models \forall \bar{w} \sigma (\bar{a},\bar{w}) ~~\Rightarrow~~ \mathcal{N} \models \exists \bar{v} \forall \bar{w} \sigma (\bar{v},\bar{w}) ~~\Rightarrow~~ \mathcal{N} \models \psi.$$

My Problem

  1. I let $\mathcal{N} \models \pmb{T}$ by assumption, using the fact that $\pmb{T}$ is consistent. Is this justified and proper in this context?

  2. When unraveling the implication of $\mathcal{N} \models \gamma$ , is it correct to evaluate it at some $\bar{b} \in \mathbb{N}$?

$\endgroup$
  • 1
    $\begingroup$ Question 2. If you are assuming that $\sf T$ has a $\forall\exists$-axiomatization, what is the purpose of the sentence beginning "Furthermore"? It seems redundant because, if the theory $\sf T$ ha a $\forall\exists$-axiomatization, then it follows that the union of a chain of models of $\sf T$ is a model of $\sf T$. $\endgroup$ – bof Feb 19 '15 at 6:01
  • $\begingroup$ @CarlMummert I edited the question to make it more clear $\endgroup$ – chibro2 Feb 19 '15 at 13:38
  • $\begingroup$ Also please consider this question: math.stackexchange.com/questions/1155575/…. It is a lot less ambiguous (in my mind) and may be a better use of your time $\endgroup$ – chibro2 Feb 19 '15 at 13:40
  • $\begingroup$ I am currently working on the same problem. From Marker, no? Anyway, your solution looks deeply flawed to me. For instance, why take $diag_\forall(M)$ instead of $diag_{\exists\forall}(M)$, as those are the sentences you care about? (This is also bad notation, diagram is supposed to mean the theory in the expanded language with names for each constant.) Then you incorrectly "Unravel the implication" (although you appear to be aware of this fact). Then, you derive that because $\mathcal{N}$ satisfies some $\forall$ sentence, then it works for all $\theta$?$\theta$ was supposed to be arbitrary! $\endgroup$ – James Feb 20 '15 at 2:47
  • $\begingroup$ Yup it's from Marker. And Yes! I had a discussion about $diag_{\forall\exists}$ vs $diag_{\forall}$ but could not decide on which. Please suggest a better proof when you come upon one! $\endgroup$ – chibro2 Feb 20 '15 at 3:11
1
$\begingroup$

Here is my attempt. Fix a theory $T$, let $\Gamma = \{\phi \ : \ \phi \in \Pi_2 \cap Cl(T)\}$, suppose $M\models \Gamma$. Then $T$ is consistent, as, otherwise $M\models \forall x \exists y (x\neq x)$.

Let $S = \Sigma_2 \cap Th(M)$. We want to show that $T \cup S$ is consistent. It suffices to show that $T \cup \Delta$ is consistent, for every finite $\Delta \subseteq S$. Write $$\Delta = \{\phi_1,\ldots,\phi_n\} = \{\exists \bar{x}\forall\bar{y}\psi_1(\bar{x},\bar{y}),\ldots, \exists \bar{x}\forall\bar{y}\psi_n(\bar{x},\bar{y})\}$$ Where $\psi_i$ are quantifier free. If $T\cup \Delta$ is consistent, we are done, otherwise $$ T \models \bigwedge_{i\leq n} \phi_i \rightarrow \bot $$ So $T \models \bigvee \neg \phi_i$, more explicitly $T\models \bigvee \forall \bar{x} \exists \bar{y} \neg \psi_i(\bar{x},\bar{y})$. Hence $T\models\forall \bar{x} \exists \bar{y} \bigvee \neg \psi_i(\bar{x},\bar{y})$. This last sentence is a $\Pi_2$ consequence of $T$, hence, it $M$ is a model for it. Therefore $M\models \forall \bar{x} \bigvee \neg \forall \bar{y} \psi_i$, so finally $M \models \neg \exists \bar{x} \bigwedge \forall \bar{y} \psi_i$.

However $M\models \bigwedge \phi_i$ so $M\models \bigwedge\exists \bar{x} \forall \bar{y} \psi_i(\bar{x},\bar{y})$,

Edit, the following is incorrect: thus $M \models \exists\bar{x} \bigwedge \forall \bar{y}\psi_i(\bar{x},\bar{y})$, but this contradicts the last paragraph.

This establishes that $T \cup S$ is consistent.


So at this point I am not sure how to proceed. I will leave this here in case I want to edit it later.

$\endgroup$
  • $\begingroup$ I'm sorry can I ask you what $\Pi_2$ and $Cl(T)$ are? $\endgroup$ – chibro2 Feb 20 '15 at 14:15
  • $\begingroup$ $\Pi_2$ is the collection of sentences starting $\forall \bar{x} \exists \bar{y} \psi$, where $\psi$ is quantifier free. In general $\Pi_n$ means starting with $\forall$, and then $n$ total quantifier alternations $\forall\exists\forall\cdots$ ect. $\Sigma_n$ is its counterpart, starting with $\exists$ and then $n$ quantifier alternations. $CL(T)$ is the deductive closure of $T$. $\endgroup$ – James Feb 20 '15 at 15:06
  • $\begingroup$ It's the same definition of $\Gamma$ in the book, it's just more brief. $\endgroup$ – James Feb 20 '15 at 15:09
  • $\begingroup$ @chibro2 see the edit. $\endgroup$ – James Feb 20 '15 at 18:05
1
$\begingroup$

I know this is 2 years later, but I am working through the same problem, and see nothing wrong with taking James' approach, with some small clarifications by removing unnecessary conjunctions. Let $\mbox{Th}_{\exists\forall}(\mathcal{M})$ be the set $S$ that James defined.

We need to show that $T\cup\mbox{Th}_{\exists\forall}(\mathcal{M})$ is consistent. This is false iff there exists a $\exists\forall$ sentence $\exists\overline{x}\forall\overline{y}\phi(\overline{x},\overline{y})$ in $\mbox{Th}_{\exists\forall}(\mathcal{M})$ where $\phi$ is quantifier free such that $T\models\forall\overline{x}\exists\overline{y}\neg\phi(\overline{x},\overline{y})$. But this implies $\forall\overline{x}\exists\overline{y}\neg\phi(\overline{x},\overline{y})\in\Gamma$ and thus $\mathcal{M}\models\forall\overline{x}\exists\overline{y}\neg\phi(\overline{x},\overline{y})$ . But $\forall\overline{x}\exists\overline{y}\neg\phi(\overline{x},\overline{y})$ is the negation of $\exists\overline{x}\forall\overline{y}\phi(\overline{x},\overline{y})$ , contradicting the fact that $\exists\overline{x}\forall\overline{y}\phi(\overline{x},\overline{y})\in\mbox{Th}(\mathcal{M})$ . $\square$

$\endgroup$

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.