Math 224
Dr. McLoughlin’s Classes
Handout V
Proof Versus
Counterexample
There has been some confusion (as it has always been)
between a proof and a counterexample.
Please refer to a text such as the text,
"100% Mathematical Proof" (Garnier &
Taylor), or my e-book
for a detailed discussion of the difference between a proof
and counterexample.
First consider the following claim:
Claim
1 Let x and y be integers. If x is even and y is even,
then x + y is even.
You must first READ the claim and decide whether
or not you think it is true (you may be wrong, but you have to practice this
step; it is based on your prior experience and knowledge). It is an
inductive step; hence, there is no guarantee that you are right.
Next, after considering claim
1, suppose we think it true. Thinking
it is true is not proving it is true. Hence, we need to construct a
proof.
We must announce it is a proof and frame it at
the beginning (Proof:) and at the end (Q.E.D.).
Proof:
1. Let x be an
integer
1. Premise
2. There exists an integer, m, such
that 2.
Definition of even integer.
x = 2m.
3. Let y be an
integer
3. Premise
4. There exists an integer, k, such
that
4. Definition of even integer.
y = 2k.
5. Consider x +
y
5. Hypothesis.
6. x + y = (2m) +
(2k)
6. Substitution
7. = 2m +
2k 7.
Associative axiom of multiplication
8. = 2(m +
k)
8. Distributive
axiom of multiplication over addition.
9. Hence, x + y = 2(m +
k)
9. Transitivity of "="
10. But, m + k is an integer, say
n.
10. Closure of integers under addition.
11. So, x + y = 2n, such that n is an
integer. 11. Substitution
12. Thus, x + y is
even.
12. Definition of even integer.
Q. E. D.
Comment:
note in line 4 we had to express y as 2 times an integer; but, we can not use
the same variable as m (for x) since we do not know [we do not have a
premise, hypothesis, or prior information] hence can not opine that y = x.
.
Claim 2
Let x and y be integers. If x is odd and y is even, then x + y is
even.
You must first READ the claim
and decide whether or not you think it is true (you may be wrong, but you have
to practice this step; it is based on your prior experience and
knowledge). It is an inductive step; hence, there is no guarantee
that you are right.
Next, after considering claim
2, suppose we think it false. Thinking it is false is not proving it
is false. Hence, we need to construct a counterexample.
We must announce it is a counterexample, present the counterexample, and
demonstrate that indeed the premises are true but the consequent is
false. A counterexample is concrete - - it is not writing a paragraph or
two explaining why one opines the claim false - - it is an example!!!!! Also,
note it is not framed at the beginning (Proof:) and at
the end (Q.E.D.: Quod Erat Demonstratum)
as with a proof; we only need announce at the beginning and compleat the
counterexample.
Counterexample:
Consider x = 3 and y = -8.
Note that x is odd since x = 2(1) + 1 and 1 is an integer.
Note that y is even since y = 2(-4) and -4 is an
integer.
Now, x + y = 3 + (-8) = -5 = 2(-2) + 1. Since -2 is an integer, -5 is an
odd integer (by the definition of odd integer). Therefore, x + y is not
even.
E. E. F.
Finally, as with all the discussions, examples,
proofs, counterexamples, claims, etc. that we encounter; it is my opinion that
few can do well in this class through just attending and watching others do the
work. I opine that only through doing can we understand and KNOW.
Hence, my advice is: "practice, practice, practice." Notice
that this too is framed - - by the announcement of a counterexample and by the
end (E. E. F.: Exemplum Est
Factum).
Back to handouts page
Last edited 2 Feb. 2009