This page details my expectations for proof-writing. See also the first chapter of the course textbook (Pugh), which has several helpful hints.

# Guidelines for Writing Proofs

Page 40 of the text gives an example of the proof technique that you are expected to use. My expectations for homework are as follows:

- When you begin a problem
**always**write out the problem statement (in your own words).

- When you begin writing the proof
- before the proof comes, write and underline "Proof:"
**always**define your variables, and state what set they are contained in (e.g. $x\in\mathbb{R}$ or $x\in A$ or something of the sort)- begin by writing out the goal of the proof. I use "WTS:", meaning
*"Want to show"*

- If you are breaking a problem into cases:
- write and underline "Case 1:", "Case 2:", etc.
- at the end of checking a particular case, draw a check mark $\checkmark$

- If you are using a
**proof by contradiction**- begin by writing "BWOC, suppose that…", where BWOC means
*"By way of contradiction"* - when a false statement is reached, write
*"This is a contradiction, therefore…"*or something similar.

- begin by writing "BWOC, suppose that…", where BWOC means
- At the end of the proof
- draw a small box $\blacksquare$, lightning bolt, "
**Q.E.D.**", "**HOOAH**", or some symbol of your choosing to indicate the end of the proof.

- draw a small box $\blacksquare$, lightning bolt, "

## Proofs by Contradiction

Proofs by contradiction can be very useful. Here is an example:

**Theorem:** There are an infinite number of prime numbers.

**Proof:**

**BWOC**, suppose there were only $n$ primes, call them $\{p_1,p_2,\ldots,p_n\}$. That would mean that every positive integer can be expressed as a product of elements in this set. We will establish a contradiction by finding an integer for which this is not true.

Let $q=p_1p_2\cdots p_n$, which divides every prime. However, $q+1=p_1p_2\cdots p_n+1$ does not divide *any* of the primes, since it has remainder 1 when divided by any of them. Therefore, $q+1$ cannot be expressed as a product of elements in the set $\{p_1,\ldots,p_n\}$, contradicting the assumption that there were only $n$ primes.

Therefore, no finite set of integers can contain all the prime numbers, and the set of prime numbers is infinite. $\blacksquare$

## Epsilon-Delta Proofs

These are extremely important in this course. Typically, the goal is to find $\delta$ such that if some condition involving $\delta$ is true, then some condition involving $\epsilon$ is true.

For example, to show a function $f$ is continuous at a point $x$, one must show that

(1)The proof that some function is continuous will typically go like this:

**Proof:**

Let $x\in\mathbb{R}$ and let $\epsilon>0$.

**WTS** there exists $\delta>0$ such that if $|x-u|<\delta$ then $|f(x)-f(u)|<\epsilon$.

Let $\delta=something$.

Then $|f(x)-f(u)|= \quad\cdots\qquad\cdots\qquad\cdots\qquad < \epsilon$.

$\blacksquare$

Note that if you are just showing $f(x)$ is continuous on a particular domain, or at a particular point, you would replace $x\in\mathbb{R}$ with something more appropriate.

There are two pieces which must be filled in. First, you have to figure out what $something$ to use for $\delta$. This may be tough to figure out, but usually can be discovered by some scratchpad pencil work. Second, you have to figure out how to put together a string of inequalities starting at $|f(x)-f(u)|$ and ending up at $\epsilon$. This also involves some scratchpad work, and frequently a trick or two.

## Counterexamples

To show that a statement is false, it suffices to find a counterexample. This is a sort of "unproof", meaning a way to show that a statement is not absolutely true.

This page contains notation that has been defined in the course. Feel free to add new entries.

## How to edit this page

To edit this page, click the button that says "edit" at the bottom. Follow the examples shown to write the entry.

**Example**- Use colons to define the term. Include spaces between the colons and the surrounding words. Use double stars around the title of the term to make it
**bold**. Use [[$ and $]] to write mathematical terms such as $\langle A,B\rangle$.

This example is produced by typing

: **Example** : Use colons to define the term. Include spaces between the colons and the surrounding words. Use [[$ and $]] to write mathematical terms such as [[$\langle A,B\rangle$]].

See how to edit pages for more help.

# Notation and Abbreviations

## Proof notation

The following notation is commonly used in proofs:

- $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ for the sets of natural numbers, integers, rationals, and reals, respectively. $\mathbb{C}$ is used for complex numbers;
- $\in$, as in $x\in A$ to indicate that an element is contained in a set [you should not use a curly epsilon $\varepsilon$];
- $\Rightarrow$ meaning
*implies*, and $\Leftarrow$ meaning*only if*; - $\Leftrightarrow$ meaning
*if and only if*or*is equivalent to*; - $\{n\in\mathbb{Z}: n \text{ is even}\}$ or $\{n\in\mathbb{Z}| n \text{ is even}\}$to indicate a set constructed of all elements with a given property. Here the colon $:$ is read as "such that";
- $f:A\to B$ to indicate a particular function's domain and range, read as "$f$ takes $A$ to $B$";

The following abbreviations are also commonly used:

**BWOC**:*by way of contradiction*;**WTS**:*want to show*;**QED**:*quad erat demonstratum*or*that which was to be shown*;**IFF**:*if and only if*;**WLOG**:*without loss of generality*.

The following notations are less commonly used; I do not advise you to use them very often in proofs:

- $\forall$ meaning "for each" or "for all";
- $\exists$ meaning "there exists", and $\nexists$ meaning "there does not exist";
- $\therefore$ meaning "therefore";
- $\ni$ or $|$ or $:$ meaning "such that" ($|$ and $:$ are usually used only in set notation);

## More Notation

These notations are specific to particular mathematical structures (e.g. logic, equivalence relations)

- Equivalence relations
- $\sim$ means equivalent;
- Logic
- $\wedge$ means "and", $\vee$ means "or", and $\lnot$ means "not";
- Set Theory
- $\emptyset$ represents the empty set, $A\cap B$ represents the intersection of sets, $A\cup B$ represents the union of sets; $A^c$ represents the complement of a set; $A+A'$ represents the set of all elements which can be written as the sum of an element in $A$ and an element in $A'$; $A*A'$, $\frac{1}{A}$, etc. are defined similarly.
- Cuts
- $A|B$ indicates a
*cut*. - Inner products
- $\langle \vec x,\vec y\rangle$ and $\vec x \cdot \vec y$ both indicate the
*dot product*or*inner product*of two vectors - Euclidean space
- $(a,b)$ indicates the
*open interval*$\{x:a<x<b\}$ of the real numbers and $[a,b]$ represents the*closed interval*$\{x:a\leq x\leq b\}$; $\mathbb{R}^n$ represents the set of*n-vectors*of the form $(x_1,\ldots,x_n)$; the*Cartesian product*$A\times B$ of sets $A\subset\mathbb{R}$ and $B\subset\mathbb{R}$ is the set of vectors $\{(a,b):a\in A,b\in B\}$.