Are you someone who relies on logic and evidence for solving problems? Mathematical proofs will help you refine and take advantage of this valuable way of thinking as it applies to mathematics, and potentially other areas such as philosophy and computer science.

In math, as in life, proof gets rid of any doubts we have that something is true. But proofs in math don't just aim to prove one thing or one situation. They use what is called deductive reasoning to prove that something is always true in all variations for all of time. This deductive reasoning means using other proven statements to deduce new facts and proofs. As long as these original statements are indeed true, then proofs give us absolute certainty about the topic. Proofs in math might be the only time such absolute certainty is possible in life. This bold mission and staunch claim to certainty is what makes proofs so treasured in the field. In this section you’ll learn the basics of the logic, language, methods, and theories involved in making sound proofs in math.

In this section we discuss valid arguments, inference rules, and various methods of proof including direct proofs, indirect proofs, proof by contrapositive, and proof by cases.

## Valid Arguments

An ** argument** is defined as a statement $q$ being asserted as a consequence of some list of statements $p_1, p_2, \ldots,p_k.$ The statements $p_1, p_2, \ldots,p_k$ are called the

**(or**

*premises***) of the argument; and the statement $q$ is called the**

*hypothesis***of the argument.**

*conclusion*** Definition**. A statement $q$ is called a

**of statements $p_1, p_2, \ldots, p_k$ if and only if the single statement $(p_1 \land p_2 \land \cdots \land p_k) \rightarrow q$ is a tautology.**

*propositional consequence*** Example**. Test the validity of the following arguments.

\begin{array}{l} p \longleftrightarrow q \\ q \lor r \\ \neg \, r \\ \hline \therefore \, \neg \, p \end{array} | \begin{array}{l} p \lor q \\ \neg \, q \rightarrow r \\ \neg \, p \lor \neg \, r \\ \hline \therefore \, \neg \, p \end{array} |

** Solution**. The arguments can be shown to be valid or not by constructing a truth table for the following statements

$\quad (a)$ $[(p \longleftrightarrow q)\land (q \lor r ) \land (\neg \, r )] \longleftrightarrow (\neg p)$

$\quad (b)$ $[(p \lor q)\land (\neg \, q \rightarrow r)\land (\neg \, p \lor \neg \, r)] \longrightarrow (\neg p)$

and determining whether or not these are tautologies. The reader should verify that the first statement is not a tautology, and so the argument in (a) is not valid. What about the second statement?

## Inference Rules

By a ** mathematical proof** (or

**) we shall mean the assertion that a certain statement (the**

*proof**conclusion*) follows from other statements (the

*premises*). A proof will be said to be (logically)

**, if and only if the conjunction of the premises implies the conclusion, that is, if the premises are all true, the conclusion**

*valid**must*also be true. In order to determine whether a mathematical proof is valid we need to be able to accomplish two goals: a valid logically argument and justifications for each statement. It's important to realize that a logically argument depends upon its form in that it does not matter what the components of the argument are. For example, is the following argument valid? \begin{equation} \label{argument} \text{If $ p\rightarrow q$ and $q\rightarrow r$, then $p\rightarrow r$.} \end{equation} Since the implication $(p\rightarrow q)\land (q\rightarrow r)\rightarrow (p\rightarrow r)$ is a tautology, \eqref{argument} is a valid argument, as can be proven by constructing a truth table. Indeed \eqref{argument} is valid as an argument regardless of the meaning of $p$, $q$ and $r.$ A proof demonstrates that the conclusion must happen and is a consequence of the premises.

** Theorem**. Suppose the statement $r$ is a consequence of the premises $p_1, p_2, \ldots, p_k$ and also suppose another statement $q$ is a consequence of the same premises $p_1, p_2, \ldots, p_k$ and $r.$ Then $q$ is a consequence of just $p_1, p_2, \ldots, p_k.$

** Proof**. For a rigorous proof we need to show that \begin{equation} \label{tautproof} \left( (p_1 \land \cdots \land p_k \rightarrow r) \land (p_1 \land \cdots \land p_k \land r \rightarrow q) \right) \rightarrow \left( p_1 \land \cdots \land p_k \rightarrow q \right) \end{equation} is a tautology. To understand why \eqref{tautproof} is a tautology, let $p$ be the variable for $p_1\land p_2\land \cdots \land p_k$ and consider the truth table for $p\rightarrow q.$ In any row where $p$ is false, $p\rightarrow q$ is true by definition of $\rightarrow.$ In any row where $p$ is true, $r$ must also be true, since $p\rightarrow r$ is a tautology. But since $(p\land r)\rightarrow q$ is always true, this guarantees that in every row where $p$ is true, $q$ must also be true. Therefore, $p\rightarrow q$ is a tautology, as desired.

Before we begin writing proofs, let's review the following tautologies.

Inference Rule | Tautology | Name |

$\begin{array}{l} p \\ \hline \therefore \, p\lor q \end{array}$ | $p\rightarrow (p\lor q)$ | Addition |

$\begin{array}{l} p\land q\\ \hline \therefore \, p \end{array}$ | $(p\land q)\rightarrow p$ | Simplification |

$\begin{array}{l} p \\ q \\ \hline \therefore \, p\land q \end{array} $ | $((p)\land (q))\rightarrow (p\land q)$ | Conjunction |

$\begin{array}{l} p \\ p\rightarrow q \\ \hline \therefore \, q \end{array} $ | $[p\land (p\rightarrow q)]\rightarrow q $ | Modus ponens |

$\begin{array}{l} \neg q \\ p\rightarrow q \\ \hline \therefore \, \neg p \end{array} $ | $[\neg q \land (p\rightarrow q)]\rightarrow \neg p$ | Modus tollens |

$\begin{array}{l} p\rightarrow q \\ q\rightarrow r \\ \hline \therefore \, p\rightarrow r \end{array} $ | $[(p\rightarrow q)\land (q\rightarrow r)]\rightarrow (p\rightarrow r)$ | Hypothetical syllogism |

$\begin{array}{l} p\lor q \\ \neg p \\ \hline \therefore \, q \end{array}$ | $[(p\lor q)\land \neg p]\rightarrow q$ | Disjunctive syllogism |

## Direct Proofs

Basically, direct proofs are proofs that do not use the Law of Excluded middle tautology. In each of the following examples, we use inference rules to write a proof in column format — and we also write a paragraph proof. For more on the Law of the Excluded middle from a philosophy point of view read this.

** Example**. Given the three previously proven theorems: Theorem 1: $p\rightarrow q$, Theorem 2: $q\rightarrow r,$ and Theorem 3: $r\rightarrow s.$ We can now prove the next theorem. $$ \text{Theorem: If $p$ then $s$.} $$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$p$ | premise | 1 |

$p\rightarrow q$ | theorem 1 | 2 |

$q$ | steps 1 and 2, modus ponens | 3 |

$q\rightarrow r$ | theorem 2 | 4 |

$r$ | steps 3 and 4, modus ponens | 5 |

$r\rightarrow s$ | theorem 3 | 6 |

$s$ | steps 5 and 6, modus ponens | 7 |

We end with a paragraph proof.

Assume $p$. By Theorem 1, we know $q$, and so by Theorem 2, we now have $r$. Hence by Theorem 3, we have $s$ as needed.

** Example**. Prove: if $p\lor q$ and $\neg \, q,$ then $p.$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$\neg q$ | premise | 1 |

$p\lor q$ | premise | 2 |

p | disjunctive syllogism | 3 |

We end with a paragraph proof.

Assume $\neg q$ and $p\lor q$. We can not have $q$ and $\neg q$, thus $p$ follows immediately.

** Example**. Assume the following: Definition: $a$ is said to be $b$ iff $r\rightarrow s$, Axiom 1: $r\rightarrow q$, Theorem 1: If $a$ is $c$ then $q\rightarrow t,$ Theorem 2: $t\rightarrow s.$ Prove the following theorem. $$ \text{Theorem: If $a$ is $c$ then $a$ is $b.$} $$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$a$ is $c$ | premise | 1 |

if $a$ is $c$ then $q\rightarrow t$ | theorem 1 | 2 |

$q\rightarrow t$ | steps 2 and 3, modus ponens | 3 |

$r$ | premise | 4 |

$r\rightarrow q$ | axiom 1 | 5 |

$q$ | steps 4 and 5, modus ponens | 6 |

$t$ | steps 3 and 6, modus ponens | 7 |

$t\rightarrow s$ | theorem 2 | 8 |

$s$ | steps 7 and 8, modus ponens | 9 |

$r\rightarrow s$ | steps 4 through 9 | 10 |

$a \text{ is } b$ | definition of $a$ is $b$ | 11 |

We end with a paragraph proof.

Assume $a$ is $c$. By Theorem 1, we have $q\rightarrow t$. To prove that $a$ is $b$ we assume $r$. Then by Axiom 1, we have $q$, which now yields $t$. By Theorem 2, it follows that $s$. Therefore we have shown $r\rightarrow s$ as needed.

## Indirect Proofs

** Example**. Given the two previously proven theorems: Theorem 1: $\neg q\rightarrow r$, Theorem 2: If $r$ then either $\neg p$ or $q.$ Prove the following theorem. $$ \text{Theorem: $p\rightarrow q.$} $$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$p$ | premise | 1 |

$q \lor \neg q$ | excluded middle | 2 |

$\neg q$ | premise | 3 |

$\neg q\rightarrow r$ | theorem 1 | 4 |

$r$ | steps 3 and 4, modus ponens | 5 |

$r\rightarrow (\neg p \lor q)$ | theorem 2 | 6 |

$\neg p \lor q$ | steps 5 and 6, modus ponens | 7 |

$p\land \neg q$ | steps 1 and 3 | 8 |

$\neg(\neg p)\land \neg q$ | double negation | 9 |

$\neg (\neg p \lor q)$ | step 9, De Morgan | 10 |

$(\neg p \lor q) \land \neg (\neg p \lor q)$ | steps 7 and 10, contradiction | 11 |

$q$ | steps 3 and 11, indirect proof | 12 |

We end with a paragraph proof.

Assume $p$. Suppose $\neg q$ for otherwise we are finished. Then $r$ by Theorem 1. By hypothesis we cannot have $\neg p$, and so by Theorem 2, we have $q$ as needed.

** Example**. Prove: if $p\leftrightarrow q$ and $q\rightarrow \neg \, p,$ then $\neg \, p.$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$p\leftrightarrow q$ | premise | 1 |

$(p\rightarrow q) \land (q\rightarrow p) $ | definition of $\leftrightarrow$ | 2 |

$p\rightarrow q$ | simplification | 3 |

$q\rightarrow \neg p$ | premise | 4 |

$p\lor \neg p$ | excluded middle | 5 |

$p$ | premise | 6 |

$q$ | steps 3 and 6, modus ponens | 7 |

$\neg p$ | steps 4 and 7, modus ponens | 8 |

$p\land \neg p $ | steps 6 and 9, contradiction | 9 |

$\neg p$ | steps 5-9, indirect proof | 10 |

We end with a paragraph proof.

Assume for a contradiction $p$. Since $p$ and $q$ are equivalent, we have $q$. By hypothesis, we then have $\neg p$. Since $\neg p$ and $p$ is a contradiction, our original premise of $p$ can not happen. Whence $\neg p$.

** Example**. Assume the following: Axiom 1: $p$ implies either $r$ or $s,$ Theorem 1: $y\rightarrow \neg p,$ Theorem 2: $r\rightarrow x,$ Theorem 3: $s\rightarrow y,$ Theorem 4: $x\rightarrow q.$ Prove the following theorem. $$ \text{Theorem: $p\rightarrow q.$} $$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$p$ | premise | 1 |

$p\rightarrow (r\lor s)$ | axiom 1 | 2 |

$r\lor s$ | steps 1 and 2, modus ponens | 3 |

$s$ | premise | 4 |

$s\rightarrow y$ | theorem 3 | 5 |

$y$ | steps 4 and 5, modus ponens | 6 |

$y\rightarrow \neg p$ | theorem 1 | 7 |

$\neg p$ | steps 6 and 7, modus ponens | 8 |

$p\land \neg p$ | steps 1 and 8, contradiction | 9 |

$\neg s$ | steps 4-9, indirect proof | 10 |

$r$ | steps 3 and 10, disjunctive syllogism | 11 |

$r\rightarrow x$ | theorem 2 | 12 |

$x$ | steps 11 and 12, modus ponens | 13 |

$x\rightarrow q$ | theorem 4 | 14 |

$q$ | steps 13 and 14, modus ponens | 15 |

We end with a paragraph proof.

Assume $p$. If we have $s$, then by Theorem 3, we have $y$; yet by Theorem 1 this yields $\neg p$. Since we can not have both $\neg p$ and $p$ we see that we can not have $s$. Hence we have $\neg s$. By Axiom 1, we must have $r$. By Theorem 2, we now have $x$, and so by Theorem 4, we conclude with $q$ as needed.

## Proof by Contrapositive

** Example**. Assume the following: Axiom 1: $p\rightarrow \neg y.$ Axiom 2: $\neg q\rightarrow r$. Theorem 1: $p\rightarrow \neg z.$ Theorem 2: $x\rightarrow \text{ either } q \text{ or } z.$ Theorem 3: $r\rightarrow \text{ either } x \text{ or } y.$ $$ \text{Theorem: $\neg p\rightarrow \neg q.$} $$

** Solution**. We prove the (logical equivalent) contrapositive statement $p\rightarrow q$. We begin with a column proof.

Conclusions | Justifications | |

$p$ | premise | 1 |

$p\rightarrow \neg y $ | axiom 1 | 2 |

$\neg y$ | steps 1 and 2, modus ponens | 3 |

$q \lor \neg q$ | excluded middle | 4 |

$\neg q$ | premise | 5 |

$\neg q\rightarrow r$ | axiom 2 | 6 |

$r$ | steps 5 and 6, modus ponens | 7 |

$r\rightarrow x \lor y$ | theorem 3 | 8 |

$x \lor y$ | steps 7 and 8, modus ponens | 9 |

$x$ | steps 3 and 9, disjunctive syllogism | 10 |

$x\rightarrow q\lor z$ | theorem 2 | 11 |

$q\lor z$ | steps 10 and 11, modus ponens | 12 |

$z$ | premise | 13 |

$ p\rightarrow \neg z$ | theorem 1 | 14 |

$z \rightarrow \neg p$ | contrapositive | 15 |

$\neg p$ | steps 13 and 15, modus ponens | 16 |

$p\land \neg p$ | steps 1 and 16, contradiction | 17 |

$\neg z$ | steps 13 and 17, indirect proof | 18 |

$q$ | steps 12 and 18, disjunctive syllogism | 19 |

$\neg (\neg q)$ | steps 5 and 19, contradiction | 20 |

$q$ | steps 4 and 20, disjunctive syllogism | 21 |

We end with a paragraph proof.

Assume $p$. Then by Axiom 1 we have $\neg y$. Assume for a contradiction that $\neg q$. Then by Axiom 2 we have $r$, and so either $x$ or $y$ by Theorem 3. In case we have $x$, then by Theorem 2 we have $z$. Now $\neg p$ follows by Theorem 1 and so this contradiction show that $x$ can not happen. Hence $y$ follows. Yet now we have $y$ and $\neg y$ and so it fact we cannot have $\neg q$. Therefore $q$ as needed.

## Proof by Cases

** Example**. Assume the following: Theorem 1: $r\rightarrow \, \neg p,$ Theorem 2: $s\rightarrow \, \neg p,$ Theorem 3: A complete set of logical possibilities is: $r, s,$ and $q;$ that is, one of the statements $r, s,$ and $q$ is true and only one. Prove the following theorem. $$ \text{Theorem: If $p$ then $q.$} $$

** Solution**. We begin with a column proof.

Conclusions | Justifications | |

$p$ | premise | 1 |

one and only one holds: $ r,s,q $ | theorem 3 | 2 |

$r$ | premise (case 1) | 3 |

$r\rightarrow \neg p$ | theorem 1 | 4 |

$\neg p $ | steps 3 and 4, modus ponens | 5 |

$p \land \neg p$ | steps 1 and 5, contradiction | 6 |

$\neg r$ | steps 3 and 6, indirect proof | 7 |

$s$ | premise (case 2) | 8 |

$s\rightarrow \neg p$ | theorem 2 | 9 |

$\neg p$ | steps 8 and 9, modus ponens | 10 |

$p \land \neg p$ | steps T and 10, contradiction | 11 |

$\neg s$ | steps 8 and 11, indirect proof | 12 |

$q$ | step 2 | 13 |

We end with a paragraph proof.

Assume $p$. By Theorem 3, there are exactly three cases two consider. If $r$, then we have $\neg p$ by Theorem 1 which is contrary to hypothesis. Similarly, $s$ is contrary to hypothesis. Hence we have $q$ as needed.

## Simple Examples

We end this section with a short discussion on how you might have seen these types of arguments (proofs) before in precalculus. We will demonstrate thee ways to prove the statement: $$ \text{If $x^3-x^2+x-1=0$, then $x=1$.} $$

(Direct Proof) Assume $x^3-x^2+x-1=0$. Then $(x-1)(x^2+1)=0$, which implies that either $x-1=0$ or $x^2+1=0$. But we know that $x^2+1\neq 0$ (since $x$ is real), and so it must be the case that $x-1$=0. Hence $x=1$.

(Proof by Contrapositive) Assume $x\neq 1$. Then $x-1\neq 0$. Also, since $x$ is real, $x^2+1\neq 0$. It follows that $(x-1)(x^2+1)\neq 0$. Upon multiplication we obtain the result $x^3-x^2+x-1\neq 0$.

(Proof by Contradiction) Suppose $x^3-x^2+x-1$ and assume for a contradiction that $x\neq 1$. Then $x-1\neq 0$. Since $x^4-x^2+x-1=(x-1)(x^2+1))$ and $x-1\neq 0$, it must be that $x^2+1=0$. This is a contradiction because $x$ is a real number. Therefore, we conclude $x=1$.

## Exercises

In the following exercises, verify if the argument is valid.

$\begin{array}{l} p \rightarrow q \\ \neg \, r \rightarrow \neg \, q \\ \hline\therefore \, \neg \, r \rightarrow \neg \, p\end{array}$ | $\begin{array}{l} p\longleftrightarrow q\\p \\ \hline\therefore \, q\end{array}$ | $\begin{array}{l} \\p\lor q\\\neg \, p \\ \hline\therefore \, q\end{array}$ | $\begin{array}{l} \\p\land q\\\neg \, p \rightarrow q \\ \hline\therefore \, \neg \, q\end{array}$ | $\begin{array}{l} \\p\rightarrow q \\p \\ \hline\therefore \, q \end{array} $ |

$\begin{array}{l} \\p\rightarrow q \\\neg \, q \\ \hline\therefore \, p\rightarrow r \end{array}$ | $\begin{array}{l} \\p\rightarrow q \\q \\ \hline\therefore \, p \end{array}$ | $\begin{array}{l} \\p\rightarrow q \\\neg \, p \\ \hline\therefore \, \neg \, q \end{array}$ | $\begin{array}{l} \\p\rightarrow q\\\neg \, q \rightarrow \neg \, r \\ \hline\therefore \, r \rightarrow p\end{array}$ | $\begin{array}{l}p \rightarrow q \\\neg \, p \rightarrow \neg \, q \\p \land \neg \, r \\ \hline\therefore \, s \end{array}$ |

In the following exercises, write both a column proof and a paragraph proof.

** Exercise**. Given the four previously proven theorems: Theorem 1: $\neg p \land q$, Theorem 2: $r\rightarrow p$, Theorem 3: $\neg r \rightarrow s$. Theorem 4: $s\rightarrow t$. Prove the next theorem: Theorem: $t$.

** Exercise**. Given the three previously proven theorems: Theorem 1: $p\rightarrow q$, Theorem 2: $\neg p \rightarrow r$, and Theorem 3: $r\rightarrow s$. Prove the next theorem: Theorem: $\neg q \rightarrow s$.