Predicate Logic

Proof. Assign a weight $w(s)$ to each symbol: $w(f)=n-1$ for an $n$ -ary function symbol $f$; $w(x)=w(c)=-1$ for variables and constants; $w=0$ for the comma and both parentheses. For a string $\sigma$, let $w(\sigma )$ be the sum of the weights of its symbols.

Claim. $w(t)=-1$ for every term $t$, and $w(\sigma )\ge 0$ for every proper non-empty initial segment $\sigma$ of a term.

Both parts go by induction on $t$. If $t$ is a variable or a constant then $w(t)=-1$, and $t$ has no proper non-empty initial segment, so the second part is vacuous. If $t=f(t_1,\dots ,t_n)$ then, using $w(t_i)=-1$,

For the second part, a proper non-empty initial segment $\sigma$ of $t$ is either the single symbol $f$, or $f($, or $f($ followed by $t_1,\dots ,t_{k-1}$, a separator, and an initial segment ${\sigma }_k$ of $t_k$ (possibly empty, possibly all of $t_k$) for some $k\le n$. In the last case

where $w({\sigma }_k)\ge -1$ holds by the induction hypothesis ($\ge 0$ if ${\sigma }_k$ is a proper segment, $=-1$ if ${\sigma }_k=t_k$, and $=0$ if empty). The first two cases give $w=n-1\ge 0$.

Now suppose a term $t$ were a proper initial segment of a term. The claim gives $w(t)\ge 0$, contradicting $w(t)=-1$. For the consequence: the first symbol decides the clause, since variables, constants and function symbols are distinct symbols. If $f(t_1,\dots ,t_n)$ and $f(t_1^{\prime },\dots ,t_n^{\prime })$ are the same string, then $t_1$ and $t_1^{\prime }$ are initial segments of one another, hence equal by the first part; strip them and repeat.∎

Proof (Sketch — rests on induction on formulas and Theorem *Unique readability of terms*). The same weight argument, now counting parentheses: give $($ weight $+1$, $)$ weight $-1$, and every other symbol weight $0$. By induction on formulas, every formula has total weight $0$ and every proper non-empty initial segment has weight $>0$; hence no proper initial segment of a formula is a formula. Uniqueness of the decomposition follows: an atomic formula is recognised because it does not begin with $($, and in a non-atomic formula the symbol just after the opening $($ is $\neg$, $\forall$ or $\exists$ — or else the formula is binary, and then its connective is the unique symbol at which the running parenthesis weight first returns to $1$. The argument rests on nothing beyond induction on formulas and Unique readability of terms, which supplies the atomic case.∎

Proof. Fix a structure with domain $D$ and an assignment $s$. By the satisfaction clauses, $\forall x\phi$ is satisfied iff $\phi$ is satisfied under $s$ modified to send $x$ to $d$, for every $d\in D$. Hence $\neg \forall x\phi$ is satisfied iff it is not the case that every $d$ works, i.e. iff some $d\in D$ makes $\phi$ fail, i.e. iff some $d$ makes $\neg \phi$ hold — which is exactly satisfaction of $\exists x\neg \phi$. The middle step, "not every $d$ " $\Rightarrow$ "some $d$ not", is the classical negation of a universal claim over the set $D$, available because the metatheory is classical.

The second equivalence is the first applied to $\neg \phi$, together with $\neg \neg \psi \equiv \psi$: from $\neg \forall x\neg \phi \equiv \exists x\neg \neg \phi \equiv \exists x\phi$, negate both sides. The two consequences follow by negating each equivalence once more.∎

Proof. For the first equivalence: $\forall x(\phi \wedge \psi )$ holds iff for every $d\in D$ both $\phi$ and $\psi$ hold of $d$, which is the same statement about $D$ as "($\phi$ holds of every $d$) and ($\psi$ holds of every $d$) ". The second equivalence follows from the first by Duality of the quantifiers, applied to $\neg \phi$ and $\neg \psi$.

The surviving implications are immediate: a single witness $d$ for $\exists x(\phi \wedge \psi )$ witnesses each conjunct separately; and if $\phi$ holds of every $d$ then $\phi \vee \psi$ does.

One counter-model refutes both converses. Take $D=\{1,2\}$ with $P^{\mathcal{M}}=\{1\}$ and $Q^{\mathcal{M}}=\{2\}$, and put $\phi =P(x)$, $\psi =Q(x)$. Then $\forall x(P(x)\vee Q(x))$ is true — each element lies in $P$ or in $Q$ — while $(\forall xP(x))\vee (\forall xQ(x))$ is false, since neither predicate holds of both elements. Dually $(\exists xP(x))\wedge (\exists xQ(x))$ is true while $\exists x(P(x)\wedge Q(x))$ is false, as no element lies in both.∎

Proof. Like quantifiers commute because "for every pair $(d,e)\in D\times D$ " does not depend on the order in which the two coordinates are presented, and likewise for "for some pair"; formally, both sides unwind to the same condition on $D\times D$ by two applications of the satisfaction clause.

For the mixed direction, suppose $\exists y\forall x\phi$ is satisfied, witnessed by $e\in D$: then $\phi$ holds for every $d$ assigned to $x$ while $y$ is assigned that single $e$. So given any $d$, the element $e$ witnesses $\exists y\phi$ for that $d$, and $\forall x\exists y\phi$ follows.

For the failure of the converse, take $D=\mathbb{N}$ with the usual $<$, and $\phi =(x<y)$. Then $\forall x\exists y(x<y)$ is true — take $y=x+1$ — while $\exists y\forall x(x<y)$ asserts a natural number strictly above every natural number, itself included, and is false.∎

Proof. Because $x$ is not free in $\psi$, the truth value of $\psi$ does not change when the assignment to $x$ is varied — this is Truth depends only on the free variables, proved in the semantics section. Write $A(d)$ for "$\phi$ is satisfied when $x$ is assigned $d$ ", and let $B$ be the fixed truth value of $\psi$. Over a non-empty domain $D$ the four claims become

The first, second and fourth are distributions of a constant through a quantifier and use $D\ne \varnothing$ only in the left-to-right direction of the second. The third is the interesting one. ($\Rightarrow$) If $\forall dA(d)$ fails then some $d_0$ has $\neg A(d_0)$, and that $d_0$ satisfies $A(d_0)\to B$ vacuously; if instead $B$ holds, every $d$ satisfies $A(d)\to B$, and $D\ne \varnothing$ supplies one. ($\Leftarrow$) If some $d_0$ satisfies $A(d_0)\to B$ and $\forall dA(d)$ holds, then $A(d_0)$ holds, hence $B$. Non-emptiness of the domain was used twice, which is where the standing assumption that domains are non-empty earns its keep.

For failure without the side condition, take the fourth law with $\phi =\psi =P(x)$, so that $x$ is free in $\psi$. The right-hand side $\forall x(P(x)\to P(x))$ is valid. The left-hand side $P(x)\to \forall xP(x)$ is refuted in the structure $D=\{1,2\}$, $P^{\mathcal{M}}=\{1\}$ under the assignment $x\mapsto 1$: the antecedent holds and the consequent fails. The two sides differ because on the right the previously free $x$ of $\psi$ has been captured by the new quantifier — the phenomenon analysed in the next section.∎

Proof (Sketch — the full induction is in Enderton §2.4 and van Dalen §2.3). The requirement that $y$ be entirely fresh guarantees that no occurrence of $y$ introduced by the substitution falls inside the scope of a quantifier on $y$, so the new $\forall y$ binds exactly the occurrences the old $\forall x$ bound. Satisfaction is then preserved by The substitution lemma below, applied with the term $y$, together with the observation that $s(x\mapsto d)$ and $s(y\mapsto d)$ agree on all variables relevant to the two formulas. The full argument is an induction on $\phi$ carried out in Enderton §2.4 and van Dalen §2.3.∎

Proof. First, for terms: an induction on $u$ shows $(u[x:=t]{)}^{\mathcal{M}}[s]=u^{\mathcal{M}}[s(x\mapsto t^{\mathcal{M}}[s])]$. It is immediate for a constant and for a variable (the two cases $u=x$ and $u\ne x$), and the inductive step for $f(u_1,\dots ,u_n)$ applies $f^{\mathcal{M}}$ to the induction hypotheses.

Now induct on $\phi$. For atomic $\phi$ the claim is the term case applied inside each argument. The connective cases are immediate, since both substitution and satisfaction commute with $\neg ,\wedge ,\vee ,\to$.

The quantifier case is where substitutability is used. Consider $\phi =\forall y\psi$.

Case $y=x$. Then $x\notin \mathrm{FV}(\phi )$ and $\phi [x:=t]=\phi$. By Truth depends only on the free variables, changing the value assigned to $x$ cannot affect satisfaction of $\phi$, so both sides agree.

Case $y\ne x$ and $x\notin \mathrm{FV}(\phi )$. Again the substitution does nothing and the relevance lemma settles it.

Case $y\ne x$ and $x\in \mathrm{FV}(\phi )$. Substitutability forces $y\notin \mathrm{var}(t)$ and makes $t$ substitutable for $x$ in $\psi$. Now $\phi [x:=t]=\forall y(\psi [x:=t])$, so the left-hand side says: for every $d\in D$, $\psi [x:=t]$ is satisfied under $s(y\mapsto d)$. By the induction hypothesis that is: for every $d$, $\psi$ is satisfied under $s(y\mapsto d)(x\mapsto t^{\mathcal{M}}[s(y\mapsto d)])$. Because $y$ does not occur in $t$, the value of $t$ is unaffected by what $y$ is assigned, so $t^{\mathcal{M}}[s(y\mapsto d)]=t^{\mathcal{M}}[s]$. Writing $e=t^{\mathcal{M}}[s]$ and using $x\ne y$ to swap the two modifications, the condition becomes: for every $d$, $\psi$ is satisfied under $s(x\mapsto e)(y\mapsto d)$ — which is precisely satisfaction of $\forall y\psi$ under $s(x\mapsto e)$, the right-hand side. The case of $\exists$ is identical with "every" replaced by "some".∎

Proof. First, for terms: if $s_1$ and $s_2$ agree on $\mathrm{var}(t)$ then $t^{\mathcal{M}}[s_1]=t^{\mathcal{M}}[s_2]$, by induction on $t$ — immediate for constants and variables, and preserved by clause 3 of Value of a term.

Now induct on $\phi$. If $\phi$ is atomic, its free variables are exactly the variables of its terms, so the term case gives equal values and hence the same truth value by clauses 1–2. The cases of $\neg$ and the binary connectives are immediate from the induction hypothesis, since $\mathrm{FV}$ of a compound contains $\mathrm{FV}$ of each part.

Let $\phi =\forall x\psi$ and suppose $s_1,s_2$ agree on $\mathrm{FV}(\phi )=\mathrm{FV}(\psi )\setminus \{x\}$. For any $d\in M$ the assignments $s_1(x\mapsto d)$ and $s_2(x\mapsto d)$ agree on all of $\mathrm{FV}(\psi )$: on $x$ they both give $d$, and elsewhere they inherit the agreement. By the induction hypothesis they satisfy $\psi$ together or not at all, so the condition "for every $d$ " holds for $s_1$ iff it holds for $s_2$. The case $\exists$ is identical with "some" in place of "every". The final claim is the case $\mathrm{FV}(\phi )=\varnothing$, where the hypothesis on $s_1,s_2$ is vacuous.∎

Proof. (1) ($\Rightarrow$) Let $\mathcal{M}\models \Sigma$. If $\mathcal{M}\models \sigma$ then $\mathcal{M}$ is a model of $\Sigma \cup \{\sigma \}$, so $\mathcal{M}\models \tau$ by hypothesis, and clause 4 of Satisfaction (Tarski) gives $\mathcal{M}\models \sigma \to \tau$; if $\mathcal{M}/\models \sigma$, the same clause gives it directly. ($\Leftarrow$) Let $\mathcal{M}\models \Sigma \cup \{\sigma \}$. Then $\mathcal{M}\models \sigma \to \tau$ and $\mathcal{M}\models \sigma$, so $\mathcal{M}\models \tau$.

(2) ($\Rightarrow$) A model of $\Sigma \cup \{\neg \sigma \}$ would be a model of $\Sigma$ satisfying $\neg \sigma$, hence not $\sigma$, contradicting $\Sigma \models \sigma$. ($\Leftarrow$) If $\mathcal{M}\models \Sigma$ but $\mathcal{M}/\models \sigma$, then $\mathcal{M}\models \neg \sigma$ by clause 3, so $\Sigma \cup \{\neg \sigma \}$ is satisfiable.

(3) is (2) with $\Sigma =\varnothing$, since every structure is a model of $\varnothing$.∎

Proof. Fix $\mathcal{M}$ and an assignment $s$, and suppose $\mathcal{M}\models (\forall x\phi )[s]$. Put $d=t^{\mathcal{M}}[s]\in M$. Clause 5 of Satisfaction (Tarski) applied with this particular $d$ gives $\mathcal{M}\models \phi [s(x\mapsto d)]$. Since $t$ is substitutable for $x$ in $\phi$, The substitution lemma converts this into $\mathcal{M}\models \phi [x:=t][s]$. As $\mathcal{M}$ and $s$ were arbitrary, the implication is satisfied everywhere.

The second formula is the first read through duality: assume $\mathcal{M}\models \phi [x:=t][s]$, so by the substitution lemma $\mathcal{M}\models \phi [s(x\mapsto d)]$ with $d=t^{\mathcal{M}}[s]$, and clause 6 needs only that one witness.∎

Proof (Sketch — rests on the completeness theorem, not proved here). The direction ($\Rightarrow$) is trivial: a model of $\Sigma$ models each subset. The direction ($\Leftarrow$) is not proved here. It follows from the completeness theorem stated in the next section: if $\Sigma$ had no model then $\Sigma \models \perp$, so by completeness $\Sigma ⊢\perp$; a derivation is a finite object and uses only finitely many members of $\Sigma$, so some finite ${\Sigma }_0\subseteq \Sigma$ has ${\Sigma }_0⊢\perp$, and by soundness ${\Sigma }_0$ has no model. The proof therefore rests on completeness (Gödel 1929), which is beyond this chapter; Henkin's construction is the standard route.∎

Proof. Induct on the structure of $\phi$, producing a prenex equivalent at each step.

Atomic $\phi$. Already prenex, with empty prefix.

$\phi =\neg \psi$. By the induction hypothesis $\psi \equiv Q_1{x}_1\cdots Q_n{x}_n\chi$ with $\chi$ quantifier-free. Applying Duality of the quantifiers $n$ times, once per quantifier from the outside in,

where $\overline{\forall }=\exists$ and $\overline{\exists }=\forall$. The matrix $\neg \chi$ is quantifier-free, so this is prenex. Each application is legitimate because equivalence is a congruence: replacing a subformula by an equivalent one preserves satisfaction, as an easy induction on the surrounding context shows.

$\phi =\psi \wedge \theta$ (and the other binary connectives). By the induction hypothesis $\psi \equiv Q_1{x}_1\cdots Q_m{x}_m\chi$ and $\theta \equiv Q_1^{\prime }{y}_1\cdots Q_n^{\prime }{y}_n{\chi }^{\prime }$. First rename: by Renaming bound variables, choose the $x_i$ and $y_j$ all distinct from one another and not free in either formula — this is the step that makes the whole construction work, and it is always available because there are infinitely many variables and each formula is finite. Now every $x_i$ is not free in $\theta$ and every $y_j$ is not free in $\psi$, so Pulling a quantifier out applies repeatedly, moving the prefix of $\psi$ outwards through $\wedge \theta$ and then the prefix of $\theta$ outwards: