%template file for latex papers
\documentclass[12pt]{article}
\usepackage[]{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\pagestyle{empty}
\oddsidemargin -0.04cm
\evensidemargin -0.04cm
\textwidth 17cm
\topmargin -.5in
\textheight 9.0in
\parskip 4.2pt
\setlength{\footskip}{45pt}
\usepackage{graphics}
\usepackage{color}
\usepackage{url}
\begin{document}
\pagestyle{empty}
\begin{center}{
\large{ \bf{ON PROOFS}}
}\end{center}
\textit{Proofs} are deductive arguments for mathematical statements.
We can usually trace them back to a set of axioms, and they use formal logic.
\textit{Axioms} (or postulates) are starting points -- they are statements that we take to be true.
\textit{Example.} In Euclidean geometry, we use Euclid’s postulates (e.g.,
\textit{A straight line segment can be drawn joining any two points} or
\textit{Any straight line segment can be extended indefinitely in a straight line}).
\begin{center}{
\textbf{Some Types of Proofs}
}\end{center}
\begin{itemize}
\item \textbf{Direct:} Direct proofs take the hypothesis of the statement to directly establish the
conclusion.
\textit{Example.} The sum of two even integers is even.\\
\textit{Proof.} Let $a$ and $b$ be two even integers. By definition of even, we can write $a = 2m$
and $b = 2n$ for the integers $m$ and $n$. Consider $a + b = 2m + 2n = 2(m + n)$, which is an even integer. \hfill $\square$
\item \textbf{Contrapositive:} If we want to show: ``If $p$, then $q$'', we instead show: ``If not $q$, then not $p$.''
\textit{Example.} If $x^2$ is an even integer, then $x$ is even. \\
\textit{Proof.} We show the contrapositive: if $x$ is not even, then $x^2$ is not even.
Suppose $x$ is not an even integer. Then it must be odd. We can write it as $2m + 1$ for some integer $m$.
Consider $x^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1$, which is an odd number. Thus, $x^2$ is not even. \hfill $\square$
\item \textbf{Contradiction (reductio ad absurdum):} If we assume a statement is true, then a
logical contradiction occurs and so the original statement must actually be false.
\textit{Example.} For a real number $x$, if $x^2 = 0$, then $x = 0$. \\
\textit{Proof.} For a real number $x$, suppose that $x^2 = 0$ and that $x \neq 0$.
Consider the equation $x^2 = 0$ and multiply both sides by $1/x$. \\
Then we have $x^2(1/x) = 0(1/x)$ or that $x = 0$, which is a contradiction with our original assumption.
Thus, $x = 0$ must actually be true. \hfill $\square$
\item \textbf{Construction:} These proofs are used to show the existence of a mathematical object
by giving a method for creating it.
\textit{Example.} There exists an even integer that can be written in two ways as the sum
of two prime numbers. \\
\textit{Proof.} We only need to provide an example that this object exists.
Take the number $10$. $10 = 5 + 5$ and $10 = 3 + 7$.
Thus, there exists an even integer that can be written in two ways as the sum of two primes. \hfill $\square$
\item \textbf{Exhaustion (brute force):} We split our statement into a set of finite cases and check
each case.
\textit{Example.} The Four Color Theorem (motivated by map-coloring) was proven by
exhaustion. See: \url{http://en.wikipedia.org/wiki/Four_color_theorem}.
\item \textbf{Induction:} A proof by induction is just like an ordinary proof in which every step must be justified.
However it employs a neat trick which allows you to prove a statement about an arbitrary number $n$ by first proving it is true when $n=1$
and then assuming it is true for $n$ and showing it is true for $n+1$.
\textit{Example.} $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$. \\
\textit{Proof.} Base case: for $n = 1$, we have $1$ on the left hand side and $2^1 - 1 = 1$ on the right hand side. \\
Assume the statement is true for our inductive hypothesis.
We want to show that the statement holds for $n + 1$. \\
Take $1 + 2 + 4 + \cdots + 2^{ n-1} = 2^n - 1$ and add $2^n$ to both sides.
We get
$$1 + 2 + 4 + \cdots + 2^{ n-1} + 2^n = 2^n - 1 + 2^n$$
$$1 + 2 + 4 + \cdots + 2^n = 2(2^n) - 1 = 2^{n+1} - 1.$$
So the statement is true for n + 1. \hfill $\square$
\end{itemize}
\begin{center}{
\textbf{Ending a Proof}
}\end{center}
It is typical to end a proof with one of the following:
\begin{itemize}
\item QED (Quod Erat Demonstrandum) “that which was to be shown”
\item $\square$ the halmos (tombstone) symbol
\end{itemize}
\begin{center}{
\textbf{Other Comments}
}\end{center}
\begin{itemize}
\item Quantifiers are important. \\
For instance, the phrase "for every $x$'' (sometimes "for all $x$'') is called a universal quantifier and is denoted by $\forall x$.
The phrase "there exists an $x$ such that'' is called an existential quantifier and is denoted by $\exists x$.
A statement that contains variables is not simply true or false unless each of these variables is bound by a quantifier.
If a variable is not bound, the truth of the formula is contingent on the value assigned to the variable from the universe of discourse.
\item A theorem cannot be proved by example; however, to show that a statement is not true, a counterexample is used.
\item Never assume any hypothesis that is not explicitly stated in the theorem.
\item Sometimes it is easier to prove the contrapositive of a statement (see above).
\item If you need to show that an object exists and is unique, first show that there actually is such an object.
To show its uniqueness, assume that there are two such objects and show that they are the same.
\end{itemize}
\end{document}