Section 2.4 The implication
In mathematics we make many statements of the form
If \(x\) is a real number then \(x^2\) is a real number
and a large fraction of the theorems we want to prove are of this form.
Definition 2.4.1.
For statements \(P\) and \(Q\text{,}\) the implications or conditional is the statement
\begin{gather*}
\text{if } P \text{ then } Q
\end{gather*}
and is denoted \(P \implies Q\text{.}\) In this context \(P\) is called the hypothesis and \(Q\) is called the conclusion. The implication is false when \(P\) is true and \(Q\) is false; otherwise it is true. The truth table is
| \(P\) |
\(Q\) |
\(P \implies Q\) |
\((\neg P) \lor Q\) |
| T |
T |
T |
T |
| T |
F |
F |
F |
| F |
T |
T |
T |
| F |
F |
T |
T |
Further note that sometimes the hypothesis is called the
antecedent while the conclusion is called the
consequent 22 .
Before we get to the peculiarities of the truth table, we should note that the statement “\(P \implies Q\)” can be read in many different ways. Some of these are (in the opinion of the authors) a little obfuscating, and we recommend to stick with “If \(P\) then \(Q\)”.
The author likes the statements above because the hypothesis comes before the conclusion. One may sometimes also see the implication \(P \implies Q\) written as
The authors recommend that you avoid these (at least until you have a bit more experience with mathematical proofs) since they write the conclusion before the hypothesis. They make it very easy to confuse the flow of logic. The statement “\(Q\) if \(P\)” is particularly confusing and, in this author’s opinion, should be avoided.
Many mathematicians like to use the terms “necessary” and “sufficient” when writing implications. These terms allow one to put more emphasis on either the hypothesis or conclusion — this can be quite useful depending on the context in which you are writing. Consider again our nonsense example
If he is Shakespeare then he is dead
It is sufficient to check that a given person is Shakespeare to decide that they must be dead. Similarly, someone is necessarily dead in order for them to be Shakespeare You may see the implication \(P \implies Q\) written in the following ways
\(P\) is a sufficient condition for \(Q\text{,}\)
\(P\) is sufficient for \(Q\text{,}\)
\(Q\) is a necessary condition for \(P\text{,}\) or
\(Q\) is necessary for \(P\text{.}\)
The first two of these emphasise that if you want to know that \(Q\) is true, then one need only check (ie it is sufficient to check) that \(P\) is true. While the last two emphasise that the truth of \(Q\) is required (it isnecessary) for \(P\) to be true.
Now back to the truth table. At first glance it can seem a bit strange so to get the feel of it we’ll use it on a couple of simple examples and then apply it to something a little larger. Consider the statements \(P: 13 \text{ is even}\) and \(Q: 7 \text{ is odd}\text{.}\) The statement \(P \implies Q\)
If 13 is even then 7 is odd
is true, while \(Q \implies P\)
If 7 is odd then 13 is even
is false.
A more sizeable example which appears in a few textbooks in similar forms. Frequently a student will ask their instructor
Will I pass this course?
and the author (sometimes) responds
If you pass the exam, then you will pass the course.
Under what circumstances is the author lying or telling the truth?
The author has definitely lied if you pass the exam but end up failing to course. The other 3 possible outcomes are consistent with them telling the truth. Let’s explore with the caveat that this should not be considered a binding discussion about your actual passing or failing of a given course. Use \(P\) to denote “The student passes the exam”, and \(Q\) to denote “The student passes the course”, so we can write my statement as \(P \implies Q\text{:}\)
“If the student passes the exam, then the student passes the course.”
- (T,T)
Say the student passes the exam and passes the course, then clearly \(P \implies Q\) is true.
- (T,F)
Say the student passes the exam, but fails the course. Clearly the statement is wrong and so \(P \implies Q\) is false. The author lied!
- (F,T)
Say they failed the exam, but passed the course. Well this is indeed possible — perhaps the exam was very nasty and the author was very impressed by the only-just-fail (and maybe some good homework) and so gave a passing mark overall. The statement is not false and so must be true. \(P \implies Q\) is true.
- (F,F)
Say the student fails the exam and fails the course. Well the statement is not false and so must be true. Hence \(P \implies Q\) is true.
Another good example (which the author has used quite a lot when teaching) is
If he is Shakespeare then he is dead.
―No one ever actually said this (well — except just now)
- (T,T)
Here is Shakespeare and, sure-enough, he is looking pretty dead
25 . So the implication above is not a lie.
- (T,F)
I found Shakespeare and he is up and about looking very well! The implication above is wrong and \(P \implies Q\) is false. Also we should all learn what his secret is since he is over 450 years old!
- (F,T)
Here is Chrisopher Marlowe
26 and he is not-alive. This does not actually invalidate the implication — it is still true.
- (F,F)
Consider a very alive modern writer — despite their accomplishments they are not Shakespeare.
27 . Again, this does not invalidate the implcation —so it is still true.
So perhaps the most important thing to re-emphasise at this point is that an implication statement is false only when it fails to deliver it’s claim. That is, when we find a situation in which the hypothesis is true but the conclusion is false.
As we noted above, a very large number of mathematical statements we want to prove take the form of an implication. For example:
If \(n\) is even then \(n^2\) is even
When we construct the proof of such a statement we need to demonstrate that it is always true and never false. To understand how we do so, consider again the four rows of the truth table.
| \(P\) |
\(Q\) |
\(P \implies Q\) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
Notice that the implication is true in three of those cases and only false in one case — namely when the hypothesis is true and the conclusion is false. So our proof needs to show that this possibility cannot happen.
- Hypothesis false
We can see from the truth table that the implication is always true. We don’t need to know anything about the conclusion since it doesn’t matter whether or not the conclusion is true or false. Because of this, a proof doesn’t actually have to consider this possibility explicitly. Anyone reading the proof knows
28 the truth-table of the implication and so also knows that the implication is true when the hypothesis is false.
- Hypothesis true
We will have to work, since the truth-value of the implication will depend on the truth value of the conclusion. Consequently most proofs start with the assumption that the hypothesis is true and then work towards showing that the conclusion must be true.
In a more linguistic context, the hypothesis is the protasis and the conclusion is the apodosis.
wikipedia.org/wiki/Down_the_Rabbit_Hole
If one is not careful, you can end up on a long digression into dead parrots, pet-shop sketches, and the history of British comedy around here.
There is (was?) a theory that Marlowe faked his own death and then started writing under the name “William Shakespeare” — though this is not widely accepted. People who promulgated this theory were called Marlovians.You can search-engine your way to some interesting articles on Marlowe.
I’m sure you can find a few with the help of your favourite search-engine or online purveyor of books. You might even be lucky enough to study on a campus that that has a bookstore that still sells actual books.
