2.7: Properties of Our Deductive System

Having gone through all the trouble of setting out our deductive system, we will now prove a few things both in and about that system. First, we will show that we can prove, in our deductive system, that equality is an equivalence relation.

Theorem 2.7.1.

1. \(\vdash x = x\).
2. \(\vdash x = y \rightarrow y = x\).
3. \(\vdash \left( x = y \land y = z \right) \rightarrow x = z\).

Proof. We show that we can find deductions establishing that \(=\) is reflexive, symmetric, and transitive in turn.

1. This is a logical axiom of type (E1).
2. Here is the needed deduction. Notice that the notations off to the right are listed only as an aid to the reader.
   \[\left[ x = y \land x = x \right] \rightarrow \left[ x = x \rightarrow y = x \right] \tag{E3}\]
   \[x = x \tag{E1}\]
   \[x = y \rightarrow y = x. \tag{PC}\]
3. Again, we present a deduction:
   \[\left[ x = x \land y = z \right] \rightarrow \left[ x = y \rightarrow x = z \right] \tag{E3}\]
   \[x = x \tag{E1}\]
   \[\left( x = y \land y = z \right) \rightarrow x = z. \tag{PC}\]

Chaff: Notice that we have done a bit more than prove that equality is an equivalence relation. (Heck, you've known that since fourth grade.) Rather, we've shown that our deductive system, with the axioms and rules of inference that have been outlined in this chapter, is powerful enough to prove that equality is an equivalence relation. There will be a fair bit of "our deductive system is strong enough to do such-and-such" in the pages to come.

We now prove some general properties of our deductive system. We start off with a lemma that seems somewhat problematical, but it will help us to think a little more carefully about what our deductions do for us.

Lemma 2.7.2 \(\Sigma \vdash \theta\) if and only if \(\Sigma \vdash \forall x \theta\).

Proof. First, suppose that \(\Sigma \vdash \theta\). Here is a deduction from \(\Sigma\) of \(\forall x \theta\):

\[\begin{array}{lr} \vdots & \text{Deduction of} \: \theta \\ \theta & \\ \left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right] \rightarrow \theta & \text{(PC)} \\ \left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right] \rightarrow \left( \forall x \theta \right) & \text{(QR)} \\ \forall x \theta. & \text{(PC)} \end{array}\]

There are a couple of things to point out about this proof. The first use of (PC) is justified by the fact that if \(\theta\) is true, then (anything \(\rightarrow \theta\)) is also true. The second use of (PC) depends on the fact that \(\left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right]\) is a tautology, and thus \(\forall x \theta\) is a propositional consequence of the implication. As for the (QR) step of the deduction, notice that the variable \(x\) is not free in the sentence \(\left[ \left( \forall y \left( y = y \right) \right) \lor \neg \left( \forall y \left( y = y \right) \right) \right]\), making the use of the quantifier rule legitimate.

Now, suppose that \(\Sigma \vdash \forall x \theta\). Here is a deduction from \(\Sigma\) of \(\theta\) (recall that \(\theta_x^x\) is \(\theta\)):

\[\begin{array}{lr} \vdots & \text{Deduction of} \: \forall x \theta \\ \forall x \theta & \\ \forall x \theta \rightarrow \theta_x^x & \text{(Q1)} \\ \theta_x^x. & \text{(PC)} \end{array}\]

Thus \(\Sigma \vdash \theta\) if and only if \(\Sigma \vdash \forall x \theta\).

Here is an example to show how strange this lemma might seem. Suppose that \(\Sigma\) consists of the single formula \(x = \overline{5}\). Then certainly \(\Sigma \vdash x = \overline{5}\), and so, by the lemma, \(\Sigma \vdash \left( \forall x \right) \left( x = \overline{5} \right)\). You might be tempted to say that by assuming \(x\) was equal to five, we have proved that everything is equal to five. But that is not quite what is going on. If \(x = \overline{5}\) is true in a model \(\mathfrak{A}\), that means that \(\mathfrak{A} \models x = \overline{5} \left[ s \right]\) for every assignment function \(s\). And since for every \(a \in A\), there is an assignment function \(s\) such that \(s \left( x \right) = a\), it must be true that every element of \(A\) is equal to 5, so the universe \(A\) has only one element, and everything is equal to 5. So our deduction of \(\left( \forall x \right) \left( x = \overline{5} \right)\) has preserved truth, but our assumption was much stronger than it appeared at first glance. And the moral of our story is: For a formula to be true in a structure, it must be satisfied in that structure with every assignment function.

Lemma 2.7.3. Suppose that \(\Sigma \vdash \theta\). Then if \(\Sigma^\prime\) is formed by taking any \(\sigma \in \Sigma\) and adding or deleting a universal quantifier whose scope is the entire formula, \(\Sigma^\prime \vdash \theta\).

Proof. This follows immediately from Lemma 2.7.2. Suppose that \(\forall x \sigma\) is in \(\Sigma^\prime\). By the preceding, \(\Sigma^\prime \vdash sigma\). Then, given a deduction from \(\Sigma\) of \(\theta\), to produce a deduction from \(\Sigma^\prime\) of \(\theta\), first write down a deduction from \(\Sigma^\prime\) of \(\sigma\), and then copy your deduction from \(\Sigma\) of \(\theta\). Having already established \(\sigma\), this deduction will be a valid deduction from \(\Sigma^\prime\).

The proof in the case that \(\forall x \sigma\) is an element of \(\Sigma\) and it is replaced by \(\sigma\) in \(\Sigma^\prime\) is analogous.

Notice that one consequence of this lemma is the fact that if we know \(\Sigma \vdash \theta\), we can assume (if we like) that every element of \(\Sigma\) is a sentence: By quoting Lemma 2.7.3 several times, we can replace each \(\sigma \in \Sigma\) with its universal closure.

Now we will show that in at least some sense, the system of deductions that we have developed mirrors the process that mathematicians use to prove theorems. Suppose you were asked to prove the theorem: If A is a square then A is a rectangle. A perfectly reasonable way to attack this theorem would be to assume that A is a square, and using that assumption, prove that A is a rectangle. But notice that you have not been asked to prove that A is a rectangle. You were asked to prove an implication! The Deduction Theorem says that there is a deduction of \(\phi\) from the assumption \(\theta\) if and only if there is a deduction of the implication \(\theta \rightarrow \phi\). (A bit of notation: Rather than writing the formally correct \(\Sigma \cup \{ \theta \} \vdash \phi\), we shall omit the braces and write \(\Sigma \cup \theta \vdash \phi\).)

Theorem 2.7.4 (The Deduction Theorem). Suppose that \(\theta\) is a sentence and \(\Sigma\) is a set of formulas. Then \(\Sigma \cup \theta \vdash \phi\) if and only if \(\Sigma \vdash \left( \theta \rightarrow \phi \right)\).

Proof. First, suppose that \(\Sigma \vdash \left( \theta \rightarrow \phi \right)\). Then, as the same deduction would show that \(\Sigma \cup \theta \vdash \left( \theta \rightarrow \phi \right)\), and as \(\Sigma \cup \theta \vdash \theta\) by a one-line deduction, and as \(\phi\) is a propositional consequence of \(\theta\) and \(\left( \theta \rightarrow \phi \right)\), we know that \(\Sigma \cup \theta \vdash \phi\).

For the more difficult direction we will make use of Proposition 2.2.4. Suppose that \(C = \{ \phi | \Sigma \vdash \left( \theta \rightarrow \phi \right) \}\). If we show that \(C\) contains \(\Sigma \cup \theta\), \(C\) contains all of the axioms of \(\Lambda\), and \(C\) is closed under the rules of inference as noted in Proposition 2.2.4, then by that proposition we will know that \(\{ \phi | \Sigma \cup \theta \vdash \phi \} \subseteq C\). In other words, we will know that if \(\Sigma \cup \theta \vdash \phi\), then \(\Sigma \vdash \left( \theta \rightarrow \phi \right)\), which is what we need to show.

So it remains to prove that \(C\) has the properties listed in the preceding paragraph.

1. \(\Sigma \subseteq C\): If \(\sigma \in \Sigma\), then \(\Sigma \vdash \sigma\). But then \(\Sigma \vdash \left( \theta \rightarrow \sigma \right)\), as this is a propositional consequence of \(\sigma\).
2. \(\theta \in C\): \(\Sigma \vdash \theta \rightarrow \theta\), as this is a tautology.
3. \(\Lambda \subseteq C\): This is identical to (1).
4. \(C\) is closed under the rules:
   1. Rule (PC): Suppose that \(\gamma_1, \gamma_2, \ldots, \gamma_n\) are all elements of \(C\) and \(\phi\) is a propositional consequence of \(\{ \gamma_1, \gamma_2, \ldots, \gamma_n \}\). We must show that \(\phi \in C\). By assumption, \(\Sigma \vdash \left( \theta \rightarrow \gamma_1 \right)\), \(\Sigma \vdash \left( \theta \rightarrow \gamma_2 \right), \ldots, \Sigma \vdash \left( \theta \rightarrow \gamma_n \right)\). But then as \(\left( \theta \rightarrow \phi \right)\) is a propositional consequence of the set
      \[\left\{ \left( \theta \rightarrow \gamma _ { 1 } \right) , \left( \theta \rightarrow \gamma _ { 2 } \right) , \ldots , \left( \theta \rightarrow \gamma _ { n } \right) \right\},\]
      we have that \(\Sigma \vdash \left( \theta \rightarrow \phi \right)\). In other words, \(\phi \in C\), as needed.
   2. Quantifier Rules: Suppose that \(\psi \rightarrow \phi\) is in \(C\) and \(x\) is not free in \(\psi\). We want to show that \(\left( \psi \rightarrow \forall x \phi \right)\) is an element of \(C\). In other words, we have to show that
      \[\Sigma \vdash \left[ \theta \rightarrow ( \psi \rightarrow \forall x \phi ) \right].\]
      By assumption we have
      \[\begin{array}{ll} \Sigma \vdash \left[ \theta \rightarrow \left( \psi \rightarrow \phi \right) \right] & \psi \rightarrow \phi \: \text{is in} \: C \\ \Sigma \vdash \left( \theta \land \psi \right) \rightarrow \phi & \text{propositional consequence} \\ \Sigma \vdash \left( \theta \land \psi \right) \rightarrow \forall x \phi & \text{rule (QR)} \\ \Sigma \vdash \left[ \theta \rightarrow \left( \psi \rightarrow \forall x \phi \right) \right] & \text{propositional consequence} \end{array}\]
      Notice that our use of rule (QR) is legitimate since we know that \(\theta\) is a sentence, so \(x\) is not free in \(\theta\). But the last line of our argument says that \(\left( \psi \rightarrow \forall x \phi \right) \in C\), which is what we needed to show. The other quantifier rule, dealing with the existential quantifier, is proved similarly.

So we have show that \(C\) contains \(\theta\), all the elements of \(\Sigma\) and \(\Lambda\), and \(C\) is closed under the rules. This finishes the proof of the Deduction Theorem.

Exercises

1. Lemma 2.7.2 tells us that \(\Sigma \vdash \theta\) if and only if \(\Sigma \vdash \forall x \theta\). What happens if we replace the universal quantifier by an existential quantifier? So suppose that \(\Sigma \vdash \theta\). Must \(\Sigma \vdash \exists x \theta\)? Now assume that \(\Sigma \vdash \exists x \theta\). Does \(\Sigma\) necessarily prove \(\theta\)?
2. Finish the proof of Lemma 2.7.3 by considering the case when \(\forall x \sigma\) is an element of \(\Sigma\) and is replaced by \(\sigma\) in \(\Sigma^\prime\).
3. Many authors demand that axioms be sentences rather than formulas. Explain how Lemma 2.7.2 implies that we could replace all of our axioms by their universal closures without changing the strength of our deductive system.
4. Suppose that \(\eta\) is a sentence. Prove that \(\Sigma \vdash \eta\) if and only if \(\Sigma \cup \left( \neg \eta \right) \vdash \left[ \left( \forall x \right) x = x \right] \land \neg \left[ \left( \forall x \right) x = x \right]\). Notice that this exercise tells us that our deductive system allows us to do proofs by contradiction.
5. Suppose that \(P\) is a unary relation symbol and show that
   \[\vdash [ ( \forall x ) P ( x ) ] \rightarrow [ ( \exists x ) P ( x ) ].\]
   [Suggestion: Proof by contradiction (see Exercise 4) works nicely here.]
6. If \(P\) is a binary relation symbol, show that
   \[( \forall x ) ( \forall y ) P ( x , y ) \vdash ( \forall y ) ( \forall z ) P ( z , y ).\]
7. Let \(P\) and \(Q\) be unary relation symbols, and show that
   \[\vdash [ ( \forall x ) ( P ( x ) ) \wedge ( \forall x ) ( Q ( x ) ) ] \rightarrow ( \forall x ) [ P ( x ) \wedge Q ( x ) ].\]