Why does proof by contrapositive make intuitive sense?

Solution 1:

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

Solution 2:

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

enter image description here

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.

enter image description here

Solution 3:

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.

Solution 4:

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?

Solution 5:

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: