Section 2.4: Problem 5 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Find a function $f$ such that if a formula $\phi$ has a deduction of length $n$ from a set $\Gamma$ , and if $x$ does not occur free in $\Gamma$ , then $\forall x\phi$ has a deduction from $\Gamma$ of length $f(n)$ . The more slowly your function grows, the better.

If $x$ does not occur free in $\phi$ , we can use axiom 4 and add

to the end. However, in general, $\phi$ may contain $x$ as a free variable. What we will try to do is to change every formula $\alpha$ in a deduction of $\phi$ to $\forall x\alpha$ , and evaluate $d(n)$ , the number of additional steps needed in the worst case scenario, by induction:

If $\alpha\in\Lambda$ , then $\forall x\alpha\in\Lambda$ and $d(n)=0$ .
If $\alpha\in\Gamma$ , then $x$ does not occur free in $\alpha$ , and $d(n)=2$ with two additional steps in the deduction $\alpha,\overset{A4}{\alpha\rightarrow\forall x\alpha},\overset{MP}{\forall x\alpha}$ .
Otherwise, $\alpha$ is deduced from $\beta$ and $\beta\rightarrow\alpha$ , where by induction we have already changed them to $\forall x\beta$ and $\forall x(\beta\rightarrow\alpha)$ , accordingly, and we need three steps instead of one previous MP-rule, namely, $\overset{A3}{\forall x(\beta\rightarrow\alpha)\rightarrow(\forall x\beta\rightarrow\forall x\alpha)}$ , and two new MP-rules.

Overall, we see that, in the worst case scenario when no axioms are used, we need three formulas in a deduction instead of each one. Of course, there could be some shortcuts even if there are no axioms in the deduction, for example, as noted at the very beginning of the solution, but in the worst case scenario, $f(n)=3n$ .

A more precise function would be one in two variables, where for a deduction of $\phi$ of length $n=l+m$ using $m$ axioms and $l$ other rules ( $\Gamma$ or MP), there is always a deduction of $\forall x\phi$ of length $f(l,m)=L(l,m)+M(l,m)$ using $M(l,m)$ axioms and $L(l,m)$ other rules ( $\Gamma$ or MP). Then, $\begin{eqnarray*} L(l,m) & = & 2l\\ M(l,m) & = & l+m\\ f(l,m) & = & 3l+m \end{eqnarray*}$

Example (p. 122). A deduction for $\vdash x=y\rightarrow y=x$ : $<\overset{A6}{x=y\rightarrow x=x\rightarrow y=x}$ ,

, a deduction of length 5. According to our derived function $f$ , $\forall x\forall yx=y\rightarrow y=x$ should require no more than $5\cdot3^{2}=45$ steps. However, here we have two free variables, 3 axioms, and 2 MP-rules. Hence, the formula in two variables gives us $L(2,3)=4$ , $M(2,3)=5$ , $f(2,3)=9$ for $\forall xx=y\rightarrow y=x$ , and $L(4,5)=8$ , $M(4,5)=9$ , $f(4,5)=17$ for $\forall x\forall yx=y\rightarrow y=x$ . As mentioned on page 122, the length of $17$ is indeed the best we can achieve in this case.

Subpages

Section 2.4: Problem 5 Solution

Section 2.4: Problem 5 Solution