\( \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 starting with a capital letter and ending with a period.
Avoid starting sentences with notation.
Notation like \(\Rightarrow,\exists,\forall,\neg\) is fine inside set-builder notation, but avoid the overuse of these symbols and the symbols \(\because\) and \(\therefore\) in the text of the proof.
Every variable needs a quantifier. In some situations a missing quantifier defaults to the universal quantifier \(\forall\).
‘‘Since \(\cdots\), then \(\cdots\).’’ is incorrect grammar.
Mathematics is usually written in first-person plural style. Avoid passive sentences.
First explain what we are about to do, then do it.
Separate logical parts of the proof into paragraphs.
Balance clarity and conciseness.
Do not include examples in proofs. Examples are welcome after the proof.
We show that \(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\)
Note: It is tempting to start the proof with the sentence ‘‘Let \(x\in A\).’’. This is not correct unless we know that the set \(A\) is not empty. An alternative is to consider the \(A=\emptyset\) case separately. This extra step can be avoided with the use of the word ‘‘assume’’ since in this case the statement is vacuously true.
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\)
Proof : Assume \(x\in A\). Then
\[ \begin{aligned}P(x) & \iff\cdots\\ & \quad\vdots\\ & \iff Q(x). \end{aligned} \]
\(\Box\)
Note: The chain of equivalent statements seems quicker but it is often very difficult to do correctly.
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 feels attractive but it is often very 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(n_{0})\) 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 also 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\)