1
$\begingroup$

Statement: Let $\Sigma = \{\phi_i\}_{i\in\omega}$ a sequence of formulas such that $\phi_{i+1}\models\phi_i$ for every $i$. Suppose that there exists a closed formula $\theta$ such that for every model $\mathcal{M}$ we have $\mathcal{M}\models\Sigma$ if and only if $\mathcal{M}\models\theta$. Show that there exists $n$ such that $\models\phi_{n+1}\Leftrightarrow \phi_n$.

I tried to suppose that such $n$ did not exist but I couldn't get to a contradiction, because I do not know how to relate $\theta$ to the equivalence I have to show. Any hint will be appreciated.

$\endgroup$
2
$\begingroup$

Hint: Apply the compactness theorem to $\Sigma \models \theta$.

What you know about $\theta$ is that $\Sigma \models \theta$ (and conversely), hence there is some finite subset $\Gamma \subset \Sigma$ with $\Gamma \models \theta$. But $\Gamma = \{\phi_{i_1}, \dots, \phi_{i_k}\}$ and since for all $i \in \omega$ we have $\phi_{i+1} \models \phi_{i}$, it holds that $\phi_n \models \Gamma$, where $n = \max(i_1, \dots i_k)$. Hence $\phi_n \models \Gamma \models \theta \models \Sigma \models \phi_{n+1}$ and so $\models \phi_n \Leftrightarrow \phi_{n+1}$.

$\endgroup$
  • $\begingroup$ Better than my A. Yours appeared while I was typing mine. $\endgroup$ – DanielWainfleet Apr 21 '17 at 14:42
0
$\begingroup$

(1). If $\neg \theta$ has no model then every model satisfies $\theta$ and hence satisfies $\phi_n$ and $\phi_{n+1}$ for every $n$.

(2). If $\neg \theta$ has a model: Note that every model satisfies $\phi_n\implies \land_{i\leq n}\phi_j$ for every $n.$

Suppose by contradiction that,for every $n,$ that $\neg (\phi_{n+1} \iff \phi_n)$ has a model $M_n.$ Then $M_n$ can't satisfy $\phi_{n+1}$ (else $M_n$ also satisfies $\phi_n$). So $M_n$ satisfies $(\neg \phi_{n+1})\land \phi_n.$

Hence $M_n$ satisfies every member of $F_n=\{\neg \theta\}\cup \{\phi_j:j\leq n\}$ (because if $M_n$ satisfied $\theta$ it would satisfy $\Sigma.$)

Now consider $F=\cup_{n\in \omega}F_n.$ Any finite subset of $F$ is a subset of $F_n$ for some $n,$ and $F_n$ has a model ($M_n$). By the Compactness Theorem, therefore $F$ has a model $M.$ But $M$ satisfies $\Sigma$ and $M$ does not satisfy $\theta,$ contrary to hypothesis.

So the supposition is paradoxical, so there must exist $n$ such that $\neg (\phi_{n+1}\iff \phi_n)$ has no model.

$\endgroup$

Your Answer

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