Writing Mathematical Proofs

Mathematical Proofs (Using Various Methods)


Master of Science in Mathematics
Lecture Notes. Accessed on: 2019-10-21 18:30:58

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 premises (or hypothesis) of the argument; and the statement $q$ is called the conclusion of the argument. 

Definition. A statement $q$ is called a propositional consequence 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.

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 proof) we shall mean the assertion that a certain statement (the conclusion) follows from other statements (the premises). A proof will be said to be (logically) valid, if and only if the conjunction of the premises implies the conclusion, that is, if the premises are all true, the conclusion 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 RuleTautologyName
$\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. 

ConclusionsJustifications
$p$premise1
$p\rightarrow q$theorem 12
$q$steps 1 and 2, modus ponens3
$q\rightarrow r$theorem 24
$r$steps 3 and 4, modus ponens5
$r\rightarrow s$theorem 36
$s$steps 5 and 6, modus ponens7

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. 

ConclusionsJustifications
$\neg q$premise1
$p\lor q$premise2
pdisjunctive syllogism3

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. 

ConclusionsJustifications
$a$ is $c$premise1
if $a$ is $c$ then $q\rightarrow t$theorem 12
$q\rightarrow t$steps 2 and 3, modus ponens3
$r$premise4
$r\rightarrow q$axiom 15
$q$steps 4 and 5, modus ponens6
$t$steps 3 and 6, modus ponens7
$t\rightarrow s$theorem 28
$s$steps 7 and 8, modus ponens9
$r\rightarrow s$steps 4 through 910
$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. 

ConclusionsJustifications
$p$premise1
$q \lor \neg q$excluded middle2
$\neg q$premise3
$\neg q\rightarrow r$theorem 14
$r$steps 3 and 4, modus ponens5
$r\rightarrow (\neg p \lor q)$theorem 26
$\neg p \lor q$steps 5 and 6, modus ponens7
$p\land \neg q$steps 1 and 38
$\neg(\neg p)\land \neg q$double negation9
$\neg (\neg p \lor q)$step 9, De Morgan10
$(\neg p \lor q) \land \neg (\neg p \lor q)$steps 7 and 10, contradiction11
$q$steps 3 and 11, indirect proof12

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. 

ConclusionsJustifications
$p\leftrightarrow q$premise1
$(p\rightarrow q) \land (q\rightarrow p) $definition of $\leftrightarrow$2
$p\rightarrow q$simplification3
$q\rightarrow \neg p$premise4
$p\lor \neg p$excluded middle5
$p$premise6
$q$steps 3 and 6, modus ponens7
$\neg p$steps 4 and 7, modus ponens8
$p\land \neg p $steps 6 and 9, contradiction9
$\neg p$steps 5-9, indirect proof10

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. 

ConclusionsJustifications
$p$premise1
$p\rightarrow (r\lor s)$axiom 12
$r\lor s$steps 1 and 2, modus ponens3
$s$premise4
$s\rightarrow y$theorem 35
$y$steps 4 and 5, modus ponens6
$y\rightarrow \neg p$theorem 17
$\neg p$steps 6 and 7, modus ponens8
$p\land \neg p$steps 1 and 8, contradiction9
$\neg s$steps 4-9, indirect proof10
$r$steps 3 and 10, disjunctive syllogism11
$r\rightarrow x$theorem 212
$x$steps 11 and 12, modus ponens13
$x\rightarrow q$theorem 414
$q$steps 13 and 14, modus ponens15

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. 

ConclusionsJustifications
$p$premise1
$p\rightarrow \neg y $axiom 12
$\neg y$steps 1 and 2, modus ponens3
$q \lor \neg q$excluded middle4
$\neg q$premise5
$\neg q\rightarrow r$axiom 26
$r$steps 5 and 6, modus ponens7
$r\rightarrow x \lor y$theorem 38
$x \lor y$steps 7 and 8, modus ponens9
$x$steps 3 and 9, disjunctive syllogism10
$x\rightarrow q\lor z$theorem 211
$q\lor z$steps 10 and 11, modus ponens12
$z$premise13
$ p\rightarrow \neg z$theorem 114
$z \rightarrow \neg p$contrapositive15
$\neg p$steps 13 and 15, modus ponens16
$p\land \neg p$steps 1 and 16, contradiction17
$\neg z$steps 13 and 17, indirect proof18
$q$steps 12 and 18, disjunctive syllogism19
$\neg (\neg q)$steps 5 and 19, contradiction20
$q$steps 4 and 20, disjunctive syllogism21

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. 

ConclusionsJustifications
$p$premise1
one and only one holds: $ r,s,q $theorem 32
$r$premise (case 1)3
$r\rightarrow \neg p$theorem 14
$\neg p $steps 3 and 4, modus ponens5
$p \land \neg p$steps 1 and 5, contradiction6
$\neg r$steps 3 and 6, indirect proof7
$s$premise (case 2)8
$s\rightarrow \neg p$theorem 29
$\neg p$steps 8 and 9, modus ponens10
$p \land \neg p$steps T and 10, contradiction11
$\neg s$steps 8 and 11, indirect proof12
$q$step 213

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$.

5/5 (1 Review)

Leave a Comment

Scroll to Top