Proving an implication

One of most common thing you would prove in this course is an implication, i.e. a logical statement of the form $P\implies Q$. In this note, we will recap some common ways to prove an implication.

Note that if S not a subset of T then one can only conclude that there is an x in S but not in T. However, we cannot conclude that there is an y in T but not in S (because the latter can be true even if S is a subset of T).

The Basics

Many of the proofs we will encounter in this course will be required to prove logical statements of the form:

If blah then blah',

which is logically equivalent to the form $P\implies Q$ (where in this case $P$ stands for blah and $Q$ stands for blah'). In this section we will see many ways to prove such a statement. To do that we will consider the following exercise throughout:

Exercise 1

Prove the following. If every human who is active also has blue eyes, then every human who is active and is curious also has blue eyes and is curious.

To solve the above problem, it would be useful to convert this into an implication. Let $A$ denote the set of all humans who are active, $B$ denote the set of all humans with blue eyes and $C$ denote the set of all curious humans. Then Exercise 1 is exactly the same as proving

Exercise 2

If $A\subseteq B$, then for any set $C$, $A\cap C \subseteq B\cap C$.

Before we go on to present multiple ways to prove an implication, here are two remarks:

Instead of using operators on sets, we could also have used logic. In particular, here is the equivalent first order logic statement \[\left( \forall x (x\in A \implies x\in B)\right)\implies \left(\forall y(y\in A \cap C \implies y\in B\cap C)\right),\] or further \[\left( \forall x (x\in A \implies x\in B)\right)\implies \left(\forall y(y\in A \wedge y\in C \implies y\in B\wedge y\in C)\right),\] where recall "$\wedge$" is the logical AND function.
We remark that Exercise 2 is true for arbitrary sets $A$, $B$ and $C$ while Exercise 1 is for specific sets. However, note that Exercise 1 does not specify anything about the humans in $A$, $B$ and $C$ other than their attributes (i.e. humans who are active, are blue-eyed and are curious respectively). Even though in English being active, having blue-eyed or being curious have specific meanings, variables in mathematics have no specific meaning. So e.g. Exercise 2 would work even if $A$, $B$ and $C$ are goats who are active, are blue-eyed and are curious respectively. Or even if $A$, $B$ and $C$ were humans who were aggressive, are brown-skinned and cold-blooded respectively. This distinction between meanings in English and mathematical variables is an important distinction and something that you should keep in mind throughout the course.

We begin with a common mis-understanding.

A mis-understanding

Here is a common mistake when one encounters $P\implies Q$. Looking at Exercise 1, one might say "I know someone who is active and has brown eyes," e.g. this guy

and then conclude that $A\not\subseteq B$ and hence the statement in Exercise 1 is false.

The above happens because of a mis-understanding of the logical expression $P\implies Q$. If $P$ is false then logically the statement $P\implies Q$ is true. Hence, we "only" need to worry about the case when $P$ is true and then also prove that $Q$ is true. This leads to the first way to prove implications.

Trick 1: Assume $P$. Then prove $Q$

The "simplest" way to prove $P\implies Q$ is the following:

Trick 1 (direct argument)

Assume that the statement $P$ is true. Then with this assumption, prove that $Q$ is true.

Next, we use this trick to solve Exercise 1:

Proof Idea (Ex 1)

We will assume that $A\subseteq B$. Then we will argue that $A\cap C\subseteq B\cap C$. To do this, we will use the logical forms of these statements mentioned in the first section.

Proof Details

Assume $A\subseteq B$. This implies for for every $x\in A$, we have $x\in B$. Now consider an arbitrary $y\in A\cap C$, which implies that $y\in A$ and $y\in C$. Now by the assumption $A\subseteq B$, we have $y\in B$, i.e. $y\in B$ and $y\in C$, which by definition, implies that $y\in B\cap C$. Since the choice of $y$ was arbitrary, we have $A\cap C\subseteq B\cap C$, as desired.

Trick 1': Case Analysis

A special case of Trick 1, which is pretty useful is to break up the assumption into cases that cover all the possibilities. In particular,

Trick 1' (case analysis)

Let $P$ be of the form $P_1\vee P_2\vee \cdots \vee P_m$. Then for $i=1,\dots,m$ do the following:
- Assume $P_i$ is true. Then prove $Q$.
Conclude that $P\implies Q$.

In the above $P_1,\dots,P_m$ are the cases. As an exercise,

Exercise 3

Convince yourself that the case analysis above indeed proves $(P_1\vee P_2\vee \cdots \vee P_m)\implies Q$.

We illustrate the trick above with the following exercise:

Exercise 4

Prove the following. For any real number $x$, if $|x-3|\ge 5$, then either $x\ge 7$ or $x\le -1$.

Proof Idea (Ex 4)

Define $P_1= x\ge 8$ and $P_2= x\le -2$. Note that $|x-3|\ge 5$ is equivalent to $P_1\vee P_2$. We will prove the result by a case analysis.

Proof Details

For notational convenience define $Q= (x\ge 7)\vee (x\le -1)$. We do a case analysis:

(Case 1: $x\ge 8$, i.e. $P_1$ is true.) Note that since $x\ge 8$ it is also true that $x\ge 7$ and hence $Q$ is true.
(Case 2: $x\le -2$, i.e. $P_2$ is true.) Note that since $x\le -2$ it is also true that $x\le -1$ and hence $Q$ is true.

Since $|x-3|\ge 5$ implies either Case 1 or Case 2 is true, we have proved that $P_1\vee P_2\implies Q$, as desired.

Trick 2: Assume $\neg Q$. Then prove $\neg P$

The next trick is to use the fact that $\neg Q\implies \neg P$ is logically equivalent to $P\implies Q$:

Trick 2 (prove a logically equivalent form)

First assume that $\neg Q$ is true (i.e. $Q$ is false). Then prove that $\neg P$ is true (i.e. $P$ is false).

Next, we use this trick to solve Exercise 1.

Proof Idea 2 (Ex. 1)

We will assume that $A\cap C\not\subseteq B\cap C$. Then we will argue that $A\not\subseteq B$. To do this, we will use the logical forms of these statements from the first section.

Proof Details

Assume that $A\cap C\not\subseteq B\cap C$. That is, there is an $x$ such that $x\in A\cap C$ but $x\not\in B\cap C$.¹ Note that $x\in A\cap C$ implies that $x\in A$ and $x\in C$. On the other hand, $x\not\in B\cap C$ means that either $x\not \in B$ or $x\not\in C$. These two conclusions imply that $x\in A$ but $x\not\in B$. This in turn implies that $A\not\subseteq B$, as desired.

Trick 3: Proof by Contradiction

Proof by contradiction is a very general (and useful) proof technique, where the idea is to assume the negation of what you're trying to prove and then come up with a contradiction (i.e. where you prove both a statement and its negation to be true). In the context of proving $P\implies Q$, this generally takes the following form:

Trick 3 (proof by contradiction)

Assume both $P$ and $\neg Q$. Then arrive at a contradiction.

We now use this trick to solve Exercise 1.

Proof Idea 3 (Ex. 1)

We will assume that both $A\subseteq B$ and $A\cap C\not\subseteq B\cap C$ and then arrive at a contradiction. To do this, we will use the logical forms of these statements from the first section.

Proof Details

Let us assume that both $A\subseteq B$ and $A\cap C\not\subseteq B\cap C$ are true. The first assumption implies that for every $x$ such that $x\in A$ it is true that $x\in B$. The second assumption implies that there exists a $y\in A\cap C$ such that $y\not\in B\cap C$. The latter implies that

$y\in A$
$y\in C$
Either $y\not\in B$ or $y\not\in C$

Now note that (ii) and (iii) imply that $y\not\in B$. This along with (i) implies that $y\in A$ but $y\not\in B$ but this contradicts our first assumption.

Which trick should I apply?

You might have noted that the three solutions to Exercise 1 are similar. A natural question to ask is if there is a way to decide when one should use a particular trick. Unfortunately, the answer is that there is no mechanical way to do this. The more proofs you write the better you will get at picking the "correct" trick. (By correct I mean that sometimes a certain proof trick leads to a much simpler proof than what one gets by applying the other tricks and the "trick" is to figure out which one to pick.) When you are starting off pretty much the only choice you have is to try out all the tricks one by one and see which one works.