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:

for every structure $\mathcal{M}$ for the language of $A$.

In this case we write:

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:

is valid, because equality is reflexive in every structure.

The sentence:

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:

and let:

Then:

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:

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:

Equivalently:

means that for every structure $\mathcal{M}$, if:

for every $B \in \Gamma$, then:

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:

and:

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

Then:

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

By asymmetry, from:

we obtain:

This is impossible, so no such $a$ exists, and therefore:

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$:

means the same thing as:

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:

and:

Equivalently:

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

Example 2.47

The sentences:

and:

are logically equivalent.

Indeed, a structure satisfies:

exactly when not every element satisfies $P$, and this holds exactly when some element fails to satisfy $P$.

Thus:

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:

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:

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:

if and only if:

is unsatisfiable.

Proof

Suppose first that:

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:

is unsatisfiable.

Conversely, suppose that:

is unsatisfiable.

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

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

and therefore:

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

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

Example 2.51

We show:

using unsatisfiability.

It is enough to show that:

is unsatisfiable.

Suppose a valuation satisfies all three formulas. Then:

is true, and:

is false.

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

is false.

This contradicts the assumption that:

is true.

Therefore no valuation satisfies all three formulas, and hence:

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:

if for every structure $\mathcal{M}$ and every assignment $s$, whenever:

for every $B \in \Gamma$, then:

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

Example 2.52

The entailment:

does not hold in all structures with an arbitrary binary relation $<$.

It becomes valid if transitivity is included as an assumption:

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.