Section 2.4: Problem 1 Solution »

# Section 2.4: A Deductive Calculus

Read this section until enlightenment (at least twice if you had no prior knowledge).
Suppose that $\Sigma\vDash\tau$ . What methods of proof might be required to demonstrate that fact? Is there necessarily a proof at all?
What is a proof? Main characteristics:
• Finiteness. This is potentially possible due to the Compactness Theorem for First-Order Logic (to be proved in Section 2.5) implying that only a finite subset of $\Sigma$ is needed to prove $\Sigma\vDash\tau$ .
• Decidability. Each step of the proof should be able to be verified, implying the set of proofs from the empty set of hypotheses ($\Sigma=\emptyset$ ) should be decidable. This would, in particular, imply that the set of all validities is effectively enumerable. This is potentially possible due to the Enumerability Theorem (to be proved in Section 2.5) implying that, under reasonable assumptions, the validities are effectively enumerable.
Vice versa, the compactness and enumerability theorems imply that for every $\Sigma\vDash\tau$ there exists a finite proof which can be found in a finite number of steps.

## Deductions

Given a wff $\phi$ , a generalization of $\phi$ is a formula $\forall x_{1}\ldots\forall x_{n}\phi$ for some $n\ge0$ and variables $x_{1},\ldots,x_{n}$ .
Logical Axioms: they are all possible generalizations of the following axioms.
1. Tautologies.
A prime formula is either an atomic formula or one of the form $\forall x\alpha$ . A nonprime formula is any other formula (built up from prime formulas using $\neg$ and $\rightarrow$ ).
Given any wff, it is build up from prime formulas by using $\mathcal{E}_{\neg}$ and $\mathcal{E}_{\rightarrow}$ , hence, can be considered as a wff of sentential logic where all prime formulas are considered as sentence symbols. A wff is called a tautology iff it is a tautology of sentential logic. Similarly, tautological implications are defined.
• If $\Gamma$ tautologically implies $\phi$ , then $\Gamma$ logically implies $\phi$ , but not necessarily vice versa.
2. $\forall x\alpha\rightarrow\alpha_{t}^{x}$ where $t$ is substitutable for $x$ in $\alpha$ .
$\alpha_{t}^{x}$ is defined as follows: a) if $\alpha$ is atomic, $t$ replaces each $x$ , b) $(\neg\alpha)_{t}^{x}=(\neg\alpha_{t}^{x})$ , c) $(\alpha\rightarrow\beta)_{t}^{x}=(\alpha_{t}^{x}\rightarrow\beta_{t}^{x})$ , d) $(\forall x\alpha)_{t}^{x}=\forall x\alpha$ , and e) $(\forall y\alpha)_{t}^{x}=\forall y\alpha_{t}^{x}$ , $y\neq x$ .
$t$ is substitutable for $x$ in $\alpha$ iff: a) if $\alpha$ is atomic, b) if $\alpha=(\neg\beta)$ and $t$ is substitutable for $x$ in $\beta$ , c) $\alpha=(\beta\rightarrow\gamma)$ and $t$ is substitutable for $x$ in $\beta$ and $\gamma$ , or d) if $\alpha=(\forall y\beta)$ and [$x$ does not occur free in $\alpha$ ] or [$y$ does not occur in $t$ and $t$ is substitutable for $x$ in $\beta$ ].
Note: $x$ is always substitutable for $x$ , and $t$ not containing any variables that occur in $\alpha$ is always substitutable for any $x$ in $\alpha$ .
For any $\alpha$ , $t$ and $x$ there is always $\alpha'$ “equivalent” to $\alpha$ such that $t$ is substitutable for $x$ in $\alpha'$ (see the Existence of Alphabetic Variants Theorem below; the idea is that the only substitutability problem we may encounter is in the case of some $\forall y\beta$ where $y\neq x$ , $x$ is free in $\beta$ , $t$ is substitutable for $x$ in $\beta$ , but $y$ occurs in $t$ , in which case we rewrite it as $\forall z\beta_{z}^{y}$ ).
3. $\forall x(\alpha\rightarrow\beta)\rightarrow(\forall x\alpha\rightarrow\forall x\beta)$ .
4. $\alpha\rightarrow\forall x\alpha$ where $x$ does not occur free in $\alpha$ .
5. (if the language has $=$ ) $x=x$ .
6. (if the language has $=$ ) $x=y\rightarrow\alpha\rightarrow\alpha'$ where $\alpha$ is atomic and $\alpha'$ is obtained from $\alpha$ by replacing $x$ in zero or more but not necessary all places by $y$ .
Rule of Inference:
1. Modus ponens: From $\alpha$ , $\alpha\rightarrow\beta$ we infer $\beta$ .
Given a set of formulas $\Gamma$ (and the set of logical axioms $\Lambda$ ), $\phi$ is a theorem of $\Gamma$ ($\phi$ is deducible from $\Gamma$ ), $\Gamma\vdash\phi$ , if $\phi$ can be obtained from $\Gamma\cup\Lambda$ by use (finite number of times) of the rule of inference. A deduction of $\phi$ from $\Gamma$ describes how $\phi$ can be obtained this way form $\Gamma$ (and $\Lambda$ ), i.e. it is a finite sequence $<\alpha_{0},\ldots,\alpha_{n}>$ of formulas such that a) $\alpha_{n}=\phi$ , and b) for $k\le n$ , $\alpha_{k}$ is in $\Gamma\cup\Lambda$ or obtained by modus ponens from some $\alpha_{i}$ and $\alpha_{j}=(\alpha_{i}\rightarrow\alpha_{k})$ , $i,j .
• $\Gamma\vdash\alpha$ iff $\Gamma\cup\Lambda$ tautologically implies $\alpha$ .
• If $\alpha$ tautologically implies $\beta$ , then $\alpha$ logically implies $\beta$ .

(Generalization Theorem) If $\Gamma\vdash\alpha$ and $x$ does not occur free in any wff in $\Gamma$ , then $\Gamma\vdash\forall x\alpha$ .
• (Generalization on Constants) If $\Gamma\vdash\alpha$ and a constant symbol $c$ does not occur in any wffs in $\Gamma$ , then there is a variable $x$ that does not occur in $\alpha$ such that $\Gamma\vdash\forall x\alpha_{x}^{c}$ (and a deduction of $\forall x\alpha_{x}^{c}$ from $\Gamma$ that does not use $c$ ).
• If $\Gamma\vdash\alpha_{c}^{x}$ where the constant symbol $c$ does not occur in any wffs in $\Gamma$ or $\alpha$ , then $\Gamma\vdash\forall x\alpha$ (and there is a deduction of $\forall x\alpha$ from $\Gamma$ that does not not use $c$ ).
• (Rule EI - Existential Instantiation) If where the constant symbol $c$ does not occur in any wffs in $\Gamma$ , $\alpha$ or $\beta$ , then $\Gamma;\exists x\alpha\vdash\beta$ (and there is a deduction of $\beta$ from $\Gamma;\exists x\alpha$ that does not use $c$ ).
(Rule T) If $\Gamma\vdash\alpha_{i}$ , $i=1,\ldots,n$ , and $\{\alpha_{1},\ldots,\alpha_{n}\}$ tautologically implies $\beta$ , then $\Gamma\vdash\beta$ .
(Deduction Theorem) If $\Gamma;\alpha\vdash\beta$ then $\Gamma\vdash(\alpha\rightarrow\beta)$ .
(Contraposition) If then $\Gamma;\beta\vdash\neg\alpha$ .
A set of wffs $\Gamma$ is inconsistent iff for some wff $\phi$ , $\Gamma\vdash\{\phi,\neg\phi\}$ .
• For every consistent $\Gamma$ there is a consistent $\Delta\supseteq\Gamma$ such that for every wff $\alpha$ , either $\alpha\in\Delta$ or $(\neg\alpha)\in\Delta$ .
(Reductio ad Absurdum) If $\Gamma;\alpha$ is inconsistent, then $\Gamma\vdash\neg\alpha$ .
(Re-Replacement Lemma) If $y$ does not occur in $\alpha$ at all, then $x$ is substitutable for $y$ in $\alpha_{y}^{x}$ and $(\alpha_{y}^{x})_{x}^{y}=\alpha$ .
(Existence of Alphabetic Variants) For a wff $\alpha$ , term $t$ and variable $x$ , there is a wff $\alpha'$ such that a) $\alpha'$ differs from $\alpha$ in the choice of quantified variables only, b) $\alpha'$ can be proved from $\alpha$ and vice versa, and c) $t$ is substitutable for $x$ in $\alpha'$ .
• The formulas $\alpha'$ as described in the theorem are called alphabetic variants of $\alpha$ .
Rules for equation:
Eq1 (p. 127) $\vdash\forall xx=x$ (reflexivity).
Eq2 (p. 127) $\vdash\forall x\forall y(x=y\rightarrow y=x)$ (symmetry).
Eq3 (p. 128) $\vdash\forall x\forall y\forall z(x=y\rightarrow y=z\rightarrow x=z)$ (transitivity).
Eq4 (p. 128) $\vdash\forall x_{1}\forall x_{2}\forall y_{1}\forall y_{2}(x_{1}=y_{1}\rightarrow x_{2}=y_{2}\rightarrow Px_{1}x_{2}\rightarrow Py_{1}y_{2})$ (similarly for $n$ -place predicate symbols).
Eq5 (p. 128) $\vdash\forall x_{1}\forall x_{2}\forall y_{1}\forall y_{2}(x_{1}=y_{1}\rightarrow x_{2}=y_{2}\rightarrow fx_{1}x_{2}=fy_{1}y_{2})$ (similarly for $n$ -place function symbols).

## Strategy

Suppose we want to deduce $\Gamma\vdash\phi$ . Working backward:
1. If $\phi=(\alpha\rightarrow\beta)$ , it is sufficient (and always possible) to show $\Gamma;\alpha\vdash\beta$ .
2. If $\phi=\forall x\alpha$ ,
1. If $x$ does not occur free in $\Gamma$ , it is sufficient (and always possible) to show $\Gamma\vdash\alpha$ .
2. If $x$ does occur free in $\Gamma$ , it is sufficient (and always possible) to show $\Gamma\vdash\alpha_{y}^{x}$ using the Re-Replacement Lemma.
3. If $\phi=(\neg\alpha)$ ,
1. If $\alpha=(\beta\rightarrow\gamma)$ , it is sufficient (and always possible) to show $\Gamma\vdash\{\beta,\neg\gamma\}$ .
2. If $\alpha=\neg\beta$ , it is sufficient (and always possible) to show $\Gamma\vdash\beta$ .
3. If $\alpha=\forall x\beta$ , it is sufficient to show $\Gamma\vdash\neg\beta_{t}^{x}$ where $t$ is substitutable for $x$ in $\beta$ , but it is not always possible.
1. One can try, $\Gamma;\gamma\vdash\neg\forall x\beta$ iff $\Gamma;\forall x\beta\vdash\neg\gamma$ , or $\Gamma;\forall y\gamma\vdash\neg\forall x\beta$ if $\Gamma;\forall x\beta\vdash\neg\gamma$ .