SUNY Geneseo Department of Mathematics
Wednesday, February 10
Math 239 03
Spring 2021
Prof. Doug Baldwin
Proving a conditional statement false? All you need to do is show that it’s possible for the hypothesis to be true but the conclusion false. Similarly, to prove a conditional true, all you have to do is show that the hypothesis being true necessarily means the conclusion is too.
Conditional statements and vacuous truth? “Vacuous truth” is the idea that any statement at all is true of all members of an empty set; for example “all the pink unicorns in the classroom are dancing on the desks” is true because there are no pink unicorns in the classroom. Such statements can be rephrased as conditionals that are true because their hypotheses are false, for example “if x is a pink unicorn in the classroom, then x is dancing on (one of) the desks.”
The Math Learning Center is open, and offers tutoring for this course. See the MLC Web site for details (https://www.geneseo.edu/math/mlc).
Based on the beginning of section 1.2 (mainly) in the textbook, and this direct proof discussion.
An example from the discussion.
This example has a nice proof, in the form of a “know-show” table, in the discussion.
Another example from the discussion, with some good ideas but not quite a complete proof, in the discussion.
Formally, the conjecture is that if x and y are odd integers, then x + y is an even integer.
Labelling steps in a know-show table with “P” and “Q” comes from the common shorthand for a generic conditional, “if P then Q” or “P → Q”
| Step | Know | Reason |
|---|---|---|
| P | x and y are odd integers | Hypothesis |
| P1 | x = 2n+1, y = 2m+1, for some integers n & m | Definition of odd |
| x+y = 2n + 1 + 2m + 1 | Algebra | |
| = 2n + 2m + 2 | Algebra | |
| = 2(n + m + 1) | Factor | |
| n + m + 1 = q is an integer | Closure of integers | |
| x + y = 2q | Substitution | |
| Q | x + y is an even integer | Definition of even |
| Step | Show | Reason |
Another discussion example that has a good start online but not a complete proof yet.
Formally, if x is an even integer and y is an odd integer, then x - y is odd.
| Step | Know | Reason |
|---|---|---|
| P | x is even, y is odd | Hypothesis |
| x = 2m, y = 2n+1 for some integers n, m | Definition of even, odd | |
| x - y = 2m - (2n+1) | Algebra | |
| P3 | x - y = 2m - 2n - 1 | Algebra |
| = 2m - 2n - (2-1) | 1 = 2 - 1 | |
| = 2m - 2n - 2 + 1 | Algebra | |
| = 2(m-n-1) + 1 | Factor | |
| m-n-1 = q is an integer | Closure of integers | |
| x - y = 2q + 1 | Substitution | |
| Q | x - y is odd | Definition of odd |
| Step | Show | Reason |
In our first attempt at this, we got to about step P3, and then tried to simplify x - y to 2(m-n) - 1. A few steps later we got stuck, because we could express x - y as 2q - 1 for some integer q, but not as 2q + 1, and you can’t just replace “+ 1” with “- 1” in the definition of odd integer (at least not unless you can prove why the 2 forms are equivalent). At this point we backed up back to step P3 and continued as shown above. This was a nice example of how proofs really get discovered, including heading down what turn out to be false paths — there’s nothing wrong with that happening, you just back up and try a different approach when it becomes clear that the one you’re using won’t work.
If you’re trying to do a proof involving an equation, i.e., trying to show that the left-hand side equals the right-and side, is it OK to manipulate both sides in parallel until they become the same thing?
Yes and no.
Yes, because such reasoning can often lead you to discover the relationships that make the equation true. An adaptation of know-show tables even helps you organize your thinking while doing this.
For example, prove that if x is real, then x2 + (x+1)2 = 2(x2+x+1) - 1
| Step | Know | Reason |
|---|---|---|
| Start | x2 + (x+1)2 | |
| = x2 + x2 + 2x + 1 | FOIL | |
| = 2x2 + 2x + 1 | Algebra | |
| = 2x2 + 2x + 1 | ||
| = 2x2 + 2x + 2 - 1 | 1 = 2 - 1 | |
| End | = 2(x2+x+1) - 1 | Algebra |
| Step | Show | Reason |
We constructed this series of equations by starting with 2(x2+x+1) - 1 and working backwards via a few algebra steps that were easy to spot. When we ran out of easy-to-see steps, we turned the working forward from x2 + (x+1)2, in particular by multiplying out the (x+1)2 term and simplifying. When we realized that each expression had simplified to the same form, we were done.
But the “no” answer to the question is because this is actually considered a terrible way to write formal proofs. The reason is that when you work on both sides of an equation in parallel, it’s very easy to fall into the trap of doing some step that would only be valid if the two sides actually were equal, and the whole point of having to prove it is that they might not be. Thus, even if you discover the proof by “working from both ends towards the middle,” you should write it as reasoning from one side of the equation through to the other. This is a chance to check your own work, i.e., to make sure that you didn’t accidentally do something that assumed the sides were equal before you knew they were.
Do they seem to be a common form in which to write proofs?
Apart from maybe some high school geometry proofs, no. Think of proofs in a calculus book: they’re written in a more narrative style, they aren’t tables.
Know-show tables are thinking aids, not proofs.
Conventions for writing proofs, and an introduction to LaTeX, a document preparation program for math.
Please read “Writing Guidelines for Mathematics Proofs” in section 1.2 of the textbook.
Please also read my “Minimalist Introduction to LaTeX,” which is available online.
Finally, participate in this discussion of proof-writing.