0.5: Proof Strategies: A Quick Reference (Summary)
- Page ID
- 132680
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\ket}[1]{\left| #1 \right>}\)
\(\newcommand{\bra}[1]{\left< #1 \right|}\)
\(\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}\)
\(\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}\)
\(\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}\)
\(\newcommand{\op}[1]{\hat{\mathbf{#1}}}\)
\(\newcommand{\expect}[1]{\langle #1 \rangle}\)
\(\newcommand{\dfn}[1]{\emph{\textbf{#1}}}\)
From DR. Thi Dinh's Proof Writing Handbook, this Bible:
In the beginning...
Let \(P\) and \(Q\) be statement variables. When needed, suppose that P = P(x) depends on a variable x. The symbol "\(\forall\)" means "for all" or "for any". The symbol \(\exists\) means "there exists".
| Type of statement | What must we do to prove that it is true |
|
(1) If \(P\), then \(Q\) (2) \(\forall P\), \(Q\) |
Suppose that \(P\) is true. Prove that \(Q\) is true. |
| (3) \(\exists x P(x) \) such that \(Q\) |
Choose \(x\) so that \(P(x)\) is true. Prove that \(Q\) is true. Note: You need not explain how you find \(x\). |
The first (and only) commandment
To prove that a statement is false, thou shalt write out the negation of the statement and prove that.
Negation statements with Quantifiers:
\(\neg(\forall x\,\exists y\,P(x,y))\equiv \exists x\,\forall y\,\neg P(x,y)\) and \(\neg(\exists y\, \forall x\, P(x,y)) \equiv\forall y\,\exists y\,\neg P(x,y).\)
To prove set equality
\(A=B,\) prove both \(A\subseteq B\) and \(B\subseteq A.\)
If and Only If Proofs
To prove
\(P\iff Q,\) prove both \(P\Rightarrow Q\) and \(Q\Rightarrow P.\)
To prove a well-defined function is injective (i.e,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)\).
To prove a well-defined function is surjective (i.e., prove onto)?
YES. Note that we start with \(f: A \rightarrow B\). Thus \(f(A)\subseteq B\) by definition.
Let \(A\) and \(B\) be sets where a function \(f\) is surjective 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 we need to find a counterexample where \(b \in B\), but there is no \(a \in A\) such that \(f(a)=b\).
Reflexive, Symmetric, Antisymmetric, 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 \(bRc\).
⠇
Show \(aRc\).