3
$\begingroup$

This note comes in my lecture notes after the Löwenheim-Skolem Theorem and a remark on the equivalence of "$\Gamma \subseteq \text{Sent}(\mathcal{L})$ is strongly maximal consistent (i.e. for any $\psi\in\text{Sent}(\mathcal{L})$, then $\psi\in\Gamma$ or $\neg\psi\in\Gamma$)" and "$\Gamma = \text{Th}(\mathcal{A})$ for some $\mathcal{L}$-structure $\mathcal{A}$". Where $\mathcal{L}$ is a first order predicate language and $\text{Th}(\mathcal{A}):=\{\varphi \in \text{Sent}(\mathcal{L})|\mathcal{A}\models\varphi\}$.

I define $\Gamma$ to be maximal consistent if it is consistent and for any $\psi\in\text{Sent}(\mathcal{L})$, we have $\Gamma\vdash\psi$ or $\Gamma\vdash\neg\psi$.

Now, to come back to the question, I see the forward direction, using the fact that $\text{Th}(\mathcal{A})$ is maximal consistent, so if $\mathcal{A}$ and $\mathcal{B}$ are models for $\Gamma$, then $\Gamma\subseteq \text{Th}(\mathcal{A})\cap\text{Th}(\mathcal{B})$ implies equality.

For the backwards direction I already have the maximal consistency of $\text{Th}(\mathcal{A})$, which is a set of sentences independent from the choice of model $\mathcal{A}$ for $\Gamma$, but $\Gamma\subseteq\text{Th}(\mathcal{A})$, and here I stop.

$\endgroup$
  • 2
    $\begingroup$ What does "strongly" maximal consistent mean? $\endgroup$ – Alex Kruckman Apr 6 at 14:47
  • $\begingroup$ Hi Alex, I thought it was a standard definition, just added. $\endgroup$ – Davide Apr 7 at 10:05
2
$\begingroup$

Call $\Gamma\subseteq\mathrm{Sent}(\mathcal L)$ complete if for every $\phi\in\mathrm{Sent}(\mathcal L)$: $\phi\in\Gamma$ or $\neg\phi\in\Gamma$.

We can then show that if $\mathfrak A\models\Gamma$ for a complete set of sentences $\Gamma$, then $\Gamma=\mathrm{Th}(\mathfrak A)$. For this, note first that as $\mathfrak A\models\Gamma$, we have $\Gamma\subseteq\mathrm{Th}(\mathfrak A)$. Now, let $\phi\not\in\Gamma$. Then, as $\Gamma$ is complete, we have $\neg\phi\in\Gamma$. Thus, $\mathfrak{A}\models\neg\phi$ and thus $\phi\not\in\mathrm{Th}(\mathfrak A)$.

Trivially, if $\Gamma=\mathrm{Th}(\mathfrak A)$, then $\Gamma$ is a complete theory as $\mathrm{Th}(\mathfrak A)$ is.


We can use this to now show another nice result about completeness of theories. For this, call $\Gamma\subseteq\mathrm{Sent}(\mathcal L)$ a theory if $\Gamma\models\phi$ implies $\phi\in\Gamma$ for any $\phi\in\mathrm{Sent}(\mathcal L)$.

Let $\Gamma$ be a satisfiable theory, then

$$\Gamma\text{ is complete iff all models are elementary equivalent}$$


For the direction from left to right, assume that $\Gamma$ is complete and let $\mathfrak A,\mathfrak B$ be two models of $\Gamma$. By the first paragraph, $\mathrm{Th}(\mathfrak A)=\Gamma=\mathrm{Th}(\mathfrak B)$ and thus $\mathfrak A\equiv\mathfrak B$.

For the direction from right to left, assume that all models of $\Gamma$ are elementary equivalent. Suppose that $\phi\not\in\Gamma$ for some $\phi\in\mathrm{Sent}(\mathcal L)$. Then, as $\Gamma$ is a theory, $\Gamma\not\models\phi$ and thus there is a structure $\mathfrak A$ such that $\mathfrak A\models\Gamma$ and $\mathfrak A\not\models\phi$. But now, for any $\mathfrak B\models\Gamma$, as $\mathfrak A\equiv\mathfrak B$, we have also $\mathfrak B\models\neg\phi$. Thus, $\Gamma\models\neg\phi$ and as $\Gamma$ is a theory, we have $\neg\phi\in\Gamma$.

$\endgroup$
  • $\begingroup$ Thanks @blub, that's a very clear answer. But I was in particular trying to prove the statement in your 2nd paragraph but with $\Gamma$ being maximal consistent (i.e. $\Gamma$ is consistent and for any $\psi\in\text{Sent}(\mathcal{L})$, then $\Gamma\vdash\psi$ or $\Gamma\vdash\neg\psi$). But I think the completeness you define is a stronger condition? (indeed, that's what I define as strong maximal consistency) $\endgroup$ – Davide Apr 7 at 10:00
  • $\begingroup$ @Davide If you want to consider a set $\Gamma$ with $\Gamma\vdash\psi$ or $\Gamma\vdash\neg\psi$ for any sentence $\psi$, you can take my argument up there applied to the deductive closure of $\Gamma$, that is $\Gamma^\vdash:=\{\phi\in\mathrm{Sent}(\mathcal L)\mid\Gamma\vdash\phi\}$. $\endgroup$ – blub Apr 7 at 10:06
  • $\begingroup$ I am not sure I see your point. The condition for $\Gamma$ to be both deductively closed and complete is still stronger than being maximal. So your proof would show that if all models are elementarily equivalent, then $\Gamma$ is maximal consistent, but I'm not sure about the other way around. $\endgroup$ – Davide Apr 7 at 10:16
  • 1
    $\begingroup$ @Davide I think you are using maximal in a non-standard sense. Normally, you refer to a set of formulae as maximal if there is no proper superset with some property. $\endgroup$ – blub Apr 7 at 10:17

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.