Chapter 37 Proofs with quantifiers

In chapter 18 we discussed strategies for constructing proofs using the basic rules of natural deduction for TFL. The same principles apply to the rules for the quantifiers. If we want to prove a quantifier sentence $\forall\mathscr{x}\,\mathscr{A}(\mathscr{x})$ or $\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$ , we can work backward by justifying the sentence we want by $\forall$ I or $\exists$ I and trying to find a proof of the corresponding premise of that rule. And to work forward from a quantified sentence, we apply $\forall$ E or $\exists$ E, as the case may be.

Specifically, suppose you want to prove $\forall\mathscr{x}\,\mathscr{A}(\mathscr{x})$ . To do so using $\forall$ I, we would need a proof of $\mathscr{A}(\mathscr{c})$ for some name $\mathscr{c}$ which does not occur in any undischarged assumption. To apply the corresponding strategy, i.e., to construct a proof of $\forall\mathscr{x}\,\mathscr{A}(\mathscr{x})$ by working backward, is thus to write $\mathscr{A}(\mathscr{c})$ above it and then to continue to try to find a proof of that sentence.

Line number	Formula	Justification
	$\vdots$
$n$	$\mathscr{A}(\mathscr{c})$
$n+1$	$\forall\mathscr{x}\,\mathscr{A}(\mathscr{x})$	$\forall$ I $n$

$\mathscr{A}(\mathscr{c})$ is obtained from $\mathscr{A}(\mathscr{x})$ by replacing every free occurrence of $\mathscr{x}$ in $\mathscr{A}(\mathscr{x})$ by $\mathscr{c}$ . For this to work, $\mathscr{c}$ must satisfy the special condition. We can ensure that it does by always picking a name that does not already occur in the proof constructed so far. (Of course, it will occur in the proof we end up constructing—just not in an assumption that is undischarged at line $n+1$ .)

To work backward from a sentence $\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$ we similarly write a sentence above it that can serve as a justification for an application of the $\exists$ I rule, i.e., a sentence of the form $\mathscr{A}(\mathscr{c})$ .

Line number	Formula	Justification
	$\vdots$
$n$	$\mathscr{A}(\mathscr{c})$
$n+1$	$\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$	$\exists$ I $n$

This looks just like what we would do if we were working backward from a universally quantified sentence. The difference is that whereas for $\forall$ I we have to pick a name $\mathscr{c}$ which does not occur in the proof (so far), for $\exists$ I we may and in general must pick a name $\mathscr{c}$ which already occurs in the proof. Just like in the case of $\vee$ I, it is often not clear which $\mathscr{c}$ will work out, and so to avoid having to backtrack you should work backward from existentially quantified sentences only when all other strategies have been applied.

By contrast, working forward from sentences $\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$ generally always works and you won’t have to backtrack. Working forward from an existentially quantified sentence takes into account not just $\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$ but also whatever sentence $\mathscr{B}$ you would like to prove. It requires that you set up a subproof above $\mathscr{B}$ , wherein $\mathscr{B}$ is the last line, and a substitution instance $\mathscr{A}(\mathscr{c})$ of $\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$ as the assumption. In order to ensure that the condition on $\mathscr{c}$ that governs $\exists$ E is satisfied, chose a name $\mathscr{c}$ which does not already occur in the proof.

Line number	Subproof level	Formula	Justification
	0	$\vdots$
$m$	0	$\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$
	0	$\vdots$
$n$	open subproof, 1	$\mathscr{A}(\mathscr{c})$	AS
	1	$\vdots$
$k$	1	$\mathscr{B}$
$k+1$	close subproof, 0	$\mathscr{B}$	$\exists$ E $m$ , $n$ – $k$

You’ll then continue with the goal of proving $\mathscr{B}$ , but now inside a subproof in which you have an additional sentence to work with, namely $\mathscr{A}(\mathscr{c})$ .

Lastly, working forward from $\forall\mathscr{x}\,\mathscr{A}(\mathscr{x})$ means that you can always write down $\mathscr{A}(\mathscr{c})$ and justify it using $\forall$ E, for any name $\mathscr{c}$ . Of course, you wouldn’t want to do that willy-nilly. Only certain names $\mathscr{c}$ will help in your task of proving whatever goal sentence you are working on. So, like working backward from $\exists\mathscr{x}\,\mathscr{A}(\mathscr{x})$ , you should work forward from $\forall\mathscr{x}\,\mathscr{A}(\mathscr{x})$ only after all other strategies have been applied.

Let’s consider as an example the argument $\forall x(A(x)\rightarrow B)\therefore\exists x\,A(x)\rightarrow B$ . To start constructing a proof, we write the premise at the top and the conclusion at the bottom.

Line number	Formula	Justification
$1$	$\forall x(A(x)\rightarrow B)$	PR
	$\vdots$
$n$	$\exists x\,A(x)\rightarrow B$

The strategies for connectives of TFL still apply, and you should apply them in the same order: first work backward from conditionals, negated sentences, conjunctions, and now also universal quantifiers, then forward from disjunctions and now existential quantifiers, and only then try to apply $\rightarrow$ E, $\neg$ E, $\lor$ I, $\forall$ E, or $\exists$ I. In our case, that means, working backward from the conclusion:

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(A(x)\rightarrow B)$	PR
$2$	open subproof, 1	$\exists x\,A(x)$	AS
	1	$\vdots$
$n-1$	1	$B$
$n$	close subproof, 0	$\exists x\,A(x)\rightarrow B$	$\rightarrow$ I $2$ –( $n-1$ )

Our next step should be to work forward from $\exists x\,A(x)$ on line $2$ . For that, we have to pick a name not already in our proof. Since no names appear, we can pick any name, say ‘ $d$ ’

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(A(x)\rightarrow B)$	PR
$2$	open subproof, 1	$\exists x\,A(x)$	AS
$3$	open subproof, 2	$A(d)$	AS
	2	$\vdots$
$n-2$	2	$B$
$n-1$	close subproof, 1	$B$	$\exists$ E $2$ , $3$ –( $n-2$ )
$n$	close subproof, 0	$\exists x\,A(x)\rightarrow B$	$\rightarrow$ I $2$ –( $n-1$ )

Now we’ve exhausted our primary strategies, and it is time to work forward from the premise $\forall x(A(x)\rightarrow B)$ . Applying $\forall$ E means we can justify any instance of $A(\mathscr{c})\rightarrow B$ , regardless of what $\mathscr{c}$ we choose. Of course, we’ll do well to choose $d$ , since that will give us $A(d)\rightarrow B$ . Then we can apply $\rightarrow$ E to justify $B$ , finishing the proof.

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(A(x)\rightarrow B)$	PR
$2$	open subproof, 1	$\exists x\,A(x)$	AS
$3$	open subproof, 2	$A(d)$	AS
$4$	2	$A(d)\rightarrow B$	$\forall$ E $1$
$5$	2	$B$	$\rightarrow$ E $4$ , $3$
$6$	close subproof, 1	$B$	$\exists$ E $2$ , $3$ – $5$
$7$	close subproof, 0	$\exists x\,A(x)\rightarrow B$	$\rightarrow$ I $2$ – $6$

Now let’s construct a proof of the converse. We begin with

Line number	Formula	Justification
$1$	$\exists x\,A(x)\rightarrow B$	PR
	$\vdots$
$n$	$\forall x(A(x)\rightarrow B)$

Note that the premise is a conditional, not an existentially quantified sentence, so we should not (yet) work forward from it. Working backward from the conclusion, $\forall x(A(x)\rightarrow B)$ , leads us to look for a proof of $A(d)\rightarrow B$ :

Line number	Formula	Justification
$1$	$\exists x\,A(x)\rightarrow B$	PR
	$\vdots$
$n-1$	$A(d)\rightarrow B$
$n$	$\forall x(A(x)\rightarrow B)$	$\forall$ I $n-1$

And working backward from $A(d)\rightarrow B$ means we should set up a subproof with $A(d)$ as an assumption and $B$ as the last line:

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,A(x)\rightarrow B$	PR
$2$	open subproof, 1	$A(d)$	AS
	1	$\vdots$
$n-2$	1	$B$
$n-1$	close subproof, 0	$A(d)\rightarrow B$	$\rightarrow$ I $2$ –( $n-2$ )
$n$	0	$\forall x(A(x)\rightarrow B)$	$\forall$ I $n-1$

Now we can work forward from the premise on line $1$ . That’s a conditional, and its consequent happens to be the sentence $B$ we are trying to justify. So we should look for a proof of its antecedent, $\exists x\,A(x)$ . Of course, that is now readily available, by $\exists$ I from line $2$ , and we’re done:

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,A(x)\rightarrow B$	PR
$2$	open subproof, 1	$A(d)$	AS
$3$	1	$\exists x\,A(x)$	$\exists$ I $2$
$4$	1	$B$	$\rightarrow$ E $1$ , $3$
$5$	close subproof, 0	$A(d)\rightarrow B$	$\rightarrow$ I $2$ – $4$
$6$	0	$\forall x(A(x)\rightarrow B)$	$\forall$ I $5$

Practice exercises

A. Use the strategies to find proofs for each of the following arguments and theorems:

1.

$A\rightarrow\forall x\,B(x)\therefore\forall x(A\rightarrow B(x))$
2.

$\exists x(A\rightarrow B(x))\therefore A\rightarrow\exists x\,B(x)$
3.

$\forall x(A(x)\wedge B(x))\leftrightarrow(\forall x\,A(x)\wedge\forall x\,B(x))$
4.

$\exists x(A(x)\vee B(x))\leftrightarrow(\exists x\,A(x)\vee\exists x\,B(x))$
5.

$A\vee\forall x\,B(x))\therefore\forall x(A\vee B(x))$
6.

$\forall x(A(x)\rightarrow B)\therefore\exists x\,A(x)\rightarrow B$
7.

$\exists x(A(x)\rightarrow B)\therefore\forall x\,A(x)\rightarrow B$
8.

$\forall x(A(x)\rightarrow\exists y\,A(y))$

Use only the basic rules of TFL in addition to the basic quantifier rules.

B. Use the strategies to find proofs for each of the following arguments and theorems:

1.

$\forall x\,R(x,x)\therefore\forall x\,\exists y\,R(x,y)$
2.

$\forall x\,\forall y\,\forall z[(R(x,y)\wedge R(y,z))\rightarrow R(x,z)]$
$\therefore\forall x\,\forall y[R(x,y)\rightarrow\forall z(R(y,z)\rightarrow R(% x,z))]$
3.

$\forall x\,\forall y\,\forall z[(R(x,y)\wedge R(y,z))\rightarrow R(x,z)],$
$\forall x\,\forall y(R(x,y)\rightarrow R(y,x))$
$\therefore\forall x\,\forall y\,\forall z[(R(x,y)\wedge R(x,z))\rightarrow R(y% ,z)]$
4.

$\forall x\,\forall y(R(x,y)\rightarrow R(y,x))$
$\therefore\forall x\,\forall y\,\forall z[(R(x,y)\wedge R(x,z))\rightarrow% \exists u(R(y,u)\wedge R(z,u))]$
5.

$\neg\exists x\,\forall y(A(x,y)\leftrightarrow\lnot A(y,y))$

C. Use the strategies to find proofs for each of the following arguments and theorems:

1.

$\forall x\,A(x)\rightarrow B\therefore\exists x(A(x)\rightarrow B)$
2.

$A\rightarrow\exists x\,B(x)\therefore\exists x(A\rightarrow B(x))$
3.

$\forall x(A\vee B(x))\therefore A\vee\forall x\,B(x))$
4.

$\exists x(A(x)\rightarrow\forall y\,A(y))$
5.

$\exists x(\exists y\,A(y)\rightarrow A(x))$

These require the use of IP. Use only the basic rules of TFL in addition to the basic quantifier rules.