Math
255
Set Theory
Handout 2
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" (the old Math 180 text;
or another available in the reading room [Dansby Hall 339]) 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).