# Why does proof by contrapositive make intuitive sense?

If you have two statements P and Q, and we say that P implies Q, that suggests that P contains Q. So if we have P, we must have Q because it is contained within P. This is my intuitive understanding of the implication.

On the other hand, if we do not have Q, by my example above it would not imply that we do not have P, since Q is only one of the things contained within P. So why would showing that when we don't have Q we don't have P prove the implication?

In short, what understanding of the material implication is needed for proof by contrapositive to make intuitive sense? I understand the truth tables are the same, but that does not provide intuition in my opinion.

• When you say that $P\implies Q$ you are saying that if $P$ is true then it is necessary that $Q$ be true. Therefore, if $Q$ is not true then neither is $P$ because $Q$ would have to be true. – John Douma Jul 25 '16 at 3:29
• You don't have Q. You either have P or you don't. If you have P then you must also have Q. But you don't. So it is impossible you have have P. So you don't have P, do you? – fleablood Jul 25 '16 at 3:49
• Q may be only one of the things P has. But it's a required thing P. If I have P, I absolutely must at risk of the universe imploding also have Q. But you want to know a secret? I don't have Q. How is that possible? We were told if I had P then I absolutely positive must have Q. But I don't have Q. How can that possibly be possible? – fleablood Jul 25 '16 at 4:11
• It would be $P$ contains $Q$ in the sense that $Q$ is a subset of $P$. This is the case if and only if the complement of $P$ is a subset of the complement of $Q$. – André Nicolas Jul 25 '16 at 4:13
• If proof by contrapositive doesn't make sense, I'm a banana. – Robert Furber Jul 25 '16 at 11:42

Since it seems you are thinking in terms of subsets, It is like saying that if $P\supseteq Q$ then $Q^c\supseteq P^c$ (in the sense that if $P$ is the set of all things we know to be true as our hypothesis, then the entirety of $Q$ is among those things we know as a result to be true. On the other hand if $Q^c$ is the set of all things we know to be true, then the entirety of $P^c$ is among the things we know to be true)

In the following image, $P$ contains $Q$ as a subset. The lighter shade indicates that it is used by both $P$ and $Q$.

On the other hand, looking at the complements, the area outside of $Q$ (part, not all, of which is red) contains the area outside of $P$ (in pink) as a subset. Again, the lighter shade is the area used in both.

• Thank you for the illustrated response! I have a follow up question; if we show that not having Q leads to not having P, it could imply that P contains Q, but it could it not also imply that Q contains P? Intuitively, it seems that both cases would allow you to show that not having Q leads to not having P. So how are we able to conclude with certainty that P contains Q just by showing that not having Q leads to not having P? – IgnorantCuriosity Jul 26 '16 at 17:00
• @ $\neg Q\implies \neg P$ is logically equivalent to $P\implies Q$. It isn't just "it could imply it" it is that it does imply it. The explanation is the same with just a relabeling of the spaces. I personally still find the most convincing argument the one involving truth tables. $(P\implies Q)$ is logically equivalent to $((\neg P) \vee Q)$ by definition. – JMoravitz Jul 26 '16 at 17:07
• But why could showing ¬Q⟹¬P also not imply that Q contains P? – IgnorantCuriosity Jul 26 '16 at 17:27
• @IgnorantCuriosity it doesn't imply it, although it could be the case. When we talk about one thing implying another, we want it to always be the case with no counterexamples, regardless of what $P$ and $Q$ actually are. There are some choices of $P$ and $Q$ where it does. There are also some choices of $P$ and $Q$ where it doesn't. – JMoravitz Jul 26 '16 at 17:39
• @IgnorantCuriosity Q = "$x$ has four legs", P = "$x$ is a healthy horse". You have $P\implies Q$ reads as "If $x$ is a healthy horse, then it has four legs." You have $\neg Q\implies \neg P$ reads "If $x$ does not have four legs, then it is not a healthy horse." Both of those are true statements. You have $Q\implies P$ reads "If $x$ has four legs then it is a healthy horse" That is false, as the desk my computer is sitting on has four legs but it certainly isn't a horse. Similarly, $\neg P\implies \neg Q$ is false since despite my desk not being a horse, it has four legs. – JMoravitz Jul 26 '16 at 17:50

If you want to have a "set containment" kind of intuition, you should probably do the opposite: thinking of $P \implies Q$ as $P \subseteq Q$. The intuition is that if you are in some situation where $P$ is true (i.e. "being contained in $P$") then $Q$ is also true for this situation ("contained in $Q$"). In particular, $Q$ may contain more than just $P$, and this makes clear that there are situations where $Q$ is true but $P$ is false. (For example, "$n$ is a multiple of $4$" implies "$n$ is even" but there are numbers like $n=6$ that are even but not multiples of $4$.)

With the correct set-containment formulation, it is easy to see the contrapositive is equivalent. $\lnot Q \implies \lnot P$ can be thought of as $Q^c \subseteq P^c$ where the $c$ denotes set complement, and you can see that this is equivalent to $P \subseteq Q$.

One situation where this set containment idea is realized is in probability of events. For example, $X > 4$ implies $|X| > 4$, so we have $\{X > 4\} \subseteq \{|X| > 4\}$ and $\mathbb{P}(X>4) \le \mathbb{P}(|X|>4)$.

Edit: I should mention that your setup can still show that the contrapositive is equivalent (see JMoravitz's answer). You just have to stay consistent with your setup: the set $P$ denotes all hypotheses that $P$ implies. Under your setup, if $Q$ is not true, then the complement of $Q$ contains all of the complement of $P$, so $\lnot Q \implies \lnot P$, even though the complement of $Q$ can still contain some things in $P$.

• Thank you. The difference between your answer and the one provided by JMoravitz brought another question to mind: is P supposed to contain Q or is Q supposed to contain P? Is there any standard for this, or does it vary with the details of the material implication? – IgnorantCuriosity Jul 26 '16 at 11:50
• @IgnorantCuriosity I think you should ask JMoravitz (or also Tanner whose answer considers both cases). I have only ever seen the $P \subseteq Q$ interpretation but that may be because I've been doing a lot of probability recently. – angryavian Jul 26 '16 at 16:50

if $P$ is true, then $Q$ has to be true.

But then suppose that $P$ is true, and $Q$ is false. But, we already said that if $P$ is true, then $Q$ had to be true. Thus, this is an impossibility. Therefore, we can conclude that $P$ is false.

The true statement of the contrapositive isn't qualified with a truth value, in the way I've done above, but this is a way to think about it.

$P \implies Q \iff \neg Q \implies \neg P$ is of course easily verified with a truth table as well.

You're asking for intuitive sense, and the other answers are great at the logical proofs, but for intuition I like concrete examples.

If I have tomatoes, I must have gone to the store.
\--------v-------/  \-------------v-------------/
P                        Q


Contrapositive:

If I didn't go to the store, I can't have tomatoes.
\-----------v-------------/  \---------v---------/
!Q                         !P


By comparison, if I don't have tomatoes I don't know whether I went to the store or not. I may have gone and just not bought them. Same with having gone to the store -- may or may not have bought tomatoes.

Does that help?

I think this comes down to what it means for one proposition to "contain" another proposition. There are two ways of thinking about this, and both ways of thinking are valid, but they are incompatible.

Let's talk about predicates instead of propositions, because predicates work better with "option 2" below. For the sake of example, let's consider the case where $P$ is the predicate "it is some sugar" and $Q$ is the predicate "it is sweet". (Note that, of course, all sugar is sweet, so $P$ implies $Q$.)

## Option 1: Predicates "contain" all of the criteria that they entail

We could think of a predicate as "containing" or "being made of" all of the conditions or criteria that the predicate entails—all of the things that must be true in order for the predicate to hold.

For example, some of the criteria that the predicate "it is sugar" entails are "it is a chemical substance", "it is a solid at room temperature", and "it can be tasted".

Now, you wrote in your question:

If you have two statements P and Q, and we say that P implies Q, that suggests that P contains Q. So if we have P, we must have Q because it is contained within P. This is my intuitive understanding of the implication.

This understanding meshes with "option 1" here. The predicate "it is sugar" can be said to "contain" the predicate "it is sweet", because all of the "criteria for sweetness" are also necessary conditions for being sugar.

However, the next part of your question doesn't mesh with "option 1" at all:

On the other hand, if we do not have Q, by my example above it would not imply that we do not have P, since Q is only one of the things contained within P.

Yes, it's true that if you have something that isn't sweet, then that thing has failed only one of the criteria for being sugar. But one is all that it takes: if something has failed even just one criterion for being sugar, then that thing cannot be sugar.

## Option 2: Predicates "contain" all of the things that they hold true for

We could think of a predicate as "containing" or "being made of" all of the things that the predicate is true for. So the predicate "it is sugar" is made of all things that are sugar, and the predicate "it is sweet" is made of all things that are sweet.

Notice that now the containment relationship is "backwards". All things which are sugar are also sweet, so the collection of all sweet things contains the collection of all sugar (we are saying that $Q$ contains $P$ now).

Let's look at the second part of your question under this interpretation:

On the other hand, if we do not have Q, by my example above it would not imply that we do not have P, since Q is only one of the things contained within P.

Under the "option 2" interpretation, $Q$ actually does contain all of the things that $P$ contains. So if we have something which is not in $Q$ (something which is not sweet), then it cannot be in $P$ (it cannot be sugar), either.

• Thank you for the detailed response. I'd like to ask you the same question I asked JMoravitz above. If we show that not having Q leads to not having P, it could imply that P contains Q, but it could it not also imply that Q contains P? Intuitively, it seems that both cases would allow you to show that not having Q leads to not having P. So how are we able to conclude with certainty that P contains Q just by showing that not having Q leads to not having P? – IgnorantCuriosity Jul 26 '16 at 17:05

It seems to me that Parmenides got it right:

"The only roads of enquiry there are to think of: one, that it is and that it is not possible for it not to be, this is the path of persuasion (for truth is its companion); the other, that it is not and that it must not be — this I say to you is a path wholly unknowable."