What does "not entails" mean

Question

Suppose we have the following assumption: $$ A \models T \iff A \not\models Q $$

where $A$ is a structure, and $T$ and $Q$ are theories. (We have a fixed language $L$.)

First of all, I do not understand what $A \not\models Q$ means. Second, I do not understand what the given assumption means.

Any help is appreciated.

Answer 1

"$\not\models$" is just the opposite of "$\models$." In particular, for a structure $\mathcal{A}$ and a sentence $\varphi$ the following are equivalent:

• $\mathcal{A}\not\models\varphi$.

• It is not the case that $\mathcal{A}\models\varphi$. (This is the definition of "$\not\models$.")

• $\mathcal{A}\models\neg\varphi$. (This is a result which requires proof, but it's immediate from the definition of truth - the "$\neg$" clause in particular.)

---

When we look at theories instead of individual sentences, we have to be a bit careful. "$\mathcal{A}\models T$" means "For every $\varphi\in T$, we have $\mathcal{A}\models\varphi$." Again "$\not\models$" is defined as the opposite of "$\models$" in this context, and so we have $$\mathcal{A}\not\models T\quad\iff\quad\mbox{For some $\varphi\in T$ we have $\mathcal{A}\not\models\varphi$.}$$ Notice the "for some" instead of "for all" - when we write "$\mathcal{A}\not\models T$," we do not mean that $\mathcal{A}\models\neg\varphi$ for every $\varphi\in T$.

---

So in particular, your specific example translates to:

$(*)\quad$ $\mathcal{A}$ satisfies every sentence in $T$ iff there is some sentence in $Q$ which $\mathcal{A}$ does not satisfy.

Here "satisfy" is the natural-language translation of "$\models$" - "$\mathcal{A}\models\varphi$" is read as "$\mathcal{A}$ satisfies $\varphi$." For example, fix a sentence $\varphi$ and let $T=\{\varphi\}, Q=\{\neg\varphi\}$. Then indeed a structure satisfies $T$ (= satisfies every sentence in $T$) iff it does not satisfy $Q$ (= fails to satisfy some sentence in $Q$).

The property $(*)$ can be intuitively rephrased as saying that $T$ and $Q$ are "complementary" in the sense that every structure satisfies exactly one of $T$ or $Q$.

---

Let me finish on a slightly technical note.

We may reasonably ask when we actually run into this situation. The "silly" example I gave above clearly qualifies, but are there any other times this happens?

Interestingly, the silly example is essentially the only way this situation can arise: if $T$ and $Q$ satisfy $(*)$, then both $T$ and $Q$ are finitely axiomatizable. Finite axiomatizability is the same as axiomatizability by a single sentence (just take the conjunction of the finitely many axioms), so if $T$ and $Q$ satisfy $(*)$ there are individual sentences $\tau,\rho$ such that the models of $\tau$ are exactly the models of $T$ and the models of $\rho$ are exactly the models of $Q$. But then by $(*)$ we have in fact $\rho\equiv\neg\tau$. So $T$ "is" just $\{\tau\}$ and $Q$ "is" just $\{\neg\tau\}$.

The finite axiomatizability of any theories satisfying $(*)$ is a consequence of the compactness theorem. Specifically, suppose $T$ and $Q$ satisfy $(*)$; there must be finite $X\subseteq T, Y\subseteq Q$ such that $X\cup Y$ is unsatisfiable since otherwise by compactness $T\cup Q$ would be satisfiable, contradicting $(*)$.

So let $X\subseteq T$, $Y\subseteq Q$ be finite such that $X\cup Y$ is unsatisfiable. Then in particular, no model of $X$ can satisfy $Q$ (since $Y\subseteq Q$). But every structure satisfies either $T$ or $Q$, by assumption $(*)$, so every model of $X$ must be a model of $T$. But that means that $X$ is a finite axiomatization of $T$. Symmetrically we get that $Y$ is a finite axiomatization of $Q$.

Answer 2

A theory is a set of FOL statements, so that could include a statement like $\forall x \ P(x)$ or $\exists x \ P(x)$

A structure (or interpretation) is a domain of objects and a set of relations that are used to interpret the non-logical symbols. So, for example, you could take $A$ to be:

Domain of $A$ is $D_A = \{ 1,2 \}$

Interpretation of $P$ is $P_A = \{ 1 \}$. That is, object $1$ has property '$P$', but object $2$ does not.

When an interpretation $I$ makes some statement $P$ true, we write $I \vDash P$. If it does not make the statement True, we write $I \not \vDash P$.

Note that under interpretation $A$ we have that $\exists x \ P(x)$ is True, but $\forall x \ P(x) \in T$ is not True. Accordingly we write $A \vDash \exists x \ P(x)$ and $A \not \vDash \forall x \ P(x)$.

If $A$ would make all statements in $T$ True, then we would write $A \vDash T$

So, note that if $\forall x \ P(x) \in Q$, then $A$ cannot make all statements in $Q$ to be true, and as such we write $A \not \vDash Q$