Section2.3Proofs

As we stated both in the preface as well as earlier in this chapter, our working definition of mathematics is that it is the application of inductive and deductive logic to a system of axioms. It is not our purpose in this text to formalize the logical procedure required to provide formalistic proofs. Rather, we wish to arm the student with the basic logic and methods of attack used to form convincing arguments of the validity of the statements encountered in a reasonably careful study of the foundations of mathematics.

Since we will need a working definition of the word “proof,” we agree that a proof is a logical sequence of steps which validate the truth of the proposition in question. In this vein the reader should review those statements which we have proven and note that usually we merely showed that certain definitions were satisfied. For example, when we proposed certain statements were equivalent, we established that they had the same truth value. Surely, as we proceed further, we will be forced to provide proofs which require longer and at times more subtle sequences of logical statements. Our endeavor, as well as yours, will be to convince the reader of the truth of the propositions in question.

There are, however, some general approaches to proofs which are based on the various tautologies and contradictions presented in Section 1.3. Most theorems are merely conditional statements of the form, “If $p\text{,}$ then $q\text{.}$” Certainly, $p$ and $q$ might themselves be complicated compound statements, but that should not be allowed to cloud the issue at this time, so let us consider a typical theorem and a few general types of proof.

Subsection2.3.1Method 1: Direct Proof

Recall from the truth table of a conditional sentence that when $p$ is false, $q$ can have any truth value and the conditional will still be true. Thus, we need only consider the case when $p$ is true and argue that $q$ must also be true. Hence, we assume $p$ is true and by applying various known tautologies and apparent implications, we argue $q$ is also true.

We will prove the statement: “Let $m$ and $n$ be integers. If $m$ is even and $n$ is even, then $m + n$ is even.”

Proof. Assume the hypothesis, “$m$ is even and $n$ is even” is true. By definition of conjunction, it follows that the component statements “$m$ is even” and “$n$ is even” are true. But since even numbers are by definition multiples of $2\text{,}$ there must exist integers $r$ and $s$ such that $m = 2r$ and $n = 2s\text{.}$ Then substitution yields

\begin{equation*} m + n = 2r + 2s = 2(r + s). \end{equation*}

Since the set of integers is closed under addition, the number $r + s$ is also an integer. Thus, we have written $m + n$ as $2$ times an integer, so we have shown $m + n$ is even. That is, the conclusion “$m + n$ is even” is true whenever the hypothesis “$m$ is even and $n$ is even” is true.

We know that $[\negate(p \rightarrow q)] \leftrightarrow [p \, \wedge (\negate q)]$ by part (5) of Theorem 1.3.6. If we begin by assuming $p \, \wedge (\negate q)$ is true and reach a contradiction, it must be the case that $p \, \wedge (\negate q)$ is false. But $p \, \wedge (\negate q)$ being false and yet equivalent to $\negate(p \rightarrow q)$ implies that $\negate(p \rightarrow q)$ is also false or $p \rightarrow q$ is true. Therefore, in proving  by contradiction, we assume $p$ and $\negate q$ are both true and reach a contradiction. This logically shows that the statement $p \rightarrow q$ as argued above.

We will prove the statement: “Let $x$ and $y$ be positive real numbers. If $x \neq y\text{,}$ then $x^2 \neq y^2\text{.}$”

Proof. For positive real numbers $x$ and $y\text{,}$ assume $x \neq y$ and $x^2 = y^2\text{.}$ Then

\begin{equation*} x^2 - y^2 = (x - y)(x + y) = 0. \end{equation*}

Hence, either $x - y = 0$ or $x + y = 0\text{.}$ We assumed that $x \neq y\text{,}$ so $x - y \neq 0\text{.}$ Consequently, $x + y = 0$ or $x = -y\text{,}$ which contradicts the assumption that both $x$ and $y$ are positive. Therefore, $x^2 \neq y^2$ if $x \neq y\text{.}$

Subsection2.3.3Method 3: Proof by Contrapositive (Indirect Proof)

Since we know that $(p \rightarrow q) \leftrightarrow ( \negate q \rightarrow \negate p )$ by part (8) of Theorem 1.3.6, we can prove $\negate q \rightarrow \negate p$ instead of $p \rightarrow q\text{.}$ That is, we assume that $\negate q$ is true and argue that $\negate p$ is true. So essentially, a proof by contraposition is a direct proof applied to a statement that is equivalent to the one we wish to prove.

As in Example 2.3.3, we will prove the statement: “Let $x$ and $y$ be positive real numbers. If $x \neq y\text{,}$ then $x^2 \neq y^2\text{.}$” However, we will directly prove the equivalent statement, “If $x^2 = y^2\text{,}$ the $x = y\text{.}$”

Proof. Assume that $x^2 = y^2\text{.}$ Then

\begin{equation*} x^2 - y^2 = (x - y)(x + y) = 0. \end{equation*}

Consequently, $x - y = 0$ or $x + y = 0\text{.}$ Since both $x$ and $y$ are positive, $x + y$ must also be positive. Hence, $x + y \neq 0\text{.}$ Therefore, $x - y = 0$ or $x = y\text{.}$

Subsection2.3.4Counterexamples

We can use a counterexample to prove that a statement is false. In considering the truth value of a conditional statement $p \rightarrow q\text{,}$ we would know the statement is false if we could find a single example for which $p$ is true but $q$ is false.

Consider the statement: “Let $m$ and $n$ be integers. If $m$ is even, then $m + n$ is even.” By considering a single example such as $m = 2$ and $n = 3\text{,}$ and observing that

\begin{equation*} m + n = 2 + 3 = 5 \end{equation*}

is not even, we have established the conditional statement is false.

Exercises2.3.5Exercises

1.

Let $m$ and $n$ represent integers. Prove by the direct method.

1. If $n$ is even, then $-n$ is even.
2. If $n$ is odd, then $-n$ is odd.
3. If $m$ is even and $n$ is odd, then $m + n$ is odd.
4. If $m$ is odd, then $m^2 + 1$ is even.
2.

Using facts from Exercise 2.3.5.1, prove the given statement by the method indicated.

If $m + n$ is even and $m$ is odd, then $n$ is odd.

1. Direct method.
2. Contraposition.