\( \def\cod{\mathop\mathrm{cod}} \) \( \def\adj{\mathop\mathrm{adj}} \) \( \def\ROP{\mathop\text{\ensuremath{\longrightarrow}}} \) \( \def\proj{\mathop\mathrm{proj}} \) \( \def\refl{\mathop\mathrm{refl}} \) \( \def\sol{\mathop\mathrm{Sol}} \) \( \def\cha{\operatorname{cha}} \) \( \def\sp{\operatorname{span}} \) \( \def\tr{\operatorname{tr}} \) \( \def\RRef{\operatorname{RRef}} \) \( \def\det{\operatorname{det}} \) \( \def\ker{\operatorname{ker}} \) \( \def\im{\operatorname{im}} \) \( \def\ran{\operatorname{ran}} \) \( \def\Null{\operatorname{Null}} \) \( \def\nullity{\operatorname{nullity}} \) \( \def\rank{\operatorname{rank}} \) \( \def\Col{\operatorname{Col}} \) \( \def\Row{\operatorname{Row}} \) \( \def\Hom{\operatorname{Hom}} \) \( \def\dom{\operatorname{dom}} \) \( \def\id{\operatorname{id}} \) \( \def\sgn{\operatorname{sgn}} \) \( \def\pty{\operatorname{pty}} \) \( \def\charpoly{\operatorname{charpoly}} \) \( \def\proj{\operatorname{proj}} \)
Write your argument in full sentences. Even displayed equations should read as full sentences with a period at the end.
Avoid starting sentences with notation.
Notation like \(\Rightarrow,\exists,\forall,\neg\) is fine when defining sets, but avoid the overuse of these symbols and \(\because,\therefore\) in the text of the proof.
Every variable needs a quantifier.
‘‘Since \(\cdots\), then \(\cdots\).’’ is incorrect grammar.
First explain what we are about to do, then do it.
Separate logical parts of the proof into paragraphs.
We show that statement \(P(x)\le Q(x)\) for all \(x\in A\).
Proof : Assume \(x\in A\).
\(\vdots\)
Hence
\[ \begin{aligned}P(x) & =\cdots\\ & \,\,\,\vdots\\ & \le\\ & \,\,\,\vdots\\ & =Q(x). \end{aligned} \]
\(\Box\)
We show that \(P(x)=Q(x)\) for all \(x\in A\).
Proof : Assume \(x\in A\).
\(\vdots\)
Hence
\[ \begin{aligned}P(x) & =\cdots\\ & \,\,\,\vdots\\ & =Q(x). \end{aligned} \]
\(\Box\)
Proof : First we show that \(P(x)\le Q(x)\) for all \(x\in A\).
\(\vdots\)
Now we show that \(P(x)\ge Q(x)\) for all \(x\in A\).
\(\vdots\)
\(\Box\)
We show that statement \(P(x)\) implies statement \(Q(x)\) for all \(x\in A\).
Proof (direct) :
Assume \(x\in A\) such that \(P(x)\) is true.
\(\cdots\)
Thus \(Q(x)\) is true.
\(\Box\)
Proof (contrapositive) :
We prove the contrapositive. Assume \(x\in A\) such that \(Q(x)\) is false.
\(\cdots\)
Thus \(P(x)\) is false.
\(\Box\)
Proof (contradiction) :
For a contradiction suppose that \(x\in A\) such that \(P(x)\) is true but \(Q(x)\) is false.
\(\cdots\) (we find something impossible)
This is a contradiction.
\(\Box\)
We show that statement \(P(x)\) is equivalent to statement \(Q(x)\) for all \(x\in A\).
Proof : ‘‘\(\Rightarrow\)’’ First we show that \(P(x)\) implies \(Q(x)\) for all \(x\in A\).
\(\cdots\)
‘‘\(\Leftarrow\)’’ Now we show that \(Q(x)\) implies \(P(x)\) for all \(x\in A\).
\(\cdots\)
\(\Box\)
We show that statement \(P(x)\) is true for some \(x\in A\).
Proof : Let \(x=\cdots\)
\(\cdots\)
Thus \(x\in A\) and \(P(x)\) is true.
\(\Box\)
We show that statement \(P(x)\) is true for a unique \(x\in A\).
Proof : First we show that \(P(x)\) is true for some \(x\in A\). Let \(x=\cdots\)
\(\cdots\)
Thus \(x\in A\) and \(P(x)\) is true.
Now we show uniqueness. Suppose that \(x,y\in A\) such that \(P(x)\) and \(P(y)\) are both true.
\(\vdots\)
Thus \(x=y\).
\(\Box\)
Given the sets \(A\) and \(B\), we show that \(A\subseteq B\).
Proof (element chasing) :
Assume \(x\in A\).
\(\vdots\)
Thus \(x\in B\).
\(\Box\)
Note: It is dangerous to start with ‘‘Let \(x\in A\)’’ because \(A\) might be the empty set.
Given the sets \(A\) and \(B\), we show that \(A\subsetneq B\).
Proof : First we show that \(A\subseteq B\). Assume \(x\in A\).
\(\vdots\)
Thus \(x\in B\).
Now we show that \(A\not=B\). Let \(y=\cdots\)
\(\vdots\)
Thus \(y\in B\) but \(y\not\in A\).
\(\Box\)
Given the sets \(A\) and \(B\), we show that \(A=B\).
Proof : ‘‘\(\subseteq\)’’ Assume \(x\in A\).
\(\vdots\)
Thus \(x\in B\).
‘‘\(\supseteq\)’’ Assume \(x\in B\).
\(\vdots\)
Thus \(x\in A\).
\(\Box\)
Proof : The result follows from the calculation
\[ \begin{aligned}x\in A & \Leftrightarrow\cdots\\ & \,\,\,\,\vdots\\ & \Leftrightarrow x\in B. \end{aligned} \]
\(\Box\)
Note: This chain of equivalent statements is very attractive but it is often difficult to do correctly.
Given the sets \(A\) and \(B\), we show that \(A\not=B\).
Proof : Let \(x=\cdots\)
\(\vdots\)
Thus \(x\in A\) but \(x\not\in B\).
\(\Box\)
Note: Another possibility is to find an \(x\in B\) such that \(x\not\in A\).
Note: Another possibility is to show that \(A\) and \(B\) have different sizes.
We show that the functions \(f:A\to B\) and \(g:X\to Y\) are equal.
Proof : First we show that \(A=B\).
\(\vdots\) (this shows that the two functions have the same domain)
Now we show that \(f(x)=g(x)\) for all \(x\in A\). If \(x\in A\), then
\[ \begin{aligned}f(x) & =\cdots\\ & \,\,\,\vdots\\ & =g(x). \end{aligned} \]
\(\Box\)
We show that the function \(f:A\to B\) is injective.
Proof : Assume \(x,y\in A\) such that \(f(x)=f(y)\).
\(\vdots\)
Thus \(x=y\).
\(\Box\)
Note: Another name for injective is one-to-one.
We show that the function \(f:A\to B\) is surjective.
Proof : Assume \(b\in B\).
\(\vdots\)
(we find an \(a\in A\) or show that an appropriate \(a\) must exist in \(A\))
\(\vdots\)
Thus \(f(a)=b\).
\(\Box\)
Note: Another name for surjective is onto.
We show that the function \(f:A\to B\) is bijective.
Proof : First we show that \(f\) is injective.
\(\vdots\)
Now we show that \(f\) is surjective.
\(\vdots\)
\(\Box\)
We show that \(P(n)\) is true for all \(n\in\mathbb{N}\).
Proof (induction) :
We use induction on \(n\).
Base step:
If \(n=1\) then
\(\vdots\)
Thus \(P(1)\) is true.
Inductive step:
Assume \(P(k)\) is true for some \(k\in\mathbb{N}\). (We are assuming \(P(n)\) is true for \(n=k\). This is called the inductive hypothesis.)
\(\vdots\)
Hence \(\cdots\) by the inductive hypothesis.
\(\cdots\)
Thus \(P(k+1)\) is true.
\(\Box\)
Note: If we want to show that \(P(n)\) is true for all \(n\ge n_{0}\), then the base step requires us to show that \(P(n_{0})\) is true.
Note: Sometimes it is better to assume that \(P(k-1)\) is true and show that \(P(k)\) is true.
Note: Sometimes the base step is not required because \(P(1)\) is vacuously true and this is shown by the inductive step.
We show that \(P(n)\) is true for all \(n\in\mathbb{N}\).
Proof (strong induction) :
We use induction on \(n\).
Base step:
If \(n=1\) then
\(\vdots\)
Thus \(P(1)\) is true.
Inductive step:
Assume that \(P(k)\) is true for all \(j\in\mathbb{N}\) with \(1\le j\le k\).
\(\vdots\)
Hence \(\cdots\) by the inductive hypothesis.
\(\cdots\)
Thus \(P(k+1)\) is true.
\(\Box\)
Note: Sometimes the inductive step uses \(P(2)\) specifically. In this case the base step needs to verify \(P(2)\).
We show that \(P(n)\le Q(n)\) for all \(n\in\mathbb{N}\).
Proof : We use induction on \(n\).
Base step:
If \(n=1\) then \(\cdots\)
Hence
\[ \begin{aligned}P(1) & =\cdots\\ & \,\,\,\vdots\\ & \le\\ & \,\,\,\vdots\\ & =Q(1). \end{aligned} \]
Inductive step:
Assume that \(P(k)\) is true for some \(k\in\mathbb{N}\).
\(\vdots\)
Hence
\[ \begin{aligned}P(k+1) & =\cdots\\ & \le\\ & \,\,\,\vdots\\ & \le\cdots+P(k)\\ & \le\cdots+Q(k)\text{ (by the inductive hypothesis)}\\ & \,\,\,\vdots\\ & =Q(k+1). \end{aligned} \]
\(\Box\)