$\newcommand{\Gr}{\mathrm{Gr}}\newcommand{\DR}{\mathrm{DR}}\newcommand{\bA}{\mathbb{A}} \newcommand{\bB}{\mathbb{B}}\newcommand{\bC}{\mathbb{C}}\newcommand{\bD}{\mathbb{D}}\newcommand{\bE}{\mathbb{E}}\newcommand{\bF}{\mathbb{F}}\newcommand{\bG}{\mathbb{G}}\newcommand{\bH}{\mathbb{H}}\newcommand{\bI}{\mathbb{I}}\newcommand{\bJ}{\mathbb{J}}\newcommand{\bK}{\mathbb{K}}\newcommand{\bL}{\mathbb{L}}\newcommand{\bM}{\mathbb{M}}\newcommand{\bN}{\mathbb{N}}\newcommand{\bO}{\mathbb{O}}\newcommand{\bP}{\mathbb{P}}\newcommand{\bQ}{\mathbb{Q}}\newcommand{\bR}{\mathbb{R}}\newcommand{\bS}{\mathbb{S}}\newcommand{\bT}{\mathbb{T}}\newcommand{\bU}{\mathbb{U}}\newcommand{\bV}{\mathbb{V}}\newcommand{\bW}{\mathbb{W}}\newcommand{\bX}{\mathbb{X}}\newcommand{\bY}{\mathbb{Y}}\newcommand{\bZ}{\mathbb{Z}}\newcommand{\cA}{\mathcal{A}}\newcommand{\cB}{\mathcal{B}}\newcommand{\cC}{\mathcal{C}}\newcommand{\cD}{\mathcal{D}}\newcommand{\cE}{\mathcal{E}}\newcommand{\cF}{\mathcal{F}}\newcommand{\cG}{\mathcal{G}}\newcommand{\cH}{\mathcal{H}}\newcommand{\cJ}{\mathcal{J}}\newcommand{\cI}{\mathcal{I}}\newcommand{\cK}{\mathcal{K}}\newcommand{\cL}{\mathcal{L}}\newcommand{\cN}{\mathcal{N}}\newcommand{\cM}{\mathcal{M}}\newcommand{\cO}{\mathcal{O}}\newcommand{\cV}{\mathcal{V}}\newcommand{\cX}{\mathcal{X}}\newcommand{\cY}{\mathcal{Y}}\newcommand{\cZ}{\mathcal{Z}}\newcommand{\uC}{\underline{\mathbb{C}}}\newcommand{\RH}{\mathrm{RH}}\newcommand{\todo}[1]{\fbox{\(\color{Mahogany} \textbf{ Todo }\): #1}}\newcommand{\cbox}[1]{\fbox{\(\color{Mahogany} \textbf{ Comment: }\) #1}}\newcommand{\rup}[1]{\lceil #1 \rceil}\newcommand{\rdown}[1]{\lfloor #1 \rfloor}\newcommand{\Perv}{\mathrm{Perv}}\newcommand{\Hom}{\mathrm{Hom}}\newcommand{\cHom}{\mathop{\mathcal{H}\! \mathit{om}}}\newcommand{\RcHom}{\mathop{R\mathcal{H}\! \mathit{om}}}\newcommand{\RHom}{\mathrm{RHom}}\newcommand{\IC}{\mathrm{IC}}\newcommand{\cExt}{{\mathop{\mathcal{E}\! \mathit{xt}}}}\newcommand{\op}{\mathrm{op}}\newcommand{\Supp}{\mathrm{Supp}}\newcommand{\Exc}{\mathrm{Exc}}\renewcommand{\div}{\mathrm{div}}\newcommand{\fram}{\mathfrak{m}}\newcommand{\modd}{\ {\rm mod}\ }\newcommand{\pinkbox}{{\color{pink}\colorbox{pink}{a}}}\newcommand{\F}{\mathbf{F}}$ **AI-generated overview of Class 0: Proofs:** ![[proofs_presentation.mp4]] **Example** Prove that a sum of two odd integers is an even integer. **Proof.** > Let $a$ and $b$ be odd integers. In particular, $a = 2k+1$ and $b=2l+1$ for some $k, l \in \bZ$. Thus $a+b = 2k+1 + 2l+1 = 2(k+l+1)$ is even. This concludes the proof. A proof is a *correct* and *complete* (without gaps) explanation. There is nothing magical about writing proofs, and there are no magic words that you need to use. Writing proofs is similar to writing letters/essays in English classes: you should **begin each sentence with a capital letter** and **finish with a full stop**; the sentences should be logically connected, for example by the use of *and*, *so*, *thus*, *therefore*, *because*, *since*, etc. For the sake of completeness, mathematical formulas should be parts of full sentences and not be put by themselves. Indeed, if you just write a mathematical formula by itself, then it is not clear whether it is a definition, an assumption, a statement, or a consequence. E.g. $x=1$ means something very different in the following sentences: * We set $x=1$. * Since $2x=2$, it holds that $x=1$. * Since $x=1$, we know that $2x=2$. > [!Remark] Important rules > **Useful hint**: to get into a good mindset, never start a sentence with a mathematical formula. > > In order to write your proofs using complete sentences, you should avoid the use of unnecessary symbols: > * Some of you may have used: ∴ (therefore), and ∵ (because). These symbols are not used in formal research mathematics, and so you should not use them in Mat 217. Instead you should just replace them with their meaning in words: *therefore* and *because*. > * The symbols ∀(for all), ∃ (there exists), ⇒ (implies), ⇐ (is implied by) ⇔ (if and only if, or iff.) are used by mathematicians in certain situations (for example, $\epsilon$ and $\delta$ proofs in analysis), but are often overused by students. When writing a proof, it is usually better to replace these symbols by their meaning in words. > > Last, you should remember to only use variables that you have defined! For example: > * Every even number can be written as $2k$, > > is not a complete statement, because it is not clear what $k$ is. Instead, you could write: > * Every even number can be written as $2$k for some integer $k$, or > * Every even number can be written as $2k$, where $k \in \bZ$. # Set notation A set $S$ is a collection of elements. It can be specified by $ S=\{x \mid x \text { satisfies some given property}\}. $ **Example.** $\mathbb{N}=\{n \mid n$ is an integer greater than or equal to 0$\}$ Notation: 1. $x \in S$ means "$x$ is an element of $Squot; 2. $S \subset T$ means "$S$ is a subset of $Tquot;, i.e. every element of $S$ is also an element of $T$. 3. $|S|$ denotes the number of elements of $S$. 4. $S \cup T$ and $S \cap T$ denote the union and intersection of $S$ and $T$, respectively. 5. $S \,\backslash\, T$ denotes the difference of $S$ and $T$. # Methods of proofs ### Direct proof **Example.** If $n$ is an odd integer, then $n^{2}$ is odd. **Proof.** > If $n$ is odd, then $n=2 k+1$ for some integer $k$. Computing, we see that $n^{2}=(2 k+1)^{2}=2\left(2 k^{2}+2 k\right)+1$ is also odd. &nbsp; ### Proof by contradiction Given a statement $P$ we assume that $P$ is false and derive a contradiction. This of course implies that $P$ must have been true in the first place. **Example**. Show that the $\sqrt{2}$ is not rational. **Proof** > Assume by contradiction that $\sqrt{2}=\frac{m}{n}$ for some relatively prime integers $m, n$ (that is, $m, n$ have no common divisors). Rewriting, this gives $m^{2}=2 n^{2}$. It follows that $m$ must be even as squares of odd numbers are odd. Therefore, there is $k \in \mathbb{Z}$ such that $m=2 k$. Computing, we get $2 n^{2}=m^{2}=4 k^{2}$. It follows that $n^{2}$ is even, and so $n$ must also be even. However, $m$ and $n$ were assumed to be relatively prime, and so they cannot be both divisible by $2$. This is a contradiction, and hence $\sqrt{2}$ is irrational. ### Proof by contraposition A proof by contraposition is similar to a proof by contradiction. **Example.** If $2^{n}-1$ is prime, then so is $n$. **Proof.** > Suppose that $n$ is not prime. Then $n=a b$ for integers $a, b \geq 2$. Set $k=2^a$. Now we have that: > $ > 2^{n}-1=2^{a b}-1=k^{b}-1=(k-1)\left(k^{b-1}+k^{b-2}+\cdots+k+1\right) . > $ > Since $k \geq 4$, this is a factorization of $2^{n}-1$ as a product of integers greater than $2$. Therefore $2^n-1$ is not prime, concluding the proof. **Comment.** Given two statements $P$ and $Q$, observe that: * ($P \implies Q$) &nbsp; is equivalent to its contrapositive &nbsp; ($Q$ is false $\implies$ $P$ is false). In our case: * $P$ = ($2^{n}-1$ is prime), and * $Q$ = ($n$ is prime). Our goal was to show that $P \implies Q$. This is hard to do directly, so we argued by contraposition proving that * ($n$ is not prime) $\implies$ ($2^{n}-1$ is not prime). > [!Remark]- Fun fact (click here) > Primes of the form $2^{n}-1$ are called Mersenne Primes. The current largest known prime $2^{82,589,933}-1$ is a Mersenne Prime and was discovered in December of $2018$. There are currently only $51$ known Mersenne Primes. See https://www.mersenne.org/primes/press/M82589933.html ### Proof by counterexample Let us consider the converse of the problem discussed above. **Typical exam problem.** Decide if the following statement is true or false, and justify. * If $n$ is prime, then $2^{n}-1$ is also prime. **Answer.** > This statement is false. If $n=11$, then $2^{11}-1=2047=23 \cdot 89$. Thus, $n=11$ is a counterexample. **Super important:** To prove that a statement is false, you **need to provide an explicit counterexample**! A general explanation that points out why you think the statement should be false is *insufficient* and, in fact, not *needed*. However, if the considered statement is true, then you need to provide a **full proof**. &nbsp; ### Existence and uniqueness proofs The following result is an example of a complex proof. We first split the proof into two parts: "existence" and "uniqueness". **Example** Let $a \in \bZ$ and let $n$ be a positive integer. Prove that there exists a unique integer $r$ such that $n \mid a-r$ and $0 \leq r < n$. **Note** the number $r$ is called the *remainder of the division of $a$ modulo $n$*, denoted as $a \bmod n$, e.g. $13 \bmod 5 = 3$. **Proof.** > We split the proof into two parts. > > **Existence of $r$.** Consider the set > $ > S := \{ x \in \bZ_{\geq 0} \mid \text{ $n$ divides $a-x$}\}. > $ > This set is non-empty as $a \in S$. Since this set is bounded below by $0$ we can pick the smallest integer $r$ contained in this set. In particular, $r \geq 0$ and $n \mid a-r$. > > We claim that $0 \leq r < n$. Suppose by contradication that $r \geq n$. Then > * $r-n \geq 0$, and > * $n \mid a - (r-n)$. > > Hence $r-n \in S$. This contradicts the choice of $r$ as the smallest element of $S$ and shows the claim, concluding the existence part of the proof. > > **Uniqueness of $r$.** Suppose there exist integers $r$ and $r'$ such that > * $0 \leq r < n$ and $n \mid a-r$; > * $0 \leq r' < n$ and $n \mid a - r'$. > > Then > * $-n < r-r' < n$, and > * $n \mid (a-r) - (a-r') = r'-r$. > > Since $r-r'$ is divisible by $n$ and contained in the range $(-n,n)$, this is only possible when $r-r'=0$. This concludes the uniqueness part of the proof. ### Proofs with "if and only if" Often we will show that two statements $P$ and $Q$ are equivalent. Formally, we write it as: $P$ holds if and only if $Q$ holds, or $P \iff Q$. To show this, we will usually split the proof into two parts: $P \implies Q$ and $Q \implies P$. **Example** Let $x, y \in \bR$. Prove that $\frac{x+y}{2} = \frac{x-y}{2}$ if and only if $y=0$. **Proof** > ($\implies$) Suppose that $\frac{x+y}{2} = \frac{x-y}{2}$. Then > $\qquad \qquad x+y = x-y, \text{ and so }$ > $2y = 0.$ > > Therefore $y=0$. > > ($\impliedby$) Suppose that $y=0$. Then > $\frac{x+y}{2} = \frac{x + 0}{2} = \frac{x - 0}{2} = \frac{x-y}{2}.$ **Comment.** Every time you write an equality symbol you should be able to explain (internally to yourself or on paper) why this equality is true. A very common mistake in proof writing is to write terms of equalities at random without taking into account the logical order. For example, in the situation above, we could have written: "Suppose $y=0$. Then $\frac{x+y}{2} = \frac{x-y}{2} = \frac{x+0}{2} = \frac{x-0}{2}.quot; In theory, this is equivalent to what we wrote above, but is an example of *bad proof-writing* as you cannot really read this formula meaningfully from left to right. **Note.** In the above example, one can also prove both implications at the same time: $\begin{align*} \frac{x+y}{2} = \frac{x-y}{2} &\iff x+y = x-y \\[0.5em] &\iff 2y = 0 \\[0.5em] &\iff y = 0. \end{align*}$ This is shorter and cleaner. However, you should be very careful when doing such proofs, as it is **easy to make a mistake**, for example by accidentally dividing by $0$. ### Proof of equality To show that $a=b$, sometimes it is easier to show $a \leq b$ and $b \leq a$. Similarly, to show two sets $S$ and $T$ are equal, sometimes it is easier to show that $S \subset T$ and $T \subset S$. We will see proofs using this idea when we talk about the dimension of a vector space. ### Proof by case by case analysis **Example.** Show that for all integers $x$ it holds that $x(x+1)$ is even. **Proof** > Since $x$ is either even or odd, we can prove this by case by case analysis. > > If $x$ is even, then we can write $x=2k$ for some $k \in \bZ$. In this case $x(x+1)=2 k(2 k+1)$ is even. > > If $x$ is odd, then we can write $x =2k+1$ for some $k \in \bZ$. In this case, $x(x+1)=(2k+1)(2k+2) = 2(2k+1)(k+1)$ is also even. ### Proof by induction **Example**. Prove that $4^{n}+6 n-1$ is divisible by $9$ for all $n \in \mathbb{N}$. **Proof.** > Note that the statement is true for $n=0$ as $4^0 + 6\cdot 0 - 1 = 0$ is divisible by $9$. By induction on $n\geq 0$ we may assume that $\begin{equation} 4^{n-1} + 6(n-1) - 1 \tag{inductive assumption}\end{equation}$ is divisible by $9$. Then $4^{n-1} = -6n+7 +9k$ for some $k\in \bZ$, and so > $\begin{equation*} 4^{n} + 6n - 1 = 4(-6n+7+9k) + 6n -1 = -18n + 36k - 27 = 9(4k-2n-3) \end{equation*}$ > is divisible by $9$. By induction, this shows that $4^{n}+6 n-1$ is divisible by $9$ for all $n \in \mathbb{N}$. **Explanation** The point of induction is as follows. Suppose that we are given statements $P_n$ depending on the parameter $n \in \bN$, and suppose we show that: 1) $P_0$ is true, and 2) if $P_{n-1}$ is true, then $P_n$ is true. Then we get a sequence of implications $P_0 \implies P_1 \implies P_2 \implies \cdotsamp;nbsp;, and so $P_n$ is valid for every $n \in \bN.$ ### Common pitfalls when doing proofs * Checking one example or case is **not a proof** (unless you are providing a counterexample!) * Intuition is not always correct. Proofs need to be built from logically valid steps. * Circular reasoning - do not implicitly assume a result that follows from what you are trying to prove. * Failing to use clear definitions and labels.