Implications

Section Preview

Investigation

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 (which actually tastes pretty good).

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 \[a^2 + b^2 = c^2\]. Okay, sure, that has a variable in it, so we must be using the convention to take the universal generalization, \[\forall a,b,c \in \R \left( a^2 + b^2 = c^2 \right)\]. So \(1^2 + 5^2 = 2^2\)??? 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\), then \(a^2 + b^2 = c^2\).

Math is about making general claims, but a claim is rarely 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 about it.

Similarly, as we saw in the subsection, when we make claims like Every square is a rectangle, we really have an implication: If something is a square, then it is a rectangle.

Here is a reminder of what we mean by an implication.

The definition of truth of an implication can also be represented as a truth table:

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\). Does that statement feel true? The truth table says it should be (since \(5 \lt 3\) is false, and \(5+3 = 8\) is true).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Understanding 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 says that there is only one way for an implication to be false: when the hypothesis is true and the conclusion is false.

Example

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\). 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\), then \(x+1 \lt y+1\), is a true statement (or at least, its universal generalization is). We know it is true because we understand how the two parts interact. If you add 1 to two numbers \(x\) and \(y\), then their order does not change. But the statement, if \(1 \lt 2\), then Euclid studied geometry is also a true implication.

This is a strange example and isn't really how 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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Related 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.

Example

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 in 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.

A quantified implication \(\forall x (P(x) \imp Q(x))\) has:

• Converse

  \(\forall x (Q(x) \imp P(x))\)

• Contrapositive

  \(\forall x (\neg Q(x) \imp \neg P(x))\)

• Inverse

  \(\forall x (\neg P(x) \imp \neg Q(x))\)

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).

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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (13)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Consider the statement, If Tommy doesn't eat his broccoli, then he will not get any ice cream. Which of the following statements mean the same thing (i.e., will be true in the same situations)? Select all that apply.

2. Suppose that your shady uncle offers you the following deal: If you loan him your car, then he will bring you tacos. In which of the following situations would it be fair to say that your uncle is a liar (i.e., that his statement was false)? Select all that apply.

3. Consider the sentence, If \(x \ge 10\), then \(x^2 \ge 25\). This sentence becomes a statement when we replace \(x\) by a value, or capture the \(x\) in the scope of a quantifier. Which of the following claims are true (select all that apply)?

4. Consider the statement, If I see a movie, then I eat popcorn (which happens to be true). Based solely on your intuition of English, which of the following statements mean the same thing? Select all that apply.

5. It happens to be true that all mammals have hair. Which of the following are also true?

6. 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.

7. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

8. Translate into English:

   1. \(\forall x (E(x) \imp E(x +2))\)
   2. \(\forall x \exists y (\sin(x) = y)\)
   3. \(\forall y \exists x (\sin(x) = y)\)
   4. \(\forall x \forall y (x^3 = y^3 \imp x = y)\)

   Revelează răspunsul

   1. Any even number plus 2 is an even number.

   2. For any \(x\) there is a \(y\) such that \(\sin(x) = y\). In other words, every number \(x\) is in the domain of sine.

   3. For every \(y\) there is an \(x\) such that \(\sin(x) = y\). In other words, every number \(y\) is in the range of sine (which is false).

   4. For any numbers, if the cubes of two numbers are equal, then the numbers are equal.

9. Consider the statement, If Oscar eats Chinese food, then he drinks milk.

   1. Write the converse of the statement.

   2. Write the contrapositive of the statement.

   3. Is it possible for the contrapositive to be false? If it was, what would that tell you?

   4. Suppose the original statement is true, and that Oscar drinks milk. Can you conclude anything (about his eating Chinese food)? Explain.

   5. Suppose the original statement is true, and that Oscar does not drink milk. Can you conclude anything (about his eating Chinese food)? Explain.

10. Write each of the following statements in the form, If , then . Careful, some statements may be false (which is fine for the purposes of this question).

    1. To lose weight, you must exercise.

    2. To lose weight, all you need to do is exercise.

    3. Every American is patriotic.

    4. You are patriotic only if you are American.

    5. The set of rational numbers is a subset of the real numbers.

    6. A number is prime if it is not even.

    7. Either the Broncos will win the Super Bowl, or they won't play in the Super Bowl.

    Revelează răspunsul

    1. If you have lost weight, then you exercised.

    2. If you exercise, then you will lose weight.

    3. If you are American, then you are patriotic.

    4. If you are patriotic, then you are American.

    5. If a number is rational, then it is real.

    6. If a number is not even, then it is prime. (Or the contrapositive: If a number is not prime, then it is even.)

    7. If the Broncos don't win the Super Bowl, then they didn't play in the Super Bowl. Alternatively, if the Broncos play in the Super Bowl, then they will win the Super Bowl.

11. Consider the implication, If you clean your room, then you can watch TV. Rephrase the implication in as many ways as possible. Then do the same for the converse.

    Revelează răspunsul

    Hint:

    Of course there are many answers. It helps to assume that the statement is true and the converse is not true. Think about what that means in the real world, and then start saying it in different ways. Some ideas: Use necessary and sufficient language, use only if, consider negations, use or else language.

12. Recall from calculus, if a function is differentiable at a point \(c\), then it is continuous at \(c\), 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.

    Revelează răspunsul

    It is true that in order for a function to be differentiable at a point \(c\), it is necessary for the function to be continuous at \(c\). However, it is not necessary that a function be differentiable at \(c\) for it to be continuous at \(c\).

    It is true that to be continuous at a point \(c\), it is sufficient that the function be differentiable at \(c\). However, it is not the case that being continuous at \(c\) is sufficient for a function to be differentiable at \(c\).

13. Consider the statement, For all natural numbers \(n\), 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.

    1. 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\), and it is that implication that we are taking the converse and contrapositive of.

    2. Write the negation of the original statement. What would you need to show to prove that the statement is false?

    3. 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.

    4. 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.

    5. 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.

Symbols used here

\sin,\ \cos,\ \tan

sine, cosine, tangent
Ratios of sides in a right triangle; coordinates on the unit circle.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\forall,\ \exists

for all, there exists
Quantifiers: every x; at least one x.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

P(A),\ P(A \mid B)

probability, conditional probability
Chance of A; chance of A given that B happened.

y',\ y''

first and second derivative of y
Prime notation for derivatives with respect to x (or t).

i

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

How to: Implications

1. Explain the conditions under which an implication is true.
2. Identify statements as equivalent to a given implication or its converse.
3. Explain the relationship between the truth values of an implication, its converse, and its contrapositive.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Încearcă pe tine.

⌨ Type ✎ Draw

Problema cu matematica

Rezolvă

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mai multe în Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions