# 2.5 Validity and Entailment

Validity and entailment are semantic notions that compare formulas across all structures, rather than inside one fixed structure. Satisfaction tells us whether a formula is true in a particular structure under a particular assignment, while validity and entailment ask whether truth is forced in every possible interpretation of the language.

### Validity

A sentence is valid if it is true in every structure for its language.

### Definition 2.41 (Validity)

Let $A$ be a sentence. We say that $A$ is valid if:
$$
\mathcal{M} \models A
$$
for every structure $\mathcal{M}$ for the language of $A$.

In this case we write:
$$
\models A
$$

Validity means that the truth of $A$ depends only on its logical form, not on any special property of a particular structure.

### Example 2.42

The sentence:
$$
\forall x \, (x = x)
$$
is valid, because equality is reflexive in every structure.

The sentence:
$$
\forall x \, P(x)
$$
is not valid, because we may choose a structure in which the predicate $P$ does not hold for every element of the domain.

For example, let the domain be:
$$
M = \{0,1\}
$$

and let:
$$
P^{\mathcal{M}} = \{0\}
$$

Then:
$$
\mathcal{M} \not\models \forall x \, P(x)
$$
because $1$ is not in $P^{\mathcal{M}}$.

### Countermodels

To show that a sentence is not valid, it is enough to give one structure in which the sentence is false. Such a structure is called a countermodel.

### Definition 2.43 (Countermodel)

Let $A$ be a sentence. A countermodel to $A$ is a structure $\mathcal{M}$ such that:
$$
\mathcal{M} \not\models A
$$

Countermodels are important because they provide concrete evidence that a sentence does not follow from logic alone.

### Semantic Entailment

Entailment generalizes validity by allowing assumptions.

### Definition 2.44 (Semantic Entailment)

Let $\Gamma$ be a set of sentences, and let $A$ be a sentence in the same language.

We say that $\Gamma$ semantically entails $A$ if every model of $\Gamma$ is also a model of $A$.

In this case we write:
$$
\Gamma \models A
$$

Equivalently:
$$
\Gamma \models A
$$
means that for every structure $\mathcal{M}$, if:
$$
\mathcal{M} \models B
$$
for every $B \in \Gamma$, then:
$$
\mathcal{M} \models A
$$

Thus $A$ is a semantic consequence of $\Gamma$ exactly when $A$ is true in every structure where all assumptions in $\Gamma$ are true.

### Example 2.45

Let $\Gamma$ contain the two sentences:
$$
\forall x \, \forall y \, (x < y \to ¬(y < x))
$$

and:
$$
\forall x \, \forall y \, \forall z \, ((x < y \land y < z) \to x < z)
$$

The first sentence says that $<$ is asymmetric, and the second sentence says that $<$ is transitive.

Then:
$$
\Gamma \models \forall x \, ¬(x < x)
$$

To see this, let $\mathcal{M}$ be any model of $\Gamma$, and suppose for contradiction that there is an element $a$ such that:
$$
a < a
$$

By asymmetry, from:
$$
a < a
$$
we obtain:
$$
¬(a < a)
$$

This is impossible, so no such $a$ exists, and therefore:
$$
\mathcal{M} \models \forall x \, ¬(x < x)
$$

Since $\mathcal{M}$ was arbitrary, the entailment holds.

### Validity as Entailment from No Assumptions

Validity is a special case of entailment.

For a sentence $A$:
$$
\models A
$$
means the same thing as:
$$
\varnothing \models A
$$

This says that every structure satisfying all sentences in the empty set also satisfies $A$. Since every structure satisfies the empty set of assumptions, this is exactly the statement that $A$ is true in every structure.

### Logical Equivalence

Two sentences are logically equivalent if they entail each other.

### Definition 2.46 (Logical Equivalence)

Let $A$ and $B$ be sentences. We say that $A$ and $B$ are logically equivalent if:
$$
A \models B
$$
and:
$$
B \models A
$$

Equivalently:
$$
\models A \leftrightarrow B
$$

This means that $A$ and $B$ have the same truth value in every structure.

### Example 2.47

The sentences:
$$
¬\forall x \, P(x)
$$
and:
$$
\exists x \, ¬P(x)
$$
are logically equivalent.

Indeed, a structure satisfies:
$$
¬\forall x \, P(x)
$$
exactly when not every element satisfies $P$, and this holds exactly when some element fails to satisfy $P$.

Thus:
$$
\models ¬\forall x \, P(x) \leftrightarrow \exists x \, ¬P(x)
$$

### Satisfiability

A set of sentences is satisfiable if it has at least one model.

### Definition 2.48 (Satisfiability)

Let $\Gamma$ be a set of sentences. We say that $\Gamma$ is satisfiable if there exists a structure $\mathcal{M}$ such that:
$$
\mathcal{M} \models \Gamma
$$

If no such structure exists, then $\Gamma$ is unsatisfiable.

Satisfiability asks whether the assumptions can all be made true together in some structure.

### Example 2.49

The set:
$$
\Gamma = \{\exists x \, P(x), \forall x \, ¬P(x)\}
$$
is unsatisfiable.

The first sentence says that at least one object satisfies $P$, while the second sentence says that no object satisfies $P$.

No structure can make both sentences true at the same time.

### Lemma 2.50 (Entailment and Unsatisfiability)

Let $\Gamma$ be a set of sentences, and let $A$ be a sentence. Then:
$$
\Gamma \models A
$$
if and only if:
$$
\Gamma \cup \{¬A\}
$$
is unsatisfiable.

Proof

Suppose first that:
$$
\Gamma \models A
$$

Then every structure satisfying all sentences in $\Gamma$ also satisfies $A$.

Therefore no structure can satisfy all sentences in $\Gamma$ and also satisfy $¬A$, because satisfying $¬A$ means that $A$ is false.

Hence:
$$
\Gamma \cup \{¬A\}
$$
is unsatisfiable.

Conversely, suppose that:
$$
\Gamma \cup \{¬A\}
$$
is unsatisfiable.

Let $\mathcal{M}$ be any structure such that:
$$
\mathcal{M} \models \Gamma
$$

If $\mathcal{M} \not\models A$, then:
$$
\mathcal{M} \models ¬A
$$

and therefore:
$$
\mathcal{M} \models \Gamma \cup \{¬A\}
$$

This contradicts the assumption that $\Gamma \cup \{¬A\}$ is unsatisfiable.

Thus every model of $\Gamma$ satisfies $A$, and so:
$$
\Gamma \models A
$$

### Example 2.51

We show:
$$
\{p \to q, p\} \models q
$$

using unsatisfiability.

It is enough to show that:
$$
\{p \to q, p, ¬q\}
$$
is unsatisfiable.

Suppose a valuation satisfies all three formulas. Then:
$$
p
$$
is true, and:
$$
q
$$
is false.

But if $p$ is true and $q$ is false, then:
$$
p \to q
$$
is false.

This contradicts the assumption that:
$$
p \to q
$$
is true.

Therefore no valuation satisfies all three formulas, and hence:
$$
\{p \to q, p\} \models q
$$

### Entailment with Free Variables

For formulas with free variables, entailment is defined using both structures and assignments.

Let $\Gamma$ be a set of formulas and let $A$ be a formula. We write:
$$
\Gamma \models A
$$
if for every structure $\mathcal{M}$ and every assignment $s$, whenever:
$$
\mathcal{M}, s \models B
$$
for every $B \in \Gamma$, then:
$$
\mathcal{M}, s \models A
$$

This definition extends the earlier definition for sentences, since sentences do not depend on assignments.

### Example 2.52

The entailment:
$$
x < y, \quad y < z \models x < z
$$
does not hold in all structures with an arbitrary binary relation $<$.

It becomes valid if transitivity is included as an assumption:
$$
\forall x \, \forall y \, \forall z \, ((x < y \land y < z) \to x < z), \quad x < y, \quad y < z \models x < z
$$

This example shows that entailment depends on the assumptions that have been included, and that relation symbols have no fixed meaning unless axioms constrain their behavior.