Ch 3. Logic and Proofs
3.5 Proofs
Mathematics is built on a logical framework known as a mathematical system. This system consists of rules and components that allow us to derive new truths from established ones. Understanding the components of this system is essential before learning how to construct formal proofs.
A mathematical system is a structured framework consisting of:
- Undefined terms
- Definitions
- Axioms (or postulates)
- Rules of inference
- Theorems
These components work together to build logical arguments and establish mathematical truths.
Example 3.22
An undefined term is a basic concept that is not formally defined but is understood intuitively and used to define other terms.
Example 3.23
A definition gives precise meaning to a mathematical term using previously defined or undefined terms.
Example 3.24
An even integer is defined as an integer that is divisible by [latex]2[/latex]. Formally:
An integer [latex]n[/latex] is even if [latex]\exists[/latex]an integer [latex]k[/latex] such that [latex]n=2k[/latex]
An odd integer is defined as an integer that is not divisible by [latex]2[/latex]. Formally:
An integer [latex]n[/latex] is odd if [latex]\exists[/latex] an integer [latex]k[/latex] such that [latex]n=2k+1[/latex].
An axiom is a statement assumed to be true without proof. Axioms are foundational truths from which other statements are derived.
Example 3.25
In arithmetic, one axiom is:
For all integers [latex]a[/latex] and [latex]b[/latex], [latex]a + b = b + a \quad[/latex](commutativity of addition).
When a mathematical statement has been proven to be true using axioms, definitions, and previously proven results, it is referred to as a theorem.
Example 3.26
Theorem: The sum of two even integers is even.
Using the definition of even integers, this can be proven.
A lemma is a minor or intermediate result used to help prove a larger theorem.
Example 3.27
Lemma: If [latex]n[/latex] is even, then [latex]n^{2}[/latex] is even.
This lemma might be used in the proof of a more complex theorem involving even numbers.
When a statement follows directly from a theorem or lemma with little or no additional proof, it is referred to as a corollary.
Example 3.28
Corollary: If [latex]n[/latex] is even, then [latex]n+2[/latex] is even.
This follows directly from the theorem that the sum of two even numbers is even.
To establish a mathematical statement’s truth, a logical argument must be used, which is referred to as a proof.
Examples 3.29
Theorem: The sum of two even integers is also even.
Proof
Let [latex]a[/latex] and [latex]b[/latex] be two even integers. By the definition of even integers, there exist integers [latex]k[/latex] and [latex]m[/latex] such that
[latex]a=2k[/latex] and [latex]b=2m[/latex]
Now consider the sum
[latex]a + b = 2k + 2m = 2(k+m)[/latex]
Since [latex]k+m[/latex] is an integer (because the sum of two integers is an integer), we can write
[latex]a+b=2n[/latex], where [latex]n = k + m[/latex]
Thus, [latex]a + b[/latex] is divisible by [latex]2[/latex], and therefore even.
[latex]\square[/latex]
Direct Proofs
Many theorems in mathematics take the form of a universally quantified conditional statement:
[latex]\forall (x_{1}, x_{2}, \dots, x_{n}), \text{ if } P(x_{1}, x_{2}, \dots, x_{n}), \text{ then } Q(x_{1}, x_{2}, \dots, x_{n})[/latex]
This means the statement is true for every combination of values in the domain, provided that the conditional proposition is true.
[latex]\text{ If } P(x_{1}, x_{2}, \dots, x_{n}), \text{ then } Q(x_{1}, x_{2}, \dots, x_{n})[/latex]is true.
The method of proving this conditional proposition is called a direct proof, where you first assume that the hypothesis [latex]P[/latex] is true, and then, using a logical argument, show that the conclusion [latex]Q[/latex] must also be true.
Example 3.30
Theorem: If two integers are odd, then their product is also odd.
Proof
Suppose that the hypothesis, “two integers are odd”, is true by letting [latex]a[/latex] and [latex]b[/latex] be odd integers. By the definition of odd integers, there exist integers [latex]k[/latex] and [latex]m[/latex] such that
[latex]a=2k+1[/latex] and [latex]b=2m+1[/latex]
Then
[latex]ab=(2k+1)(2m+1)=4km+2k+2m+1=2(2km+k+m)+1[/latex]
Since [latex](2km+k+m)[/latex] is an integer, [latex]ab[/latex] is of the form [latex]2n+1[/latex], which is odd. This shows that the conclusion “their product is also odd” is true.
[latex]\square[/latex]
The proof in the next example uses the following definitions for the minimum and maximum of two real numbers.
The minimum of two real numbers [latex]a[/latex] and [latex]b[/latex], denoted by [latex]\min(a, b)[/latex], is defined as:
[latex]\min(a,b) = \begin{cases} a & \text{if } a \le b \\ b & \text{if } b < a \end{cases}[/latex]
The maximum of two real numbers [latex]a[/latex] and [latex]b[/latex], denoted by [latex]\max(a, b)[/latex], is defined as:
[latex]\max(a,b) = \begin{cases} a & \text{if } a \ge b \\ b & \text{if } b > a \end{cases}[/latex]
Example 3.31
Theorem: For any real numbers [latex]a[/latex] and [latex]b[/latex],
[latex]\min(a, b) + \max(a, b) = a + b[/latex]
Proof
Suppose that the hypothesis, “[latex]a[/latex] and [latex]b[/latex] are real numbers”, is true. If [latex]a < b[/latex], then [latex]\min(a, b) = a[/latex] and [latex]\max(a, b) = b[/latex], so [latex]\min(a, b) + \max(a, b) = a + b[/latex]. If [latex]b < a[/latex], then [latex]\min(a, b) = b[/latex] and [latex]\max(a, b) = a[/latex], so [latex]\min(a, b) + \max(a, b) = b + a = a + b[/latex]. In both cases, the sum is [latex]a + b[/latex]. Therefore, the identity holds for all real numbers [latex]a[/latex] and [latex]b[/latex] (i.e., the conclusion [latex]\min(a, b) + \max(a, b) = a + b[/latex] is also true).
[latex]\square[/latex]
Disproving a Universally Quantified Statement
A universally quantified statement has the form:
[latex]\forall x[/latex], if [latex]P(x)[/latex], then [latex]Q(x)[/latex]
To disprove such a statement, it is not necessary to show that it is false for all values of [latex]x[/latex]. Instead, it is enough to find a single value of [latex]x[/latex] for which the hypothesis [latex]P(x)[/latex] is true, but the conclusion [latex]Q(x)[/latex] is false.
This single value is called a counterexample: a specific case that shows that [latex]\forall x[/latex], if [latex]P(x)[/latex], then [latex]Q(x)[/latex] is false. It satisfied the hypothesis [latex]P(x)[/latex] but contradicts the conclusion [latex]Q(x)[/latex].
Example 3.32
Statement: For all integers [latex]n \geq 2[/latex], [latex]n[/latex] is prime if and only if [latex]n[/latex] is odd.
Disproof: We only need to disprove one direction of this bidirectional statement for the whole statement to be false. Consider the universally qualified statement:
if [latex]n \geq 2[/latex], [latex]n[/latex] is prime ([latex]P(n)[/latex]), then [latex]n[/latex] is odd ([latex]Q(n)[/latex])
Let [latex]n=2[/latex]. Then [latex]n[/latex] is prime ([latex]P(2)[/latex] is true), but [latex]n[/latex] is not odd ([latex]Q(2)[/latex] is false). This contradicts the “if, then” condition. Therefore, the statement is false.
Counterexample: [latex]n=2 \quad[/latex]
[latex]\square[/latex]
Example 3.33
Statement: For all real numbers [latex]a[/latex] and [latex]b[/latex], [latex]\min(a, b) + \max(a, b) = ab[/latex].
Disproof: Let [latex]a=2[/latex] and [latex]b=3[/latex]. Then [latex]\min(2, 3) = 2[/latex], [latex]\max(2, 3) = 3[/latex], and their sum is [latex]5[/latex]. But [latex]ab=6[/latex], so the statement is false.
Counterexample: [latex]a=2, b=3 \quad[/latex]
[latex]\square[/latex]
Proof by Contradiction
In mathematics and logic, a proof by contradiction (also known as an indirect proof) is a method of demonstrating the truth of a statement by assuming the opposite (its negation) and showing that this assumption leads to a contradiction—a logical inconsistency or impossibility. Since the assumption results in an illogical or false outcome, the original statement must be true.
A contradiction is a situation where two or more statements cannot all be true simultaneously. For example, asserting that a number is both even and odd leads to a contradiction.
A proof by contradiction is a proof technique where you assume the negation of the statement to be proved and derive a contradiction. This contradiction proves that the original statement must be true.
An indirect proof is a general term for any proof that does not prove a statement directly. Proof by contradiction is a type of indirect proof.
To prove a proposition [latex]p[/latex] using contradiction:
- Assume [latex]\neg p[/latex] (the opposite of what you want to prove).
- Show that this assumption logically leads to a contradiction.
- Conclude that [latex]\neg p[/latex] must be false, and therefore [latex]p[/latex] is true.
Example 3.34
Statement: The sum of an odd integer and an even integer is odd.
Proof
Let [latex]a[/latex] be an odd integer and [latex]b[/latex] be an even integer. Suppose, for contradiction, that [latex]a+b[/latex] is even. By the definitions of odd and even integers, there exist integers [latex]m[/latex] and [latex]k[/latex] such that
[latex]a+b=(2m+1)+2k=2(m+k)+1[/latex]
This result is clearly odd, since it is of the form [latex]2n+1[/latex]. But we assumed the sum was even, which is a contradiction. In conclusion, the sum must be odd, as claimed.
[latex]\square[/latex]
Example 3.35
Statement: There is no greatest real number.
Proof
Assume, for contradiction, that there exists a greatest real number, say [latex]m[/latex], such that for all real numbers [latex]x[/latex], [latex]x < m[/latex]. Now consider the number [latex]m+1[/latex]. Clearly, [latex]m+1>m[/latex], and [latex]m+1[/latex] is a real number. But we assumed [latex]m[/latex] was the greatest real number, which is a contradiction. In conclusion, there is no greatest real number, as claimed.
[latex]\square[/latex]
The following example uses the definitions of rational and irrational numbers.
A number [latex]r[/latex] is rational if there exist integers [latex]p[/latex] and [latex]q[/latex] with [latex]q \neq 0[/latex] such that [latex]r = \frac{p}{q}[/latex].
A number [latex]x[/latex] is irrational if there do not exist integers [latex]p[/latex] and [latex]q[/latex] with [latex]q \neq 0[/latex] such that [latex]x = \frac{p}{q}[/latex].
Example 3.36
Statement: [latex]\sqrt{2}[/latex] is irrational.
Proof
Assume, for contradiction, that [latex]\sqrt{2}[/latex] is a rational number. Then it can be written as a fraction [latex]\frac{p}{q}[/latex], where [latex]p[/latex]and [latex]q[/latex] are integers with [latex]q \neq 0[/latex], and the fraction is in lowest terms. That is,
[latex]\sqrt{2} = \frac{p}{q} \rightarrow 2 = \frac{p^{2}}{q^{2}} \rightarrow p^{2} = 2q^{2}[/latex]
This implies [latex]p^2[/latex] is even, so [latex]p[/latex] must be even. Let [latex]p=2k[/latex], for some integer [latex]k[/latex]. Then
[latex]p^{2} = \left( 2k \right) ^{2} = 4k^{2} = 2q^{2} \rightarrow q^{2} = 2k^{2}[/latex]
So, [latex]q^2[/latex] is also even, and therefore [latex]q[/latex] is even. Now, both [latex]p[/latex] and [latex]q[/latex] are even, meaning they share a factor of [latex]2[/latex]. But this contradicts our assumption that [latex]\frac{p}{q}[/latex] is in lowest terms.
In conclusion, our assumption must be false, so [latex]\sqrt{2}[/latex] is irrational.
[latex]\square[/latex]
Proof by Cases
A proof by cases is a method of proving a statement by considering all possible scenarios (or "cases") that cover every possibility. By showing that the conclusion is true in every case, it shows that the overall statement is true.
Say we want to prove the following statement:
[latex]\left( p_{1} \lor p_{2} \lor \dots \lor p_{n} \right) \rightarrow q[/latex]
Then it is easier to prove the alternative statement:
[latex]\left( p_{1} \rightarrow q \right) \land \left( p_{2} \rightarrow q \right) \land \dots \land \left( p_{n} \rightarrow q \right)[/latex]
To understand this, if [latex]q[/latex] follows from each [latex]p_{i}[/latex], and one of the [latex]p_{i}[/latex] is guaranteed to be true, then [latex]q[/latex] must be true.
When all logically possible cases are examined (with no omissions), the proof by cases is referred to as an exhaustive proof.
Example 3.37
Statement: For any integer [latex]n[/latex], [latex]n^{2} \geq 0[/latex].
Proof
We consider all cases for the integer [latex]n[/latex].
Case 1: [latex]n = 0 \rightarrow n^{2} = 0 \geq 0[/latex]
Case 2: [latex]n > 0 \rightarrow n^{2} > 0[/latex]
Case 3: [latex]n < 0 \rightarrow n^{2} = \left( -n \right) ^{2} > 0[/latex]
In all cases, [latex]n^{2} \geq 0[/latex].
[latex]\square[/latex]
The following example uses absolute values. The absolute value of a real number [latex]x[/latex], denoted [latex]|x|[/latex] is defined as:
[latex]|x| = \begin{cases} x & \text{if } x \ge 0 \\ -x & \text{if } x < 0 \end{cases}[/latex]
Example 3.38
Statement: For all real numbers [latex]x[/latex], [latex]|x| \geq x[/latex].
Proof
We consider all cases for the real number [latex]x[/latex].
Case 1: [latex]x \geq 0 \rightarrow |x| = x[/latex], so [latex]|x| \geq x[/latex]
Case 2: [latex]x < 0 \rightarrow |x| = -x[/latex] and since [latex]x < 0, -x > x[/latex], so [latex]|x| > x[/latex]
In all cases, [latex]|x| \geq x[/latex].
[latex]\square[/latex]
Example 3.39
Statement: Every card in a standard 52-card deck is either red or black.
Proof
A standard 52-card deck has four suits: hearts, diamonds, clubs, and spades.
Case 1: Card is a heart [latex]\rightarrow[/latex] red
Case 2: Card is a diamond [latex]\rightarrow[/latex] red
Case 3: Card is a club [latex]\rightarrow[/latex] black
Case 4: Card is a spade [latex]\rightarrow[/latex] black
These are all the suits in a standard 52-card deck. Each suit maps to either red or black, so the statement is true for all cards.
[latex]\square[/latex]
Proofs of Equivalence
A proof of equivalence shows that two logical (or mathematical) statements are equivalent, meaning each one implies the other. This involves proving the statement in one direction and then proving the statement in the other direction:
[latex]p \leftrightarrow q[/latex] by proving [latex]p \rightarrow q[/latex] and [latex]q \rightarrow p[/latex]
Example 3.40
Statement: An integer [latex]n[/latex] is odd if and only if [latex]n^{2}[/latex] is odd.
Proof
Let [latex]n[/latex] be an integer and suppose it is odd, such that [latex]n=2k+1[/latex]. Then
[latex]n^{2} = \left( 2k + 1 \right) ^{2} = 4k^{2} + 4k + 1 = 2 \left( 2k^{2} + 2k \right) + 1[/latex]
which is odd.
Conversely, suppose [latex]n^{2}[/latex] is odd. Additionally, suppose [latex]n[/latex] is even, such that [latex]n=2k[/latex]. Then [latex]n^{2} = 4k^{2}[/latex] is even, which is a contradiction. So, [latex]n[/latex] must be odd.
Hence, [latex]n[/latex] is odd if and only if [latex]n^{2}[/latex] is odd.
[latex]\square[/latex]
Example 3.41
Statement: For all real numbers [latex]x[/latex], [latex]|x|=x[/latex] if and only if [latex]x \geq 0[/latex].
Proof
Let [latex]x[/latex] be a real number, and suppose [latex]|x|=x[/latex]. By the definition of absolute value, [latex]x \geq 0[/latex].
Conversely, suppose [latex]x \geq 0[/latex]. By the definition of absolute value, [latex]|x|=x[/latex].
Therefore, [latex]|x|=x[/latex] if and only if [latex]x \geq 0[/latex].
[latex]\square[/latex]
Existence Proofs
An existence proof is a type of mathematical proof that shows that at least one element with a certain property exists. These proofs do not always construct the element explicitly; sometimes, they show that it must exist.
There are two types. The first is constructive, which provides an explicit example.
Example 3.42
Statement: There exists a real number [latex]x[/latex] such that [latex]x^{2} = 2[/latex].
Proof: Let [latex]x = \sqrt{2}[/latex]. Then [latex]x^{2} = 2[/latex]. So, such a number exists.
[latex]\square[/latex]
Example 3.43
Statement: There exists an even prime number.
Proof: The number 2 is even and prime (divisible only by 1 and 2). Therefore, such a number exists.
[latex]\square[/latex]
The second is non-constructive, as it proves existence without providing a specific example.
The following example uses the definition of an average. For a list of numbers [latex]x_{1}, x_{2}, \dots, x_{n}[/latex], we define the average to be
[latex]\bar{x} = \frac{x_{1} + x_{2} + \dots + x_{n}}{n}[/latex]
Example 3.44
Statement: If you have a list of numbers (like test scores, prices, or measurements), then at least one number is less than or equal to the average, and at least one number is greater than or equal to the average.
Proof
Suppose you have a list of numbers [latex]x_{1}, x_{2}, \dots, x_{n}[/latex]. We’ll prove this by showing two things:
a) at least one number is less than or equal to the average
b) at least one number is greater than or equal to the average
a) Let’s assume (for contradiction) that every number in the list is greater than the average. That means
[latex]x_{1} > \bar{x}, x_{2} > \bar{x}, \dots, x_{n} > \bar{x}[/latex]
Adding up all these inequalities gives
[latex]x_{1} + x_{2} + \dots + x_{n} > n \cdot \bar{x}[/latex]
But this is impossible. By the definition of average, we have
[latex]x_{1} + x_{2} + \dots + x_{n} = n \cdot \bar{x}[/latex]
Hence, we have a contradiction. That means not all the numbers can be greater than the average. Therefore, at least one number must be less than or equal to the average.
b) Now let’s assume (for another contradiction) that every number in the list is less than the average. That means
[latex]x_{1} < \bar{x}, x_{2} < \bar{x}. \dots, x_{n} < \bar{x}[/latex]
Adding up all these inequalities gives
[latex]x_{1} + x_{2} + \dots + x_{n} < n \cdot \bar{x}[/latex]
But this is impossible by the definition of average, so we have another contradiction. That means not all the numbers can be less than the average. So at least one number must be greater than or equal to the average.
In conclusion, in any list of numbers, some numbers are less than or equal to the average, and some numbers are greater than or equal to the average.
[latex]\square[/latex]
Real-World Example 3.5: Verifying Business Logic with Proof
A company offers a discount policy: “If a customer buys two or more items, and the total cost is over $100, they get a 15% discount.”
Define [latex]p[/latex] as the proposition “The customer buys two or more items”, [latex]q[/latex] as the proposition “The total cost is over $100”, and [latex]r[/latex] as the proposition “The customer gets a 15% discount”.
The business rule can be written as [latex](p \land q) \rightarrow r[/latex]. Now suppose a customer buys 3 items totalling $120. We claim that the discount should apply.
Proof
The proposition [latex]p[/latex] is true since 3 items are greater than or equal to 2 items. The proposition [latex]q[/latex] is true since $120 is greater than $100. Therefore, [latex]p \land q[/latex] is true. By Modus Ponens (see Section 3.3), since [latex](p \land q) \rightarrow r[/latex] and [latex]p \land q[/latex] is true, then [latex]r[/latex] is true.
Therefore, the customer should receive the discount.
[latex]\square[/latex]
