How do we carry out the process of constructing a proof? As mentioned earlier, the structure of the statements we wish to prove will guide our approach. In the most formal sense, this is accomplished using inference rules.
Let’s consider the proposition $p \wedge q$. Earlier, we were given the truth table for this statement, but what would a proof of such a proposition look like? Well we know that in order for $p \wedge q$ to be true, it has to be the case that $p$ is true and that $q$ is true. But how do we know that $p$ and $q$ are both true? Well, if we had a proof for $p$, we would know that it’s true and if we had a proof for $q$, we would know it’s true. That is, if we have a proof of $p$ and we have a proof of $q$, then we are able to construct a proof of $p \wedge q$.
We can express this idea as a rule, written \[\frac{p \quad q}{p \wedge q} \wedge\!i.\] This is an example of an inference rule. This rule is called $\wedge$-introduction, since it allows us to “create” a conjunction.
Inference rules are rules that govern how we can construct proofs for our statements based on what we have already proved. We can define a whole bunch of these inference rules and by using these rules, we can manipulate formulas to acquire other formulas. Inference rules are often specified in the following way: \[\frac{\alpha_1 \quad \alpha_2 \quad \cdots \quad \alpha_n}{\beta}.\]
This rule says that if I know that statements $\alpha_1, \alpha_2, \dots, \alpha_n$ are valid, then I can conclude that $\beta$ is also valid. A statement $\alpha_i$ is valid if we already know it beforehand (i.e. it is a known, given fact) or if it “shows up” at some earlier point in the proof. The reason for this is that since we were able to get to $\alpha_i$ at some point earlier in the proof, we must have obtained it by following our proof rules. Therefore, if we stopped at the point that we got $\alpha_i$, we would have a proof if $\alpha_i$.
Inference rules define a proof system. The proof system that we’ll be referring to is natural deduction, which was defined by Gerhard Gentzen in the 1930s, and contains rules that correspond to common patterns of proof used by human mathematicians. There are other proof systems which are geared for other purposes, such as use with computers or the study of proof systems.
We won’t actually be learning or using natural deduction to prove things. Instead, we’ll be walking through basic proof techniques and noting how and where they correspond to rules that are defined in natural deduction.
Here’s a particularly important inference rule (dating back to antiquity): $$\frac{p \rightarrow q \quad p}{q} \rightarrow\!e.$$
This inference rule is called $\rightarrow$-elimination. What does it mean? It’s an argument of the form
This is classical logic. But let’s consider it from the perspective of proof. What this says is that if we have a proof of the proposition $p \rightarrow q$ and we have a proof of $p$, we are able to construct a proof for $q$.
For instance, the following argument follows the same structure:
We can rewrite this so that it’s even more abstract.
Notice that this is just a linear form of our inference rule from above. There’s nothing that says that $p \rightarrow q$ and $p$ have to appear in this order. Also note that in very formal proofs, we cite the rule we’re applying along with which lines we’re applying the rule to.
One thing to notice that the content of the argument has no bearing on whether it’s valid or not. The only thing that matters is whether we have followed the rules to get from one statement to the next. (This is not unlike how many people try to argue on the internet.)
With the rules that we’ve seen, we can start trying to parse the sentence that describes our induction axiom and see how the induction proof template is derived. Recall that we have the following sentence given to us as fact, \[P(z) \wedge \forall k (P(k) \rightarrow P(\operatorname{succ}(k))) \rightarrow \forall n P(n).\]
Our goal is to prove $\forall n P(n)$. Notice that this is a sentence of the form $p \rightarrow q$, where $p$ is $P(z) \wedge \forall k(P(k) \rightarrow P(\operatorname{succ}(k)))$ and $q$ is $\forall n P(n)$, and we want to prove $q$. This means that using the second of the inference rules we just saw, we know that what we need to do is prove $p$, which, again, is \[P(z) \wedge \forall k (P(k) \rightarrow P(\operatorname{succ}(k))).\]
Now, observe that this is a conjunction: it is a sentence of the form $p \wedge q$. So this means we need a proof for $p$, which in our case is $P(z)$ and a proof for $q$, which is $\forall k (P(k) \rightarrow P(\operatorname{succ}(k)))$.
This is exactly the template for induction:
We end up with a proof tree that looks like \begin{prooftree} \AxiomC{$P(z) \wedge \forall k (P(k) \rightarrow P(\operatorname{succ}(k))) \rightarrow \forall n P(n)$} \AxiomC{$P(z)$} \AxiomC{$\forall k (P(k) \rightarrow P(\operatorname{succ}(k)))$} \BIC{$P(z) \wedge \forall k (P(k) \rightarrow P(\operatorname{succ}(k)))$} \BIC{$\forall n P(n)$} \end{prooftree}
The base case, $P(z)$, is fairly straightforward to prove—it’s a single predicate, so we can prove this directly. However, in order to prove the inductive case, $\forall k (P(k) \rightarrow P(\operatorname{succ}(k)))$, we need to continue to peel back pieces, starting with how to prove universally quantified statements.
A universally quantified statement is one of the form $\forall x P(x)$. At first glance, it seems like we have a lot of work to do, because we have to show that this statement holds for every $x$ in our domain. One way we can attempt this is to go through every element in our domain and see if we have a proof for each one. This is bad because our domain may be infinitely large (as is the case with natural numbers).
Instead, what we do is “pick” a generic representative and continue our argument with that representative. Since we just choose an arbitrary element with nothing special about it, we can conclude that our statement must hold for any element from the domain we’ve chosen, because we could’ve picked any of them.
Recall the statement that begins the inductive case for the proof of Proposition 1.9 from last class:
If $n = \operatorname{succ}(k)$ for some natural number $k$ $\dots$
The phrasing is a bit different, but the idea is that we are picking a generic natural number $k$, from which we discuss the rest of the inductive case. Since we don’t know anything about $k$, we can conclude that whatever we say will hold for any natural number.
What does the inference rule for this look like? We call this rule $\forall$-introduction: \[\frac{\boxed{\begin{matrix} u \qquad \\ \vdots \\ P(u) \end{matrix}}}{\forall x P(x)} \forall i\] Why is there a box? This notational style is due to Jaśkowski in 1934 and is a way to show that $u$ exists only inside the box. You can think of the box as the “scope” of $u$ and that $u$ can’t be used outside of the box. (Notice how “scope” is a concept that has its origins in mathematical logic)
This rule looks complicated (and the notation admittedly is), but it actually tells us exactly what a proof for $\forall x \in S, P(x)$ looks like.
Once we apply this rule, we are cleared to consider the sentence that has been quantified. In our case, this is $P(k) \rightarrow P(\operatorname{succ}(k))$, which is an implication.
Let’s see an example of universal quantification by starting a proof of Proposition 2.13, which was
For all integers $a$, $b$, and $c$, if $a \mid b$, then $a \mid bc$.
This had the formula $\forall a,b,c (a \mid b \rightarrow a \mid bc)$.
Let $a$, $b$, and $c$ be arbitrary integers. \[\cdots\]
Now, we would proceed with our proof by using the $a,b,c$ we chose. This means constructing a proof for the sentence $a \mid b \rightarrow a \mid bc$. To do that, we need to know how to prove an implication.
As stated earlier, most theorems are implications. This corresponds to the inference rule $\rightarrow$-introduction: \[\frac{\boxed{\begin{matrix}p \\ \vdots \\ q\end{matrix}}}{p \rightarrow q} \rightarrow\!i\] What this rule means is that in order to prove such statements, we assume $p$ and then use that assumption to show that the conclusion $q$ is true. Again, we use a box to show that $p$ exists as an assumption inside the box, since it’s not one of our given facts.
Let’s continue our proof from above. Since we dealt with the universal quantification, we are left with the statement $a \mid b \rightarrow a \mid bc$. This means we need to assume $a \mid b$ is true and we can use this assumption to complete our proof.
Let $a$, $b$, and $c$ be arbitrary integers. We assume that $a \mid b$. So there exists an integer $n$ such that $a \cdot n = b$. Then \begin{align*} bc &= (a \cdot n) \cdot c &\text{substitution} \\ &= a \cdot (n \cdot c) &\text{associativity} \end{align*} We note that $n \cdot c$ is an integer, since the integers are closed under multiplication. Therefore, there exists an integer $n'$ (which is our new name for $n \cdot c$) such that $a \cdot n' = bc$. Therefore, $a \mid bc$.
From this, we can see that a proof of $p \rightarrow q$ involves
Here, step (2) is a bit thin on details, but this is where the clever combining of mathematical facts and knowledge happens, so there’s not much we can say regarding the structure of the proof.
You may have noticed we did something sneaky in the above proof. When we applied the definitions for divisibility, in a sense, we substituted $a \mid b$ for the statement $\exists n (a\cdot n = b)$. This means that we were working with an existentially quantified statement. Here’s what happened
The inference rule for using an existentially quantified statement is \[\frac{\begin{matrix} \quad \\ \quad \\ \exists x P(x) \end{matrix} \quad \boxed{\begin{matrix} P(u), \text{sub $u$ for $x$} \\ \vdots \\ Q \end{matrix}}}{Q} \exists e\] In other words, if we want to use an existentially quantified statement $\exists x P(x)$, we simply choose a specific element $u$ and work with the statement $P(u)$. Notice that
Like the other rules we saw earlier, the chosen $u$ exists only within a specific scope. But we can use this fact to arrive at a proof of some other statement $Q$.
However, this is only half the story, because we end up having to arrive at a proof for an existentially quantified statement:
That is, we showed that there exists an appropriate integer and we use this to construct an existentially quantified statement. This is the inference rule \[\frac{P(t)}{\exists x P(x)} \exists i\] In essence, this is a proof that looks like this:
Let’s go back to induction and wrap up our examination with the inductive case. Here, we have a sentence $\forall k (P(k) \rightarrow P(\operatorname{succ}(k)))$. What we need to do then is to show for an arbitrary element, say $t$, that $P(t) \rightarrow P(\operatorname{succ}(t))$. So now, we are left with an implication that we need to come up with a proof for. Then our inference rule says that we need to assume $P(t)$ and use that assumption to construct a proof for $P(\operatorname{succ}(t))$.
We can now put all of this together.
Let’s prove that addition on the natural numbers is associative. We say that an operation $\circ$ is associative if $m \circ (n \circ p) = (m \circ n) \circ p$ for all $m, n, p$. In other words, the order in which we “execute” the operation on three elements doesn’t matter. String and list concatenation are other examples of operations that are associative, while subtraction is an example of an operation that is not associative.
For all natural numbers $m, n, p$, $m + (n+p) = (m+n)+p$.
We will prove this by induction on $m$.
Base case. If $m = z$, then we have \begin{align*} m + (n + p) &= z + (n + p) &\text{base case} \\ &= n + p &\text{addition} \\ &= (z+ n) + p &\text{addition} \\ &= (m+ n) + p &\text{base case} \end{align*}
Inductive case. Let $k$ be an arbitrary natural number. Assume for all natural numbers $n$ and $p$ that $k + (n + p) = (k + n) + p$. Let $m = \operatorname{succ}(k)$. We have \begin{align*} m + (n + p) &= \operatorname{succ}(k) + (n + p) &\text{inductive case} \\ &= \operatorname{succ}(k + (n + p)) &\text{addition} \\ &= \operatorname{succ}((k + n) + p) &\text{inductive hypothesis} \\ &= \operatorname{succ}(k + n) + p &\text{addition} \\ &= (\operatorname{succ}(k) + n) + p &\text{addition} \\ &= (m + n) + p &\text{inductive case} \end{align*}
A common use for induction that you may have encountered before is for proving properties of sums or sequences of integers. Consider the following.
For every $n \in \mathbb N$, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$.
If you’ve been taught this formula before, then you’ve probably been told the story of Gauss solving this problem when he was a child—a story which has been embellished over the last century and a half. However, his teachers in this story, in assigning $n = 100$, gave him an easy out since he only needed to consider one instance of the problem, so his solution does not use induction. We don’t have that luxury, since we want to prove that this formula holds for all $n$.
We will prove that $\sum_{i=0}^n i = \frac{n(n+1)}{2}$ by induction on $n$.
Base case. Let $n = 0$. Then $\sum \limits_{i=0}^0 i = 0$ and $\frac{0 \cdot (0+1)}2 = 0$. Therefore, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$ holds for $n = 0$.
Inductive case. Let $k \in \mathbb N$ be arbitrary. Assume that $\sum \limits_{i=0}^k i = \frac{k(k+1)}2$. We will show that $\sum \limits_{i=0}^{k+1} i = \frac{(k+1)(k+2)}2$. We have the following: \begin{align*} \sum_{i=0}^{k+1} i &= \sum_{i=0}^k i + (k+1) & \text{sum} \\ &= \frac{k(k+1)}2 + (k+1) & \text{inductive hypothesis} \\ &= (k+1) \cdot \left(\frac k 2 + 1 \right) & \text{factoring}\\ &= (k+1) \cdot \left(\frac k 2 + \frac 2 2 \right) &\text{$1 = \frac n n$}\\ &= \frac{(k+1)(k+2)}2 & \text{common denominator} \end{align*}
Thus, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$ holds for $n = k+1$. Therefore, $\sum \limits_{i=0}^n i = \frac{n(n+1)}2$ holds for all $n \in \mathbb N$.
Notice that even though we were proving a fact about a sum, we were really performing induction on the structure of the natural numbers. This is typically how induction is learned—as a property of the natural numbers. But recall that the structure of the proof mirrors the structure of the recursive definition of the natural numbers. This suggests that induction can be applied to other recursive structures, beyond just the natural numbers.