Little Timmy’s Mom tells him, “if you don’t eat all your broccoli, then you will not get any ice cream.” Of course, Timmy loves his ice cream, so he quickly eats all his broccoli.
After dinner, when Timmy asks for his ice cream, he is told no! Does Timmy have a right to be upset? Why or why not?
By far, the most important type of statement in mathematics is the implication. It is also the least intuitive of our basic molecular statement types. Our goal in this section is to become more familiar with this key concept.
To see why this sort of statement is so prevalent, consider the Pythagorean Theorem. Despite what social media might claim, the Pythagorean Theorem is not
So \(1^2 + 5^2 = 2^2\text{???}\) Okay, fine. The equation is true as long as \(a\) and \(b\) are the lengths of the legs of a right triangle and \(c\) is the length of the hypotenuse. In other words:
If\(a\) and \(b\) are the lengths of the legs of a right triangle with hypotenuse of length \(c\text{,}\)then\(a^2 + b^2 = c^2\text{.}\) 2
It turns out it is also true that if\(a^2 + b^2 = c^2\text{,}\)then there is a right triangle with legs of lengths \(a\) and \(b\) and hypotenuse of length \(c\text{.}\) So we could have also expressed this theorem as a biconditional: “\(a\) and \(b\) are the lengths of the legs of a right triangle with hypotenuse of length \(c\)if and only if\(a^2 + b^2 = c^2\text{.}\)”
Math is about making general claims, but it is very rare that a claim is going to be true of absolutely every mathematical object. The way we restrict our claims to a particular type of object is with an implication: “take any object you like, if it is of the right type, then this thing is true of it.”
Similarly, as we saw in Subsection , when we make claims like “every square is a rectangle”, we are really making an implication: “if something is a square, then it is a rectangle.”
Definition1.2.1.Implications.
An implication (or conditional) is a molecular statement of the form
\begin{equation*}
P \imp Q
\end{equation*}
where \(P\) and \(Q\) are statements. We say that
\(P\) is the hypothesis (or antecedent).
\(Q\) is the conclusion (or consequent).
An implication is true provided \(P\) is false or \(Q\) is true (or both), and false otherwise. In particular, the only way for \(P \imp Q\) to be false is for \(P\) to be true and\(Q\) to be false.
The definition of truth of an implication can also be represented as a truth table:
\(P\)
\(Q\)
\(P \imp Q\)
T
T
T
T
F
F
F
T
T
F
F
T
Figure1.2.2.The truth table for \(P \imp Q\)
Does this truth table make sense? Should we believe it? Look in particular at the third row: F, T, T, and consider the implication, “If \(5 \lt 3\) then \(5+3 = 8\text{.}\)” Does that statement feel true? The truth table says it should be (since \(5 \lt 3\) is false, and \(5+3 = 8\) is true).
Much of what we will do in the remainder of this section is convince ourselves that this truth table makes sense.
SubsectionUnderstanding the Truth Table
The truth value of the implication is determined by the truth values of its two parts. Our definition of the truth conditions for an implication say that there is only one way for an implication to be false: when the hypothesis is true and the conclusion is false.
Example1.2.3.
Consider the statement:
If Bob gets a 90 on the final, then Bob will pass the class.
This is definitely an implication: \(P\) is the statement “Bob gets a 90 on the final,” and \(Q\) is the statement “Bob will pass the class.”
Suppose I made that statement to Bob. In what circumstances would it be fair to call me a liar? What if Bob really did get a 90 on the final, and he did pass the class? Then I have not lied; my statement is true. However, if Bob did get a 90 on the final and did not pass the class, then I lied, making the statement false. The tricky case is this: what if Bob did not get a 90 on the final? Maybe he passes the class, maybe he doesn’t. Did I lie in either case? I think not. In these last two cases, \(P\) was false, and the statement \(P \imp Q\) was true. In the first case, \(Q\) was true, and so was \(P \imp Q\text{.}\) So \(P \imp Q\) is true when either \(P\) is false or \(Q\) is true.
Just to be clear, although we sometimes read \(P \imp Q\) as “\(P\)implies\(Q\)”, we are not insisting that there is some causal relationship between the statements \(P\) and \(Q\) (although there might be). “If \(x \lt y\text{,}\) then \(x+1 \lt y+1\text{,}\)” is a true statement (or at least, its universal generalization is). We know it is true because we understand the way the two parts interact. If you add 1 to two numbers \(x\) and \(y\text{,}\) then their order does not change. But the statement, “if \(1 \lt 2\text{,}\) then Euclid studied geometry” is also a true implication.
Example1.2.4.
Decide which of the following statements are true and which are false. Briefly explain.
If \(1=1\text{,}\) then most horses have 4 legs.
If \(0=1\text{,}\) then \(1=1\text{.}\)
If 8 is a prime number, then the 7624th digit of \(\pi\) is an 8.
If the 7624th digit of \(\pi\) is an 8, then \(2+2 = 4\text{.}\)
Solution.
All four of the statements are true. Remember, the only way for an implication to be false is for the if part to be true and the then part to be false.
Here both the hypothesis and the conclusion are true, so the implication is true. It does not matter that there is no meaningful connection between the true mathematical fact and the fact about horses.
Here the hypothesis is false and the conclusion is true, so the implication is true.
I have no idea what the 7624th digit of \(\pi\) is, but this does not matter. Since the hypothesis is false, the implication is automatically true.
Similarly here, regardless of the truth value of the hypothesis, the conclusion is true, making the implication true.
This is a strange example, and isn’t really the way we use implications anyway. This strangeness is not just mathematicians being stubborn though. The truth conditions for implications must be like they are for mathematics to make sense. Let’s see why.
Example1.2.5.
Consider the statement, “all squares are rectangles”, which can also be phrased as, “for all shapes, if the shape is a square, then it is a rectangle.” Is this statement true or false? Are we sure? What about the following three shapes?
Solution.
Of course the statement is true. A square is a 4-sided plane figure with 4 right angles and 4 equal length sides, while a rectangle is a 4-sided plane figure with 4 right angles.
However, what we mean when we consider a universal statement like this is that, no matter what we “plug in” for variable (“the shape” in this case), the resulting statement is true. When making the statement about a particular shape, we have an implication \(P \imp Q\text{.}\) This means that, if the actual square on the left is a square, then it is a rectangle, must be true. Great. The shape is a square (\(P\) is true) and is a rectangle (\(Q\) is true), so the implication is true.
Is the implication true of the rectangle in the middle? Well, that is not a square (\(P\) is false) and it is a rectangle (\(Q\) is true). Look, we believe that all squares are rectangles, so the statement must be true. Even of a rectangle. The only way this works is if “true implies false” is true!
Similarly, all squares are rectangles is a true statement, even when we look at a triangle. \(P\) is false (the triangle is not a square) and \(Q\) is false (the triangle is not a rectangle). Thankfully, we defined implications to be true in this case as well.
We have given shapes that illustrate lines 1, 3, and 4 of the truth table for implications (Figure 1.2.2). What shape illustrates line 2? That would need to be a shape that was a square and was not a rectangle... Of course we can’t find one, precisely because the statement is true!
SubsectionRelated Statements
An implication is a way of expressing a relationship between two statements. It is often interesting to ask whether there are other relationships between the statements. Here we introduce some common language to address this question.
Definition1.2.6.Converse, Contrapositive, and Inverse.
Given an implication \(P \imp Q\text{,}\) we say,
The converseisthe statement\(Q \imp P\text{.}\)
The contrapositiveis the statement\(\neg Q \imp \neg P\text{.}\)
The inverse is the statement, \(\neg P \imp \neg Q\text{.}\)
Example1.2.7.
Consider the implication, “If you clean your room, then you can go to the party.” Give the converse, contrapositive, and inverse of this statement
Solution.
The converse is, “If you can go to the party, then you clean your room.”
The contrapositive is, “If you can’t go to the party, then you don’t clean your room.”
The inverse is, “If you don’t clean your room, then you can’t go to the party.”
Symbolically, both the converse and the contrapositive switch the order of the two parts of the statement (or alternatively, think about turning the arrow to point the other direction). The contrapositive and the inverse take the negation of both of the statements. Notice that if you take the converse (switch the order) and then take the contrapositive of that converse (switch the order back and negate both parts) you get the inverse. So the inverse is nothing more than the contrapositive of the converse. Or the converse of the contrapositive, which is a fun fact to mention at parties.
When considering statements with quantifiers, we ignore the outside quantifiers when forming the converse, contrapositive, and inverse. For example, “for all shapes, if the shape is a square, then it is a rectangle” (i.e., all squares are rectangles) has the converse, “for all shapes, if the shape is a rectangle, then it is a square” (so all rectangles are squares).
Well, that’s not true! There are rectangles that are NOT squares. Indeed, this statement is an example of a statement that is true and whose converse is false. There are lots of examples of this all over mathematics. There are also examples of true implications that have true converses. You just can’t know from the logic.
The contrapositive of “for all shapes, if it is a square, then it is a rectangle” is “for all shapes, if the shape is not a rectangle, then it is not a square.” This is true. In fact, the contrapositive of a true statement is always true!
Since the contrapositive of an implication always has the same truth value as its original implication, it can often be helpful to analyze the contrapositive to decide whether an implication is true.
Example1.2.8.
True or false: If you draw any nine playing cards from a regular deck, then you will have at least three cards all of the same suit. Is the converse true?
Solution.
True. The original implication is a little hard to analyze because there are so many different combinations of nine cards. But consider the contrapositive: If you don’t have at least three cards all of the same suit, then you don’t have nine cards. It is easy to see why this is true: if you don’t have at least three cards in a suit, you can have at most two cards of each of the four suits, for a total of at most eight cards.
The converse: If you have at least three cards all of the same suit, then you have nine cards. This is false. You could have three spades and nothing else. Note that to demonstrate that the converse (an implication) is false, we provided an example where the hypothesis is true (you do have three cards of the same suit), but where the conclusion is false (you do not have nine cards). In other words, we find some example that puts us in row 2 of the implication’s truth table.
Understanding converses and contrapositives can help understand implications and their truth values:
Example1.2.9.
Suppose I tell Sue that if she gets a 93% on her final, then she will get an A in the class. Assuming that what I said is true, what can you conclude in the following cases:
Sue gets a 93% on her final.
Sue gets an A in the class.
Sue does not get a 93% on her final.
Sue does not get an A in the class.
Solution.
Note first that whenever \(P \imp Q\) and \(P\) are both true statements, \(Q\) must be true as well. For this problem, take \(P\) to mean “Sue gets a 93% on her final” and \(Q\) to mean “Sue will get an A in the class.”
We have \(P \imp Q\) and \(P\text{,}\) so \(Q\) follows. Sue gets an A.
You cannot conclude anything. Sue could have gotten the A because she did extra credit for example. Notice that we do not know that if Sue gets an \(A\text{,}\) then she gets a 93% on her final. That is the converse of the original implication, so it might or might not be true.
The contrapositive of the converse of \(P \imp Q\) is \(\neg P \imp \neg Q\text{,}\) which states that if Sue does not get a 93% on the final, then she will not get an A in the class. But this does not follow from the original implication. Again, we can conclude nothing. Sue could have done extra credit.
What would happen if Sue does not get an A but did get a 93% on the final? Then \(P\) would be true and \(Q\) would be false. This makes the implication \(P \imp Q\) false! It must be that Sue did not get a 93% on the final. Notice now we have the implication \(\neg Q \imp \neg P\) which is the contrapositive of \(P \imp Q\text{.}\) Since \(P \imp Q\) is assumed to be true, we know \(\neg Q \imp \neg P\) is true as well.
As we said above, an implication is not logically equivalent to its converse, but it is possible that both the implication and its converse are true. In this case, when both \(P \imp Q\) and \(Q \imp P\) are true, we say that \(P\) and \(Q\) are equivalent and write \(P \iff Q\text{.}\) This is the biconditional we mentioned in Section 1.1.
You can think of “if and only if” statements as having two parts: an implication and its converse. We might say one is the “if” part, and the other is the “only if” part. We also sometimes say that “if and only if” statements have two directions: a forward direction \((P \imp Q)\) and a backwards direction (\(P \leftarrow Q\text{,}\) which is really just sloppy notation for \(Q \imp P\)).
Let’s think a little about which part is which. Is \(P \imp Q\) the “if” part or the “only if” part? Consider an example.
Example1.2.10.
Suppose it is true that I sing if and only if I’m in the shower. We know this means both that if I sing, then I’m in the shower, and also the converse, that if I’m in the shower, then I sing. Let \(P\) be the statement, “I sing,” and \(Q\) be, “I’m in the shower.” So \(P \imp Q\) is the statement “if I sing, then I’m in the shower.” Which part of the if and only if statement is this?
What we are really asking for is the meaning of “I sing if I’m in the shower” and “I sing only if I’m in the shower.” When is the first one (the “if” part) false? When I am in the shower but not singing. That is the same condition on being false as the statement “if I’m in the shower, then I sing.” So the “if” part is \(Q \imp P\text{.}\) On the other hand, to say, “I sing only if I’m in the shower” is equivalent to saying “if I sing, then I’m in the shower,” so the “only if” part is \(P \imp Q\text{.}\)
It is not terribly important to know which part is the “if” or “only if” part, but this does illustrate something very, very important: there are many ways to state an implication!
Example1.2.11.
Rephrase the implication, “if I dream, then I am asleep” in as many different ways as possible. Then do the same for the converse.
Solution.
The following are all equivalent to the original implication:
I am asleep if I dream.
I dream only if I am asleep.
In order to dream, I must be asleep.
To dream, it is necessary that I am asleep.
To be asleep, it is sufficient to dream.
I am not dreaming unless I am asleep.
The following are equivalent to the converse (if I am asleep, then I dream):
I dream if I am asleep.
I am asleep only if I dream.
It is necessary that I dream in order to be asleep.
It is sufficient that I be asleep in order to dream.
If I don’t dream, then I’m not asleep.
Hopefully you agree with the above example. We include the “necessary and sufficient” versions because those are common when discussing mathematics. In fact, let’s agree once and for all what they mean.
Definition1.2.12.Necessary and Sufficient.
“\(P\) is necessary for \(Q\)” means \(Q \imp P\text{.}\)
“\(P\) is sufficient for \(Q\)” means \(P \imp Q\text{.}\)
If \(P\) is necessary and sufficient for \(Q\text{,}\) then \(P \iff Q\text{.}\)
To be honest, I have trouble with these if I’m not very careful. I find it helps to keep a standard example for reference.
Example1.2.13.
In a regular deck of cards, the red suits are hearts and diamonds. The black suits are clubs and spades. Thus it is true that, after picking a card, if my card is a spade, then my card is black.
Restate this fact using necessary and sufficient phrasing.
Solution.
In order of my card to be a spade, it is necessary that it is black. However, it is not sufficient for it to be black in order to say that I am holding a spade (since I could have a club).
I can also say that to have a black card, it is sufficient to have a spade. It is not necessary that I have a spade.
It is helpful to think about the amount of evidence you need. Is knowing that the card is a spade enough evidence to conclude that it is a black card? Yes, that is sufficient! Being a spade is a sufficient condition for the card to be black.
Thinking about the necessity and sufficiency of conditions can also help when writing proofs and justifying conclusions. If you want to establish some mathematical fact, it is helpful to think what other facts would be enough (be sufficient) to prove your fact. If you have an assumption, think about what must also be necessary if that hypothesis is true.
Reading QuestionsReading Questions
1.
Give an example of a true implication (written out in words) that has a false converse. Explain why your implication is true and why the converse is false.
ExercisesPractice Problems
1.
In my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a pentagon, and the other is a triangle. Each shape is drawn in a single color. Suppose you believe me when I tell you that,
if the pentagon is purple, then the triangle is blue.
What do you therefore know about the truth value of the following statements?
The pentagon is not purple or the triangle is blue.
If the triangle is not blue, then the pentagon is not purple.
The pentagon and the triangle are both purple.
If the triangle is blue, then the pentagon is purple.
The pentagon the triangle are both blue.
Solution.
The main thing to realize is that we do not know the colors of these two shapes, but we do know that we are in one of three cases: We could have a purple pentagon and blue triangle. We could have a pentagon that was not purple but a blue triangle. Or we could have a pentagon that was not purple and a triangle that was not blue. The case in which the pentagon is purple but the triangle is not blue cannot occur, as that would make the statement false.
2.
Suppose the statement, "if the diamond is blue, then the pentagon is purple," is true. Assume also that the converse is false. Classify each statement below as true or false (if possible).
The pentagon is purple.
The diamond is blue.
The diamond is blue if and only if the pentagon is purple.
The diamond is blue if and only if the pentagon is not purple.
Solution.
The only way for an implication \(P\rightarrow Q\) to be true but its converse to be false is for \(Q\) to be true and \(P\) to be false. Thus we know that pentagon is purple and that diamond is not blue.
3.
Consider the statement, "If you will give me a cow, then I will give you magic beans." Decide whether each statement below is the converse, the contrapositive, or neither.
If I will not give you magic beans, then you will not give me a cow.
If you will give me a cow, then I will not give you magic beans.
If you will not give me a cow, then I will not give you magic beans.
If I will give you magic beans, then you will not give me a cow.
You will give me a cow and I will not give you magic beans.
If I will give you magic beans, then you will give me a cow.
Solution.
The converse is "If I will give you magic beans, then you will give me a cow." The contrapositive is "If I will not give you magic beans, then you will not give me a cow." All the other statements are neither the converse nor contrapositive.
4.
You have discovered an old paper on graph theory that discusses the viscosity of a graph (which for all you know, is something completely made up by the author). A theorem in the paper claims that “if a graph satisfies condition (V), then the graph is viscous.” Which of the following are equivalent ways of stating this claim? Which are equivalent to the converse of the claim?
Every viscous graph satisfies condition (V).
For a graph to be viscous, it is sufficient for it to satisfy condition (V).
Only viscous graphs satisfy condition (V).
A graph is viscous only if it satisfies condition (V).
For a graph to be viscous, it is necessary that it satisfies condition (V).
5.
Which of the following statements are equivalent to the implication, "if you win the lottery, then you will be rich," and which are equivalent to the converse of the implication?
It is necessary for you to win the lottery to be rich.
You will win the lottery and be rich.
It is sufficient to win the lottery to be rich.
Unless you win the lottery, you won’t be rich.
You will be rich if you win the lottery.
6.
Additional exercises coming soon.
ExercisesAdditional Exercises
1.
Recall from calculus, if a function is differentiable at a point \(c\text{,}\) then it is continuous at \(c\text{,}\) but that the converse of this statement is not true (for example, \(f(x) = |x|\) at the point 0). Restate this fact using “necessary and sufficient” language.
Solution.
It is true that in order for a function to be differentiable at a point \(c\text{,}\) it is necessary for the function to be continuous at \(c\text{.}\) However, it is not necessary that a function be differentiable at \(c\) for it to be continuous at \(c\text{.}\)
It is true that to be continuous at a point \(c\text{,}\) it is sufficient that the function be differentiable at \(c\text{.}\) However, it is not the case that being continuous at \(c\) is sufficient for a function to be differentiable at \(c\text{.}\)
2.
Consider the statement, “For all natural numbers \(n\text{,}\) if \(n\) is prime, then \(n\) is solitary.” You do not need to know what solitary means for this problem, just that it is a property that some numbers have and others do not.
Write the converse and the contrapositive of the statement, saying which is which. Note: the original statement claims that an implication is true for all \(n\text{,}\) and it is that implication that we are taking the converse and contrapositive of.
Write the negation of the original statement. What would you need to show to prove that the statement is false?
Even though you don’t know whether 10 is solitary (in fact, nobody knows this), is the statement “if 10 is prime, then 10 is solitary” true or false? Explain.
It turns out that 8 is solitary. Does this tell you anything about the truth or falsity of the original statement, its converse or its contrapositive? Explain.
Assuming that the original statement is true, what can you say about the relationship between the set\(P\) of prime numbers and the set\(S\) of solitary numbers. Explain.
