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

5/5 (1 Review)
Scroll to Top