% Part: methods
% Chapter: proofs
% Section: proof-by-contradiction

\documentclass[../../../include/open-logic-section]{subfiles}

\begin{document}

\olfileid{mth}{prf}{con}

\olsection{Proof by Contradiction} 

In the first instance, proof by contradiction is an inference pattern
that is used to prove negative claims.  Suppose you want to show that
some claim~$p$ is \emph{false}, i.e., you want to show~$\lnot p$.  The
most promising strategy is to (a) suppose that $p$~is true, and (b)
show that this assumption leads to something you know to be false.
``Something known to be false'' may be a result that conflicts
with---contradicts---$p$ itself, or some other hypothesis of the
overall claim you are considering.  For instance, a proof of ``if $q$
then $\lnot p$'' involves assuming that $q$~is true and proving~$\lnot
p$ from it. If you prove $\lnot p$ by contradiction, that means
assuming $p$ in addition to~$q$. If you can prove $\lnot q$ from $p$,
you have shown that the assumption~$p$ leads to something that
contradicts your other assumption~$q$, since $q$~and $\lnot q$ cannot
both be true.  Of course, you have to use other inference patterns in
your proof of the contradiction, as well as unpacking definitions.
Let's consider an example.

\begin{prop}
  If $A \subseteq B$ and $B = \emptyset$, then $A$ has no !!{element}s.
\end{prop}

\begin{proof}
  Suppose $A \subseteq B$ and $B = \emptyset$. We want to show that
  $A$ has no !!{element}s.
  \begin{quote}
    Since this is a conditional claim, we assume the antecedent and
    want to prove the consequent. The consequent is: $A$ has no
    !!{element}s. We can make that a bit more explicit: it's not the
    case that there is an~$x \in A$.
  \end{quote}
  $A$ has no !!{element}s iff it's not the case that there is an~$x$
  such that $x \in A$.
  \begin{quote}
    So we've determined that what we want to prove is really a
    negative claim~$\lnot p$, namely: it's not the case that there is
    an $x \in A$.  To use proof by contradiction, we have to assume the
    corresponding positive claim~$p$, i.e., there is an $x \in A$, and
    prove a contradiction from it.  We indicate that we're doing a
    proof by contradiction by writing ``by way
    of contradiction, assume'' or even just ``suppose not,'' and then state
    the assumption~$p$.
  \end{quote}
  Suppose not: there is an $x \in A$.
  \begin{quote}
    This is now the new assumption we'll use to obtain a
    contradiction. We have two more assumptions: that $A \subseteq B$
    and that $B = \emptyset$. The first gives us that $x \in B$:
  \end{quote}
  Since $A \subseteq B$, $x \in B$.
  \begin{quote}
    But since $B = \emptyset$, every !!{element} of $B$ (e.g., $x$)
    must also be !!a{element} of~$\emptyset$.
  \end{quote}
  Since $B = \emptyset$, $x \in \emptyset$. This is a contradiction,
  since by definition $\emptyset$ has no !!{element}s.
  \begin{quote}
    This already completes the proof: we've arrived at what we need (a
    contradiction) from the assumptions we've set up, and this means
    that the assumptions can't all be true. Since the first two
    assumptions ($A \subseteq B$ and $B = \emptyset$) are not
    contested, it must be the last assumption introduced (there is an
    $x \in A$) that must be false. But if we want to be thorough, we
    can spell this out.
  \end{quote}
  Thus, our assumption that there is an $x \in A$ must be false, hence,
  $A$ has no !!{element}s by proof by contradiction.
\end{proof}

Every positive claim is trivially equivalent to a negative claim: $p$
iff $\lnot\lnot p$.  So proofs by contradiction can also be used to
establish positive claims ``indirectly,'' as follows: To prove~$p$,
read it as the negative claim $\lnot\lnot p$. If we can prove a
contradiction from $\lnot p$, we've established $\lnot\lnot p$ by
proof by contradiction, and hence~$p$.

In the last example, we aimed to prove a negative claim, namely that
$A$ has no !!{element}s, and so the assumption we made for the purpose
of proof by contradiction (i.e., that there is an $x \in A$) was a
positive claim. It gave us something to work with, namely the
hypothetical $x \in A$ about which we continued to reason until we got
to $x \in \emptyset$.

When proving a positive claim indirectly, the assumption you'd make
for the purpose of proof by contradiction would be negative. But very
often you can easily reformulate a positive claim as a negative claim,
and a negative claim as a positive claim.  Our previous proof would
have been essentially the same had we proved ``$A = \emptyset$''
instead of the negative consequent ``$A$ has no !!{element}s.'' (By
definition of $=$, ``$A = \emptyset$'' is a general claim, since it
unpacks to ``every !!{element} of~$A$ is an !!{element} of~$\emptyset$
and vice versa''.) But it is easily seen to be equivalent to the
negative claim ``not: there is an $x \in A$.''

So it is sometimes easier to work with $\lnot p$ as an assumption than
it is to prove~$p$ directly.  Even when a direct proof is just as
simple or even simpler (as in the next examples), some people prefer to
proceed indirectly.  If the double negation confuses you, think of a
proof by contradiction of some claim as a proof of a contradiction
from the \emph{opposite} claim. So, a proof by contradiction of $\lnot
p$ is a proof of a contradiction from the assumption~$p$; and proof by
contradiction of~$p$ is a proof of a contradiction from~$\lnot p$.

\begin{prop}
$A \subseteq A \cup B$.
\end{prop}

\begin{proof}
  We want to show that $A \subseteq A \cup B$.
  \begin{quote}
    On the face of it, this is a positive claim: every $x \in A$ is
    also in $A \cup B$.  The negation of that is: some $x \in A$ is
    $\notin A \cup B$. So we can prove the claim indirectly by
    assuming this negated claim, and showing that it leads to a
    contradiction.
    \end{quote}
  Suppose not, i.e., $A \nsubseteq A \cup B$.
  \begin{quote}
    We have a definition of $A \subseteq A \cup B$: every $x \in A$ is
    also $\in A \cup B$.  To understand what $A \nsubseteq A \cup B$
    means, we have to use some elementary logical manipulation on the
    unpacked definition: it's false that every $x \in A$ is also $\in
    A \cup B$ iff there is \emph{some}~$x \in A$ that is $\notin C$.
    (This is a place where you want to be very careful: many students'
    attempted proofs by contradiction fail because they analyze the
    negation of a claim like ``all $A$s are $B$s'' incorrectly.) In
    other words, $A \nsubseteq A \cup B$ iff there is an $x$ such that
    $x \in A$ and $x \notin A \cup B$. From then on, it's easy.
  \end{quote}
  So, there is an $x \in A$ such that $x \notin A \cup B$.  By
  definition of $\cup$, $x \in A \cup B$ iff $x \in A$ or $x \in
  B$. Since $x \in A$, we have $x \in A \cup B$. This contradicts the
  assumption that $x \notin A \cup B$. 
\end{proof}

\begin{prob}
Prove \emph{indirectly} that $A \cap B \subseteq A$.
\end{prob}

\begin{prop}
If $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$.
\end{prop}

\begin{proof}
  Suppose $A \subseteq B$ and $B \subseteq C$. We want to show $A
  \subseteq C$.
  \begin{quote}
    Let's proceed indirectly: we assume the negation of what we want
    to etablish.
  \end{quote}
  Suppose not, i.e., $A \nsubseteq C$.
  \begin{quote}
    As before, we reason that $A \nsubseteq C$ iff not every $x \in A$
    is also $\in C$, i.e., some $x \in A$ is $\notin C$.  Don't worry,
    with practice you won't have to think hard anymore to unpack
    negations like this.
  \end{quote}
  In other words, there is an~$x$ such that $x \in A$ and $x \notin C$.
  \begin{quote}
    Now we can use this to get to our contradiction. Of course, we'll
    have to use the other two assumptions to do it.
  \end{quote}
  Since $A \subseteq B$, $x \in B$. Since $B \subseteq C$, $x \in
  C$. But this contradicts $x \notin C$.
\end{proof}

\begin{prop}
If $A \cup B = A \cap B$ then $A = B$.
\end{prop}

\begin{proof}
  Suppose $A \cup B = A \cap B$. We want to show that $A = B$.
  \begin{quote}
    The beginning is now routine:
  \end{quote}
  Assume, by way of contradiction, that $A \neq B$.
  \begin{quote}
    Our assumption for the proof by contradiction is that $A \neq
    B$. Since $A = B$ iff $A \subseteq B$ an $B \subseteq A$, we get
    that $A \neq B$ iff $A \nsubseteq B$ \emph{or} $B \nsubseteq
    A$. (Note how important it is to be careful when manipulating
    negations!{}) To prove a contradiction from this disjunction, we
    use a proof by cases and show that in each case, a contradiction
    follows.
  \end{quote}
  $A \neq B$ iff $A \nsubseteq B$ or $B \nsubseteq A$. We distinguish
  cases.
  \begin{quote}
    In the first case, we assume $A \nsubseteq B$, i.e., for some $x$,
    $x \in A$ but $\notin B$. $A \cap B$ is defined as those
    !!{element}s that $A$ and $B$ have in common, so if something
    isn't in one of them, it's not in the intersection. $A \cup B$ is
    $A$ together with $B$, so anything in either is also in the
    union. This tells us that $x \in A \cup B$ but $x \notin A \cap
    B$, and hence that $A \cap B \neq A \cup B$.
  \end{quote}
  
  Case 1: $A \nsubseteq B$. Then for some $x$, $x \in A$ but $x \notin
  B$. Since $x \notin B$, then $x \notin A \cap B$. Since $x \in A$,
  $x \in A \cup B$. So, $A \cap B \neq A \cup B$, contradicting the
  assumption that $A \cap B = A \cup B$.

  Case 2: $B \nsubseteq A$. Then for some $y$, $y \in B$ but $y \notin
  A$. As before, we have $y \in A \cup B$ but $y \notin A \cap B$, and
  so $A \cap B \neq A \cup B$, again contradicting $A \cap B = A \cup
  B$. 
\end{proof}

\end{document}