Mathematical Proofs: Basics

What is a proof?

A mathematical proof is a sequence of logically correct deductions based on a set of hypotheses and rules of inference to establish the truth value of a proposition under consideration. In the collection of hypotheses, we include the propositions already known to be true or assumed to be true. At times we use a more direct approach and use a truth table to look at all the possibilities to conclude the truth value of the desired proposition.

Let’s assume that we are given $H = \{H_1, H_2, \ldots, H_n\},$ as set of hypotheses. We apply a rule of inference using $H_j$ and (possibly) $H_k$ to conclude $C_1$ . Then for the next step, $C_1$ can be used as a hypothesis along with members of $H$ . The objective is to conclude $C$ , which is the desired proposition; in other words, $C$ is the proposition we want to prove.

It is pertinent to note that if we prove a statement that is known to be false, then there are only two possibilities. Either a rule of inference is not applied correctly, or at least one of the hypotheses is not true.

Examples

How do we prove a proposition from a set of hypotheses? We explain it with the help of examples. In each of the following examples, we’ll look at a scenario, formalize it, state the set of hypotheses, note down the desired conclusion, and then present a proof to deduce the desired conclusion.

Science grade

For the first example, consider the following scenario in which Beth is a sixth-grade student.

Scenario

If Beth prepares from the textbook, (then) she gets an A grade in science. If she prepares from the class notes, (then) she gets a B grade in science. Beth prepared from the textbook or class notes. Beth did not get a B grade in science.

Can we conclude that Beth gets an A grade in science?

Formalization

$s_1$ : Beth prepares from the textbook.
$s_2$ : Beth gets an A grade in science.
$s_3$ : Beth prepares from the class notes.
$s_4$ : Beth gets a B grade in science.

Hypotheses

$H_1:\;\;\; s_1 \Rightarrow s_2 \;\;\;:$ If Beth prepares from the textbook, (then) she gets an A grade in science.
$H_2:\;\;\; s_3 \Rightarrow s_4 \;\;\;:$ If Beth prepares from the class notes, (then) she gets a B grade in science.
$H_3:\;\;\; s_1 \lor s_3 \;\;\;:$ Beth prepared from the textbook or class notes.
$H_4:\;\;\; \neg s_4 \;\;\;:$ Beth did not get a B grade in science.

Conclusion

$C:\;\;\; s_2 \;\;\;:$ Beth gets an A grade in science.

If we apply the conjunction rule on $H_1$ and $H_2$ , we conclude the following:

$C_1:\;\;\; (s_1 \Rightarrow s_2)\land (s_3 \Rightarrow s_4). \;\;\;$

<br>

Now, use $C_1$ and $H_3$ to apply constructive dilemma, as shown on the right, and get the following conclusion:

$C_2:\;\;\; s_2\lor s_4. \;\;\;$

Apply disjunctive syllogism using $C_2$ and $H_4$ to get the following:

$C:\;\;\; s_2 \;\;\;:$ Beth gets an A grade in science.

\begin{aligned}{} &\;\;\;\;H_1:\;\;\; s_1 \Rightarrow s_2\\ &\;\;\;\;H_2:\;\;\; s_3 \Rightarrow s_4\\ &\rule[0 pt]{130 pt}{0.5 pt}\\ &\therefore C_1:\;\;\;(s_1 \Rightarrow s_2)\land (s_3 \Rightarrow s_4) \end{aligned}

\begin{aligned}{} &\;\;\;\;C_1:\;\;\; (s_1 \Rightarrow s_2)\land (s_3 \Rightarrow s_4)\\ &\;\;\;\;H_3:\;\;\; s_1 \lor s_3\\ &\rule[0 pt]{130 pt}{0.5 pt}\\ &\therefore C_2:\;\;\;s_2 \lor s_4 \end{aligned}

\begin{aligned}{} &\;\;\;\;C_2:\;\;\; s_2 \lor s_4\\ &\;\;\;\;H_4:\;\;\; \neg s_4\\ &\rule[0 pt]{130 pt}{0.5 pt}\\ &\therefore \;C:\;\;\;s_2 \end{aligned}

Hypotheses

$H_1:\;\;\; p_1 \Rightarrow p_2 \;\;\;:$ If Steve believes in ghosts, then they are a reality for him.
$H_2:\;\;\; p_2 \Rightarrow p_3 \;\;\;:$ If ghosts are a reality for Steve, then they are affecting his life.
$H_3:\;\;\; \neg p_4 \Rightarrow \neg p_3 \;\;\;:$ If ghosts do not exist, then they are not affecting Steve’s life.
$H_4:\;\;\; p_1 \;\;\;:$ Steve believes in ghosts.

Conclusion

$p_4$ : Ghosts exist.

We use $H_1$ and $H_4$ to apply modus ponens and conclude $p_2$ .

$C_1:\;\;\; p_2 \;\;\;:$ Ghosts are a reality for Steve.

Now use $H_2$ and $C_1$ to apply modus ponens again and conclude $p_3$ .

$C_2:\;\;\; p_3 \;\;\;:$ Ghosts will affect Steve’s life.

Finally, take $H_3$ and $C_2$ to apply modus tollens and conclude $\neg (\neg p_4)$ , which is $p_4$ . Note that, $C_2 \equiv \neg (\neg p_3)$ .

$C:\;\;\; p_4 \;\;\;:$ Ghosts exist.

\begin{aligned}{} &\;\;\;\;H_1:\;\;\; p_1 \Rightarrow p_2\\ &\;\;\;\;H_4:\;\;\; p_1\\ &\rule[0 pt]{130 pt}{0.5 pt}\\ &\therefore C_1:\;\;\;p_2 \end{aligned}

\begin{aligned}{} &\;\;\;\;H_2:\;\;\; p_2 \Rightarrow p_3\\ &\;\;\;\;C_1:\;\;\; p_2\\ &\rule[0 pt]{130 pt}{0.5 pt}\\ &\therefore C_2:\;\;\;p_3 \end{aligned}

\begin{aligned}{} &\;\;\;\;H_3:\;\;\; \neg p_4 \Rightarrow \neg p_3\\ &\;\;\;\;C_2:\;\;\; p_3\\ &\rule[0 pt]{130 pt}{0.5 pt}\\ &\therefore \;C:\;\;\;p_4 \end{aligned}

Introduction

Propositional Logic

Basic Operations

Assessment-I

Propositional Toolkit

Assessment-II

Logical Reasoning

Assessment-III

Quantifiers and First Order Logic

Assessment-IV

Quantified Logical Reasoning

Assessment-V

Proving Theorems

Assessment-VI

Conclusion

Mathematical Proofs: Basics

What is a proof?

Examples

Science grade

Ghosts exist