After studying direct rules for conditionals, conjunctions, and disjunctions, we now consider a different proof strategy. Contradiction and indirect proof show that a statement may be established by proving that its denial leads to an impossible statement. This method is especially useful when a direct route to the conclusion is not visible. In this lesson, contradiction and indirect proof will be connected with valid argument forms and formal proof steps. :::definition[Contradiction] A contradiction is a statement that is always false. In textbook notation, a contradiction may be denoted by $F_0$. An example of a contradiction is $$\begin{equation*} p\land\neg p. \end{equation*}$$ ::: :::theorem[Rule of Contradiction] Let $p$ be a statement and let $F_0$ be a contradiction. If $\neg p\to F_0$ is true, then $p$ is true: $$\begin{equation*} \begin{array}{c} \neg p\to F_0\\ \hline p \end{array} \end{equation*}$$ ::: :::proof Given that $\neg p\to F_0$ is true, where $F_0$ is a contradiction. To prove that $p$ is true. If possible let $p$ be false. Then $\neg p$ is true. Since $\neg p\to F_0$ is true and $\neg p$ is true, Modus Ponens gives that $F_0$ is true. But $F_0$ is a contradiction and cannot be true. A contradiction. Therefore the supposition that $p$ is false is impossible. Hence $p$ is true. $\square$ ::: :::definition[Logical Form of the Rule of Contradiction] The logical implication corresponding to the Rule of Contradiction is $$\begin{equation*} (\neg p\to F_0)\to p. \end{equation*}$$ The tabular form is $$\begin{equation*} \begin{array}{c} \neg p\to F_0\\ \hline p \end{array} \end{equation*}$$ ::: :::definition[Proof by Contradiction] Let $p_1,p_2,\ldots,p_n$ be premises and let $q$ be a conclusion. To prove $$\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q \end{equation*}$$ by proof by contradiction, assume the negation $\neg q$ as an additional premise and derive a contradiction. ::: :::definition[Contradiction Form of an Argument] The validity of $$\begin{equation*} (p_1\land p_2\land\cdots\land p_n)\to q \end{equation*}$$ may be established by proving $$\begin{equation*} (p_1\land p_2\land\cdots\land p_n\land\neg q)\to F_0. \end{equation*}$$ This means that the premises together with the denial of the conclusion cannot all be true. ::: An indirect proof begins by assuming the opposite of what must be proved. Then the assumption is combined with the premises and known rules of inference. If the steps produce a contradiction such as $r\land\neg r$, the temporary assumption must be rejected. Therefore the original conclusion must hold. Students should write the contradiction explicitly, because it explains why the assumed negation fails. Proof by contradiction has a temporary assumption that must be tracked carefully. Use the steps to follow the solved argument from the assumption $\neg p$ to the contradiction $r\land\neg r$. Each step records which premise or rule supplies the next statement. The point is not to guess the conclusion, but to see why the assumed denial cannot remain true. :::scientific-preview[Contradiction Path Explorer]