A.1: Mathematical Proofs and Logic

Mathematical Logic

The phrases if, only if, and if and only if are similar, but they have subtle differences. Let \(A\) and \(B\) be logical statements or propositions. The statement \(B\) if \(A\) means \(A\) is a sufficient condition for \(B.\) When \(A\) is true, \(B\) must also be true; symbolically, \(A \implies B.\) (But when \(B\) is true, \(A\) doesn't need to be true.) Conversely, \(B\) only if \(A\) says \(A\) is a necessary condition for \(B;\) that is, \(B\) is only possible when \(A\) is true. Thus, when \(B\) is true, \(A\) must also be true. We therefore say \(A\) is implied by \(B\)—mathematically, \(A \impliedby B.\) (Yet when \(A\) is true, \(B\) doesn't need to be true, so \(A\) does not necessarily imply \(B.\)) Combining the previous two logical statements, \(B\) if and only if \(A\) is the most restrictive statement. It means \(A\) both implies and is implied by \(B\)—that is, \(A \iffArrow B.\) Accordingly, a bidirectional relationship exists between \(A\) and \(B \col\) either both are true or both are false.

LOGICAL STATEMENTS

Statement	Notation	Meaning
\(B\) if \(A\)	\(A \implies B\)	\(A\) is a sufficient condition for \(B\)
\(B\) only if \(A\)	\(A \impliedby B\)	\(A\) is a necessary condition for \(B\)
\(B\) if and only if \(A\)	\(A \iffArrow B\)	\(A\) and \(B\) are either both true or both false

Many logical statements remain correct when you replace if and only if with if or only if, but doing so sacrifices precision. In mathematics, if and only if occurs frequently with definitions. The following statements exemplify the uses of these statements:

The children will fall asleep only if a bedtime story is read. (Reading the story is a necessary condition for the children to fall asleep, but just reading might not guarantee it.)
You will feel better if you take some medication. (Taking the medication is a sufficient condition to ensure you feel better, but there might be other remedies.)
\(f\) is greater than \(g\) on \([a, b]\) if and only if \(f(x) \gt g(x)\) on \([a, b].\) (These statements are synonymous with each other.)
The series \(\sum a_n\) is absolutely convergent if and only if \(\sum \abs{a_n}\) is convergent. (In this definition, either \(\sum a_n\) is absolutely convergent and \(\sum \abs{a_n}\) is convergent, or both are false.)
A function \(f\) is differentiable only if \(f\) is continuous. (Continuity is a necessary, but not sufficient, condition for differentiability. Without continuity, differentiability can't be established.)
A function \(f\) is continuous if \(f\) is differentiable. (Differentiability is a sufficient, but not necessary, condition for continuity. The converse of this statement—\(f\) is differentiable if \(f\) is continuous—is generally false.)

Types of Mathematical Proofs

A mathematical proof is an argument that logically guarantees the truth of some statement. There are many types of mathematical proofs, but we only cover a few. The simplest type is a direct proof, using a combination of definitions and theorems to validate some conclusion. Another method is a Proof by Contradiction, in which we derive a contradiction, and therefore conclude the assumption (the negation) is false—so the original statement must be true. Finally, to construct a Proof by Induction, we first prove a simple base case, then assume a general rule, and lastly show that the general rule implies the next case.

EXAMPLE 1

Prove that the sum of two even integers is even.

Let's use a direct proof. By definition, a number is even if and only if it's divisible by \(2.\) Let two even integers be \(m\) and \(n;\) then they can be written as \(m = 2a\) and \(n = 2b\) for some integers \(a\) and \(b.\) But \[ \ba m + n &= 2a + 2b \nl &= 2(a + b) \pd \ea \] The quantity \(2(a + b)\) is even since it is divisible by \(2,\) so the sum of two even integers is even.

EXAMPLE 2

Prove that the following equation has no solutions: \[\frac{x + 4}{x + 5} = 1 \pd\]

Let's use a Proof by Contradiction by first assuming a solution does exist. Multiplying both sides by \((x + 5)\) gives \[ \ba x + 4 &= x + 5 \nl 4 &= 5 \pd \ea \] We have a contradiction: \(4 = 5\) is never true. Hence, our assumption was false, so no value of \(x\) satisfies \[\frac{x + 4}{x + 5} = 1 \pd\]

EXAMPLE 3

For integers \(n \geq 3,\) prove that \(2^n \gt 2n.\)

Let's use a Proof by Induction. We first prove the statement for the base case, \(n = 3 \col\) \[ \ba 2^3 &\gt 2(3) \nl 8 &\checkAbove{\gt} 6 \pd \ea \] Now we assume that \(2^n \gt 2n\) is true for any \(n = k,\) where \(k \geq 3.\) Our goal is to prove that the inequality is also true for \(n = k + 1\)—that is, \(2^{k + 1} \gt 2 (k + 1).\) Starting with the induction hypothesis \(2^k \gt 2k,\) multiplying both sides by \(2\) yields \[ \ba 2 \cdot 2^k &\gt 2 \cdot 2k \nl 2^{k + 1} &\gt 4k \pd \ea \] Observe that \(4k \gt 2(k + 1)\) because \(4k \gt 2k + 2\) \(\iffArrow 2k \gt 2\) \(\iffArrow k \gt 1,\) which is true since we are given \(k \geq 3.\) Hence, \[2^{k + 1} \gt 4k \gt 2(k + 1) \pd\] Accordingly, \(2^n \gt 2n\) is also true for \(n = k + 1.\) By mathematical induction, the given inequality is true for all \(n \geq 3.\)