Recall from Wednesday how to prove a statement with “for all” or “there exists”.

Recipe for proving a “for all” statement:

<aside>

Proposition. For all $x$, $P(x)$.

Proof. Suppose $x$. … Therefore $P(x)$.

</aside>

Recipe for proving a “there exists” statement.

<aside>

Proposition. There exists an $x$ such that $P(x)$.

Proof. Let $x$ be… [describe a specific example]. … Therefore $P(x)$.

</aside>

Today we’ll talk about how to disprove a false statement. The main idea:

<aside> 💡

To disprove $P$, we prove $\mathord{\sim} P$.

</aside>

If $P$ involves an “and” or an “or”, we’ll need De Morgan’s laws to understand what $\mathord{\sim} P$ means:

$$ \begin{aligned} \mathord{\sim}(P \vee Q) \quad&=\quad \mathord{\sim}P \wedge \mathord{\sim}Q \\ \mathord{\sim}(P \wedge Q) \quad&=\quad \mathord{\sim}P \vee \mathord{\sim}Q \end{aligned} $$

What about negating a conditional statement? Recall from Monday’s activity that $P \Rightarrow Q$ is equivalent to $\mathord{\sim} P \vee Q$. So:

$$ \begin{aligned} \mathord{\sim} (P \Rightarrow Q) \quad&=\quad \mathord{\sim}(\mathord{\sim} P \vee Q) \\ &=\quad P \wedge \mathord{\sim}Q \end{aligned} $$

How do we negate statements with quantifiers?

$$ \begin{aligned} \mathord{\sim} (\forall x, P(x)) \quad&=\quad \exists x, \mathord{\sim}P(x)\\ \mathord{\sim} (\exists x, P(x)) \quad&=\quad \forall x, \mathord{\sim}P(x)\\ \end{aligned} $$

Example. Disprove the following: if $n \in \mathbb{Z}$ and $n^5 - n$ is even, then $n$ is even.

We could write this symbolically:

$$ \forall n \in \mathbb{Z}, (n^5 - n\text{ is even}) \Rightarrow (n\text{ is even}) $$

We need to prove: