How To Write Proofs

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:

  1. When you begin a problem
    • always write out the problem statement (in your own words).
  2. 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"
  3. 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$
  4. 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.
  5. 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.

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)
\begin{align} \text{there exists a } \delta>0 \text{ such that for all $u$ satisfying } |x-u|<\delta, |f(x)-f(u)|<\epsilon. \end{align}

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\}$.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License