Basics of Implication and Deduction

Learning goals: Basic intuitive understanding of $P$ implies $Q$, as well as various associated terms such as 'deduction' and 'implication'.

What is an implication of a statement P?

An implication $Q$ of a statement $P$ is a conclusion that must follow if or whenever $P$ is true. In other words, once we know that $P$ is true, we are forced to conclude the implication $Q$ is true as well.

Example 1

Suppose we know: $n$ is a multiple of 10; This is our statement $P$, what implications (or conclusions) can we draw? Well, even though we don't know exactly what number $n$ is, but based on $P$, we can conclude:

• $n$ is even.
• $n$ is divisible by $5$.
• $n$ must end in $0$.

These are three separate implications of our $P$.

Example 2

Suppose we know: James is in a boat floating on the Thames river in London; This is our statement $P$. What implications (or conclusions) can we draw?

• James is not on land.
• James is in England.
• There is at least one boat floating on the Thames.

For both examples, you can see that in each case, multiple implications (or conclusions) $Q$ were drawn (or deduced) from $P$, it is also possible to draw even more conclusions. In each case, we can write the relation between $P$ and $Q$ in short as:

The double lined arrow: $\Rightarrow$ is known as the implication arrow symbol, it means the statement the arrow is pointing to, is an implication of the statement to the other side of the arrow. Here are some examples:

• $n$ is a multiple of 10 $\Rightarrow$ $n$ is even
• $x >2 \Rightarrow x > 0$
• It rained $\Rightarrow$ roads get wet
• $n^2$ is odd $\Leftarrow$ $n$ is odd
• Right-angled triangle $\Leftarrow$ $a^2 + b^2 = c^2$

An implication is a deduction

At this level, we may consider the words implication and deduction having the same meaning, as well as the associated verbs of imply and deduce meaning the same thing. For example, we may say:

• $x>1$ implies $x>2$
• $x>2$ is an implication of $x>1$
• $x>2$ is a deduction from $x>1$
• From $x>1$, we deduce $x>2$

All of the above statements are different ways of saying the same thing, namely: $x>1 \Rightarrow x>2$. So you should get used to all of these wordings.

Chained Implications or deductions

In mathematical logical arguments, we often write a chain of implications / deductions to form basis of our argument, or proof. An example of such structure in words:

We know $A$ to be true, therefore $B$ is true, and now because $B$ is true, $C$ is true, and now $D$ is true.

In symbols: $A \Rightarrow B \Rightarrow C \Rightarrow D$

Here is an mathematical example of a direct proof using chained implications.

Question:

Prove that $x^2 + 2x + 4$ is always positive.

Proof: We start by stating an obvious fact which everyone agrees which that does not require proof:

then

and so it is proven.

Caution 1: $P \Rightarrow Q$ tell us nothing about $Q \Rightarrow P$

In general, just because $P$ implies $Q$, it does not automatically mean that $Q$ implies $P$. This is a common source of mistakes. For example:

• $x>1 \Rightarrow x^2>1$ is true, but $x^2>1 \Rightarrow x>1$ is not true, take $x=-2$, $(-2)^2>1$ but $-2$ is not greater than 1.
• $x = 2 \Rightarrow (x-1)x = 2(x-1)$ is true, but $(x-1)x = 2(x-1) \Rightarrow x=2$ is false, because given $(x-1)x = 2(x-1)$, $x$ is 1 or 2, in particular, to say $x=2$ which means $x$ must be 2, is false.

Caution 2: $P \Rightarrow Q$ tell us nothing about $P$ or $Q$ themselves.

This one is a little subtle, but $P \Rightarrow Q$ just tell us whenever $P$ is true, $Q$ must be true. This does not say anything about the truthiness or $P$ or $Q$, it is a hypethetical:

• $x>1\,\,(P) \Rightarrow x>2\,\,(Q)$, this is true. However, depending on the actual value of $x$, $P$ maybe false, while $Q$ maybe true, for example $x=1.5$. Or say $x=0$ and now they are both false. The only combination we cannot have is when $P$ is true and $Q$ is false, but more on this in later sections.
• Horses has big wings like the legendary Pegasus $\Rightarrow$ one can ride a horse into the sky. We wink and say this is true: if one day,

and read it as "$P$ implies $Q$", or equally "if $P$, then $Q$". Here $P$ is the condition — the thing we are given, or assuming — and $Q$ is what follows from it.

The arrow points one way, and that direction is the whole point of this section. We start at $P$ and travel to $Q$. Throughout, we are asking a single question:

Given that $P$ holds, what can I conclude?

For the most part, at least where TMUA is concerned, the word implication and deduction mean the same thing, as well as the associated verbs of imply and deduce also mean the same thing. For example, we may say

"Implied" and "deduced" are the same word

Mathematicians describe that single arrow $P \Rightarrow Q$ using several different phrasings. Every one of the following says exactly the same thing:

• $P$ implies $Q$
• $Q$ is implied by $P$
• $Q$ can be deduced from $P$
• from $P$ we deduce $Q$

The verbs "imply" and "deduce" run in opposite grammatical directions — $P$ implies $Q$, but $Q$ is deduced from $P$ — yet they describe one and the same arrow. Don't let the two words trick you into thinking there are two ideas. There is one idea: $P$ gives you $Q$.

Everyday examples

Implication is not a mathematical invention; you reason this way all the time.

Let $P$ be "it is raining" and $Q$ be "the ground outside is wet". Then

Given the rain (the condition $P$), you can deduce the wet ground (the conclusion $Q$).

Another: let $P$ be "today is a public holiday" and $Q$ be "the bank is closed". From the condition that it's a public holiday, you deduce that the bank is closed: $P \Rightarrow Q$.

In each case you are doing the one thing this section is about — starting from a condition and reading off what must follow.

Mathematical examples

The mathematics has exactly the same shape.

If you are told $n$ is a multiple of $4$, you may deduce that $n$ is even.

Given $x = 3$, you deduce $x^2 = 9$.

If $x$ is greater than $5$, then certainly $x$ is greater than $2$.

Notice these are the same forward-deductions as the rain and the bank — a condition on the left, a conclusion read off on the right.

Deductions can be chained

Because an implication hands you a new true statement, you can feed that statement straight into another implication. If $P \Rightarrow Q$ and $Q \Rightarrow R$, then

For example, from $x = 3$ we deduce $x^2 = 9$, and from $x^2 = 9$ we deduce $x^2 - 9 = 0$:

Chaining deductions like this is the engine of almost every proof you will ever write.

One thing $P \Rightarrow Q$ does not say

An implication is a promise about a link, not a claim that $P$ is currently true. The statement "if it is raining, the ground is wet" is perfectly true on a dry, sunny day — it only tells you what would follow if it rained. Keep two things firmly apart:

• the implication $P \Rightarrow Q$ being true (the link holds), and
• the condition $P$ being true (it is, in fact, raining).

In this section we are only studying the link.

Common mistakes

1. Running the arrow backwards. From $P \Rightarrow Q$ you may not conclude $Q \Rightarrow P$. Wet ground doesn't mean rain — a burst pipe would do it. In maths, from $x^2 = 9$ you cannot deduce $x = 3$, because $x$ might be $-3$. Reversing an implication is a genuine topic of its own — it's the whole of Section 2.

2. Assuming the condition is true. $P \Rightarrow Q$ does not assert that $P$ holds. It only tells you what to conclude if it does.

Summary

• $P \Rightarrow Q$ means "if $P$, then $Q$": from the condition $P$, the conclusion $Q$ follows.
• "$P$ implies $Q$" and "$Q$ is deduced from $P$" are the same statement in different words.
• The arrow has a direction — we only ever travel $P \to Q$ here.
• Implications chain: $P \Rightarrow Q$ and $Q \Rightarrow R$ give $P \Rightarrow R$.

Next: Section 2 — P ⇒ Q Equivalents → the many equivalent ways to phrase an implication.