Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
The Book of
Foundational Mathematics
1 Propositional Logic
2 Arguments and Proof
- The Structure of Basic Arguments
- Rules of Inference
- Using the Rules of Inference
- Logically Equivalent Arguments
- Invalid Arguments
- Universal Specification
- Universal Generalization
- Axioms, Definitions, Theorems, and Proofs
- Proof Technique: Direct Proofs
- Proof Technique: Indirect Proofs
- Proof Technique: Contradiction
- Mistakes in Proofs
- Proof Technique: Equivalence
4 Relations and Functions
Appendix
Mistakes in Proofs
So far, we’ve seen three different proof techniques: one direct technique, and two indirect techniques. Application of those techniques requires a close adherence to the rules of inference discussed throughout this chapter.
However, if we make an argument that uses an invalid inference rule, then we have an invalid argument, and hence an invalid proof. In this section, we discuss a few of the most common types of errors that can be made.
Violating Hypotheses of a Theorem or Axiom
Remember that a theorem guarantees that some result will hold when a certain collection of premises are satisfied. If even one premise fails to be true in a certain scenario, then the theorem no longer applies. The conclusion of the theorem may still be true, but not because of the theorem itself. Consider the following “proof” showing that 1 = 2:
Let a and b be real numbers such that a = b.
| a = b | Initial Premise. | |
| ⟺ | ab = b2 | Multiply both sides by b. |
| ⟺ | 0 = ab – b2 | Move b2 to the other side of the equation. |
| ⟺ | ab = 2ab – b2 | Add ab to both sides. |
| ⟺ | ab – b2 = 2ab – 2b2 | Subtract b2 from both sides. |
| ⟺ | b(a – b) = 2ab – 2b2 | Factor out the b from the left-hand side. |
| ⟺ | b(a – b) = 2b(a – b) | Factor out the 2b from the right-hand side. |
| ⟺ | b = 2b | Cancel out the common (a – b) term. |
| ⟺ | 1 = 2 | Cancel out the common b term. |
Clearly something went wrong somewhere because obviously 1 ≠ 2.
The first thing we do is check the arithmetic on each line. In this particular case, the arithmetic checks out, so that’s not the issue.
Take a close look at lines 7-8 in the above table. Notice how we went from
b(a – b) = 2b(a – b)
in line 7 to
b = 2b
in line 8. We did that by canceling out the (a – b) term on both sides of the equation. To cancel out this common term, we simply divided both sides of the equation by (a – b).
Remember that division by 0 is undefined. For example, how would we divide 100 objects into 0 groups? Always be sure that any expression you divide by is not equal to 0.
Figure 2.12.1: Division by 0 is undefined.
The problem is that we initially said that a = b. This means that a – b = 0. So, when we divide both sides of the equation on line 7 by the quantity (a – b), we were really dividing both sides of the equation by 0.
However, division by 0 is undefined, and is not a valid arithmetical manipulation of an equation. Even though the arithmetic was done “correctly”, the actual steps being taken were invalid.
It is common when solving equations to cancel out like terms, and there is a theorem to help us out in such a pursuit:
Theorem 2.12.1
If a ≠ 0, and ab = ac, then
b = c.
When a ≠ 0, the result comes about by simply dividing both sides of the equation by a and simplifying.
There are two premises to this theorem:
| p1: | a ≠ 0 |
| p2: | ab = ac |
If these premises are true, the the theorem guarantees that the following conclusion is true:
| c: | b = c |
Now, what happens when we try to apply this theorem to the above proof on lines 7-8?
| p1: | a – b ≠ 0 |
| p2: | b(a – b) = 2b(a – b) |
What happens is that premise p1 is false. Thus, this theorem does not guarantee that b = 2b.
To be clear, it may still be the case that b = 2b in some instances, like when b = 0:
| b = 2b | |
| ⟺ | 0 = 2(0) |
| ⟺ | 0 = 0 |
However, the truth of b = 2b is not guaranteed by Theorem 2.12.1, but we would have to instead appeal to an entirely different theorem.
Arguing by the Converse or Inverse
As described in this section, we noted that an implication is not in general logically equivalent to its converse or inverse (though in some cases it may be.)
Thus, we can’t in general deduce the truth of a proposition by examining the truth of its converse or inverse.
Example 2.12.1
Suppose we knew that n2 > 0. Can we conclude that that n > 0?
We know that if n > 0 then n2 > 0 (the converse) for two reasons. The first reason is that we’re squaring a positive number. A positive number times a positive number is also a positive number. The second reason we know that n2 > 0 is because even if n were negative, squaring n would give us a negative number times a negative number, which results in a positive number.
Thus, since n > 0 ⟹ n2 > 0, can we conclude that n2 > 0 ⟹ n > 0?
No because as we discussed, a negative number multiplied by a negative number yields a positive number. If n = -1, then n2 = 1.
This is a counter example to the proposition
n2 > 0 → n > 0
hence we have that
n2 > 0 ⇏ n > 0.
Example 2.12.2
Suppose we know that n < 0. Can we conclude that n2 < 0?
We know that when n ≥ 0, then n2 ≥ 0 (the inverse.) However, as discussed in Example 2.12.1, multiplying a negative number by a negative number always yields a positive number.
Hence, we have that n2 is always greater than or equal to 0. There is no real number x such that x2 < 0.
For a counter-example, consider the case when n = -1:
| n2 | = | n*n |
| = | (-1) * (-1) | |
| = | 1 |
Circular Reasoning
One particular type of error that occasionally occurs is to implicitly assume the truth of the conclusion, instead of deducing its truth from the premises. Even though it sounds silly to prematurely assume the truth of the conclusion, consider that many proofs require multiple paragraphs of carefully written out logic. It can be easy to mistake the conclusion for a premise, and to start working out faulty results.
It’s a subtle mistake, but a mistake nonetheless.
Example 2.12.3
Consider the following “proof” of the claim
n2 is even ⟹ n is even.
Suppose n2 is even. This means there exists some integer k such that
n2 = 2k.
Let n = 2ℓ for some integer ℓ, then we have that
| n2 | = | n * n |
| = | (2ℓ) *(2ℓ) | |
| = | 4ℓ2 | |
| = | 2(2ℓ2) | |
| = | 2k |
Thus we must have that k = 2ℓ2. Thus, since n = 2ℓ where ℓ is an integer, then n is even by definition as desired.
This result may seem convincing, as we’ve supposedly shown that n was double some other integer. However, after noting that n2 = 2k (invoking the definition of an even integer), we asserted that n = 2ℓ for some integer ℓ.
But that’s what we’re trying to show in the first place! We assumed that n was even, and hence arrived at the conclusion that… n was even. Obviously, if we assume that n is even, then we conclude that n is even.
After we assumed n was even, we did a little bit of algebraic work to show that k = 2ℓ2. However, this result is meaningless because it relies on us making an assumption about n that we haven’t logically justified.
It’s worth pointing out that it is true that if n2 is even, then n is in fact even. This can be proven, however, the proof supplied here is not a valid proof of the fact.
As demonstrated by Example 2.12.3, one way this type of error occurs is that the assumption is quickly stated, and then a bunch of results are derived afterwards. When reading the attempted proof, we may gloss over any assumptions being made, and focus on the results derived from those assumptions. This is where we may miss the fact that we’;re assuming the truth of the conclusion, which is why this mistake is easier to make than one may initially think.
Always be on the lookout for unwarranted assumptions in proposed proofs of statements.
Abusing Universal Generalization
Universal Generalization is a technique used to prove that a universally quantified statement is true. We start by taking a specific, but arbitrarily chosen element from the universe of discourse, and manipulate that element in order to show that some result is true of that element. Since that element was arbitrarily chosen, any derived results hold for any element from the universe we pick, and hence the result holds for all elements in the universe.
Typically, we use a variable to represent the arbitrarily chosen element. This means that since the value is unknown, the only thing we know about it is what is known about every element within the universe.
Example 2.12.4
Suppose we want to prove a result that is true of all even integers.
We can use n as a placeholder for any even integer we may potentially chose. And since n is even, we know that there is some integer k such that
n = 2k.
However, which even integer is n? It could be 2, or it could be 4, or 788, or 5667454, or even -100918. We don’t know because n is arbitrarily chosen. All we know is that n is double some other other integer k. The integer k may be even, or it may be odd, but all we know is that k is some integer.
When doing any manipulation on k, anything that works for all integers is valid.
Problems may arise when the element we pick is not arbitrarily chosen.
Example 2.12.5
Consider the following invalid proof that
For all integers n, n = n2.
Consider n = 0, then we have that
0 = 02.
Since the element we picked satisfies the equation n = n2, the result holds by invoking Universal Generalization as desired.
Note we could pick another element such as n = 1 because 1 = 12 as well.
Was our choice for n arbitrary? No, because we used knowledge about the number 0 that is shared by only one other integer, namely 1, and which is not shared by any other integer. That fact that 0 = 02 and 1 = 12 does not show that all integers are equal to their squares.
For example 2 ≠ 22 = 4.
Not every integer n has the property that n = n2, and thus we can’t use that property when trying to determine if n = n2 when trying to invoke Universal Generalization. What we do with n must be true for all integers, not just 0 and 1.