|
|
We have seen the rules of inference used in proofs. For instance, modus ponens is:
if p is true and p Þ q is true, then q is true.
We call p Þ q, the ARGUMENT in the proof.
There are also other statements related to p Þ q that appear in proof arguments.
Here we look at these relatives of p Þ q.
Let us begin with p Þ q itself.
 |
| p Þ q |
Conditional Statements
Consider this statement:
If a person lives in New York, then the person lives in America.
The statement has the following form: If p, then q.
Another way of writing this is p Þ q.
It is a Conditional Statement. p is called the premise (or antecedent) and q is called the conclusion (or consequent).
A pictorial method of representing it is with an Euler Diagram.
All points within the inner circle match the premise p. For our original statement, which is an instance of p Þ q, those points in circle p consist of people who live in New York. Because the circles are nested, the same points in p are also in circle q. So the points in p possess the property possessed by points in q.
Often, a premise is also called a hypothesis. However, a statement that has resisted attempts to prove it or is unprovable, contradicts no known statements, and helps to prove other statements, is also called a Hypothesis. So we prefer to call p the premise or assumption.
Converse
If we turn around p Þ q, we get q Þ p. The latter is called the converse of the former. "Converse" comes from the Latin word "conversus", meaning "turned around." It is clear that the converse of our original statement is not true. So, for some true statements the converse is not true. And there are true statements for which the converse is also true. Consider this.
If a triangle is right-angled, then the square of the side subtending the right angle is equal to the sum of squares of the sides containing the right angle.
This is the Pythagorean Theorem. Its converse is true: If in a triangle the square of one of the sides is equal to the sum of squares of the remaining two sides, the angle contained by those remaining sides is a right angle.
Note that the converse of the Pythagorean Theorem is seldom proved in school. The standard proof[1] of this converse is beautiful and is instructive in how sometimes p Þ q can be used to obtain a short proof of q Þ p. Note also that this converse, the last proposition in the First Book of Euclid's Elements, is of practical use in that it allows us to construct a right angle.
A theorem is a proposition of wide applicability.
Contrapositive
Another conditional statement associated with p Þ q is the contrapositive: ~q Þ ~p, where ~p denotes "Not p." That is, if ~q, then ~p. The contrapositive does have the same truth value as its source statement, as can be verified from their truth values. Thus, p Þ q and ~q Þ ~p are either both true or both false. The Euler diagram illustrates why the contrapositive is equivalent to the original statement. Because circle p is wholly within circle q, points outside of circle q ("Not q") must be outside of circle p ("Not p") as well. So Not q implies Not p. If a person lives outside America, then it is not true that the person lives in New York.
What is the use of the contrapositive if it behaves just like the statement it is contrapositive of? The question is relevant because it "seems" that one has to do the same amount of work to prove either statement. Not so! In some statements, p Þ q, ~q contains more information we can work with than we can in p, and so the proof of the contrapositive in that case will be easier.
Here is a simple example that illustrates this.
We will use the following definitions.
- An integer x is called even (respectively odd) if there is another integer k for which x = 2k (respectively 2k+1).
- Two integers are said to have the same parity if they are both odd or both even.
For the purpose of this example we will assume as proved that each integer is either even or odd.
Proposition.
If x and y are two integers for which x+y is even, then x and y have the same parity.
Proof.
The contrapositive version of this theorem is "If x and y are two integers with opposite parity, then their sum must be odd." So we assume x and y have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose x is even and y is odd. Thus, there are integers k and m for which x = 2k and y = 2m+1. Then x+y = 2k + 2m + 1 = 2(k+m) + 1, which is an odd integer by definition.
In our section on the techniques of proof, we will comment more on using the contrapositive in proving the source statement. The contrapositive is also called "counterpositive."
Inverse
Consider the converse of the contrapositive of p Þ q. That is, ~ p Þ ~ q; it is called the inverse of p Þ q. What is the inverse of our original statement? If a person does not live in New York, the person does not live in America. This statement is not true. So for some satements, the inverse is not true. Here is a theorem whose converse as well as inverse are true.
If two sides of a triangle are congruent, then the angles opposite those sides are congruent.
(This is the Isosceles Triangle Theorem. We will refer to it as ITT.)
The converse is: If two angles of a triangle are congruent, then the sides opposite those angles are conguruent.
The inverse of ITT is: If two sides of a triangle are not congruent, then the angles opposite those sides are not congruent.
(Moreover, the larger angle is opposite the larger side!)
If, and Only If
We have seen that for some statements p Þ q, the converse is also true. For instance, ITT and Pythagorean Theorem are of this kind.
For statements like these, whose converses are also true, we can combine the statement and the converse as "p, if and only if, q". This is the situation precisely when p and q are equivalent statements. However, care should be taken when combining to form the "if, and only if" form.
Let us combine the Pythagorean Theorem and its converse.
Pythagorean Theorem:
If a triangle is right-angled, then the square of the side subtending the right angle is equal to the sum of squares of the sides containing the right angle.
Another way of writing it is: A triangle is right-angled only if the square of the side subtending the right angle is equal to the sum of squares of the sides containing the right angle.
Now let us combine this with its converse. Would the combined form be the following?
A triangle is right-angled if, and only if, the square of the side subtending the right angle is equal to the sum of squares of the sides containing the right angle.
You can see that there is a problem with this last statement. The Pythagorean Theorem contained in it - namely, the version obtained by omitting "if" is fine. Now, keep the "if" and omit the "only if":
A triangle is right-angled if the square of the side subtending the right angle is equal to the sum of squares of the sides containing the right angle.
That is, if the square of the side subtending the right angle is equal to the sum of squares of the sides containing the right angle, then the triangle has a right-angle. This statement is not proving that the triangle has a right angle; for, the premise says that the triangle is right-angled.
So how do you combine PT and its converse? Here it is:
An angle in a triangle is a right angle if, and only if, the square of the side subtending the angle is equal to the sum of squares of the sides containing the angle.
Let us consider an example.
Proposition
A positive integer n is evenly divisible by 3 if the sum of the digits of n is divisible by 3.
(Let us write this as follows: For a positive integer n, if the sum of the digits of n is divisible by 3, then n is evenly divisible by 3.
Proof:
Suppose n is a positve integer whose decimal representation is a0a1...ak. This means, n = a0 + a1 10 + ...ak 10k. The digit sum is s = a0 + a1 + ... + ak.
Now, n-s = (a0 + a1 10 + ...ak 10k) - (a0 + a1 + ... + ak) = 9a1 + 99a2 + ... + ak (99...9) (where the last term has k nines). So, clearly, n - s is divisble by 3, and since, by assumption, s is divisible by 3, n is divisible by 3.
Q.E.D.
Notice from the proof that the converse of the proposition also holds because n-s is always divisible by 3, so s is divisible by 3 whenever n is.
So we can combine the statement and its converse thus: A positive integer n is evenly divisible by 3 if and only if the sum of the digits is divisible by 3.
To prove a "If, and Only If" theorem, you must prove two implications: (1) If p, then q and (2) If q, then p. "If p, then q" says q is a necessary condition for p to be true. "If q, then p" says q is a sufficient condition for p to be true. Therefore, "p if, and only if, q," is sometimes written "p is necessary and sufficient for q." Why is this?
Look at p Þ q. If this statement is true, it means that p as a condition is sufficient to prove q. Now look at q Þ p. Here, p is a necessary consequene for q. Thus, "p if, and only if, q" or p Û q is equivalent to saying "p is necessary and sufficient for q." This is also equivalent to "q is necessary and sufficient for p."
In writing out the proof of a "if, and only if" or, what is the same, "necessary and sufficient" statement, one proves the two implications: (1) If p then q. Or what is the same thing, "Necessity of q," and (2) If q then p. Or what is the same thing, "Sufficiency of q."
Alternately, one proves the necessity and sufficiency of p.
"p if, and only if, q" is often written without the commas. It is also written "p iff q" to save time - it is now common practice.
It is the natural tendency of the mathematician to ask, once a statement p Þ q is proved, if the converse is true. Often, for "if and only if" theorems, one implication is likley to be easier than the converse of it. It is the easier part that is often first discovered.
REFERENCES
[1]Eulcid, Book I of the Elements, Proposition 48
Invalid Arguments
« BACK
MathPath - "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2002-2003 by the MathPath Organization
Last updated - June 18, 2003
|
