Theory Entailment (First-Order Logic)

first-order-logic

Definition

Theory Entailment (First-Order Logic)

A theory $\Gamma$ entails a sentence $\phi$, written $\Gamma \models \phi$, if for every structure $\mathcal{M}$:

$$\mathcal{M}\models \Gamma ⟹\mathcal{M}\models \phi$$

where $\mathcal{M}\models \Gamma$ means $\mathcal{M}\models \psi$ for all $\psi \in \Gamma$.

Examples

Example

Does $P(a),\forall x(P(x)\to P(f(x)))\models \forall xP(x)$ hold?

No. Let $\mathcal{D}=\{0,1\}$, $a^{\mathcal{M}}=0$, $f^{\mathcal{M}}(x)=0$, and $P^{\mathcal{M}}=\{0\}$.

• $0\in P^{\mathcal{M}}$, so $\mathcal{M}\models P(a)$.
• For every $d\in \mathcal{D}$: if $d\in P^{\mathcal{M}}$ then $f^{\mathcal{M}}(d)=0\in P^{\mathcal{M}}$, so $\mathcal{M}\models \forall x(P(x)\to P(f(x)))$.
• But $1\notin P^{\mathcal{M}}$, so $\mathcal{M}/\models \forall xP(x)$.

The premises are true, the conclusion is false — therefore the entailment fails.

Example

Does $\forall xA(x)\models \exists xA(x)$ hold?

Yes. In every structure $\mathcal{M}$, the domain is non-empty. If $\mathcal{M}\models \forall xA(x)$, then $A^{\mathcal{M}}=\mathcal{D}$. Since $\mathcal{D}\ne \varnothing$, there is some $d\in A^{\mathcal{M}}$, so $\mathcal{M}\models \exists xA(x)$.

Example

Does $\forall x(A(x)\to B(x))\models \exists xB(x)$ hold?

No. Let $\mathcal{D}=\{0\}$, $A^{\mathcal{M}}=\varnothing$, $B^{\mathcal{M}}=\varnothing$.

• For every $d\in \mathcal{D}$: $d\notin A^{\mathcal{M}}$, so the antecedent is false and the implication $A(d)\to B(d)$ is true. Hence $\mathcal{M}\models \forall x(A(x)\to B(x))$.
• But $B^{\mathcal{M}}=\varnothing$, so $\mathcal{M}/\models \exists xB(x)$.

The implication is vacuously true when nothing has $A$; that does not force anything to have $B$.

Example

Given the three formulas below, show that none is entailed by the other two.

$$\begin{array}{rlrl}1.& \forall xR(x,x)& & \text{(reflexivity)}\\ 2.& \forall x\forall y(R(x,y)\to R(y,x))& & \text{(symmetry)}\\ 3.& \forall x\forall y\forall z((R(x,y)\wedge R(y,z))\to R(x,z))& & \text{(transitivity)}\end{array}$$

For each pair, provide a structure satisfying the two but not the third:

Without	Structure
reflexivity	$\mathcal{D}=\{0,1\}$, $R^{\mathcal{M}}=\varnothing$ — symmetric and transitive, but $0$ is not related to itself
symmetry	$\mathcal{D}=\{0,1\}$, $R^{\mathcal{M}}=\{(0,0),(1,1),(0,1)\}$ — reflexive and transitive (a partial order), but $(0,1)\in R$ while $(1,0)\notin R$
transitivity	$\mathcal{D}=\{0,1,2\}$, $R^{\mathcal{M}}=\{(0,0),(1,1),(2,2),(0,1),(1,0),(1,2),(2,1)\}$ — reflexive and symmetric, but $(0,1),(1,2)\in R$ while $(0,2)\notin R$

Each structure witnesses the independence of one axiom from the other two.