3.5: Proof by Contradiction

Last updated
Save as PDF

Page ID: 88856

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The first proofs we worked started with the condition, applied definitions, and previous theorems, one by one until we arrived at the conclusion. These are called direct proof. Now we will look at the first alternate. In these proofs we begin by supposing our conclusion is wrong and then applying definitions and previous theorems one by one until we run into a problem.

First proof using contradiction

Definition \(\PageIndex{1}\): Mapping Composition.

For two mappings \(g:A \to B\) and \(f:B \to C\), the composition of those mappings, denoted \(f \circ g\), is the mapping \(h:A \to C\) defined by \(h(x)=f(g(x))\)

The following proof has two parts. The first is a direct proof, and the second is a proof by contradiction.

Theorem \(\PageIndex{2}\): The composition of two functions is a function.

If the mappings \(g:X \to Y\) and \(f:Y \to Z\) are functions, then the composition \(h(x)=f(g(x))\) is a function.

Proof

First we show that for each element of the domain there exists an element in the codomain to which it is mapped. Let \(x \in X\). Because gg is a function there exists a \(y \in Y\) such that \(g(x)=y\) Because ff is a function, there exists a \(z \in Z\) such that \(f(y)=z\). This means for all \(x \in X\) there exists a \(z \in Z\) such that \(h(x)=z\).

Second we show that each element of the domain is mapped to a unique element of the codomain. Suppose for sake of contadiction that there exists \(x \in X\) such that \(h(x)=z_1\) and \(h(x)=z_2\). This means that \(f(g(x))=z_1\) and \(f(g(x))=z_2\). Because gg is a function there exists a unique \(y \in Y\) such that \(g(x)=y\). Thus \(f(y)=z_1\) and \(f(y)=z_2\). But this contradicts that ff is a function which maps an element of the domain to a unique element of the codomain.

Thus the composition of two functions is a function.