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

To prove injective relationship (ie prove one-to-one)

YES If \(f(x_1) = f(x_2)\) 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\).