0.5: Proof Templates

Last updated
Save as PDF

Page ID: 132680

\( \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}}\)

Proof Templates

To prove injective relationship (ie prove one to one)
Is \(f(x_1) = f(x_2)\)?

YES then you need to prove \(x_1=x_2\).

Let \(A\) be a set. Let \(x_1,x_2 \in A\) such that \(f(x_1)=f(x_2)\).

⠇

Show \(x_1=x_2\).

NO then you need to provide one counterexample where \(x_1 \ne x_2\) when \(f(x_1) = f(x_2)\).

Is there a surjective relationship (i.e. prove onto)?

YES Note we are starting from \(f: A \rightarrow B\). Thus \(f(A)\subseteq B\) by definition.

Let \(A\) and \(B\) be sets where \(A\) is onto \(B\) if and only if \(f(A) \subseteq B\) and \(B \subseteq f(A)\).

By definition, \(f(A) \subseteq B\). Next show \(B \subseteq f(A)\).

Let \(x \in B\).

⠇

Show \(x \in f(A)\).

Conclude with: Since \(f(A) \subseteq B\) and \(B \subseteq f(A)\) therefore \(f\) is onto.◻

NO then need to find a counterexample where \(b \in B\), but there is no \(a \in A\) whereby \(f(a)=b\).

Reflexive, Symmetric, Anti Symmetric, Transitive Property Proofs

Need a non empty set \(A\) and a relation \(R\).

Reflexive

Let \(a \in A\). ← Starting point

⠇

Show \(aRa\) ← Ending point

Symmetric

Let \(a, b \in A\) s.t. \(aRb\).

⠇

Show \(bRa\)

Antisymmetric

Let \(a,b \in A\) s.t. \(aRb\) and \(bRa\)

⠇

Show \(a=b\).

Transitive

Let \(a,b,c \in A\) s.t. \(aRb\) and \(bRa\).

⠇

Show \(aRc\).