\documentstyle[12pt,twoside,amsfonts]{article}
\input{macros-course}

\parskip1.5ex
\parindent0pt

\begin{document}

\handout{notes1}{Notes 1}{September 7, 1995}


\section{Introduction}

\subsection{Administrivia}

Introductions.

Books in the COOP are under 18.062

Recitation is a must, since new material will be covered.

HW policies:
\begin{itemize}
\item Homework due Tuesday at {\em start} of class.  
\item Late work penalized till Thursday.  Then a zero.
\item Collaboration is encouraged, but you must 
\begin{itemize}
\item understand and write up the solution yourself in your own words
\item cite {\em all} your collaborators.  
\end{itemize}
\end{itemize}

HW1 due next Tuesday.  More and easier questions than usual.

\subsection{Class Content}

\begin{itemize}
\item proofs
\item abstraction
\item tools that ease proofs and abstraction
\end{itemize}

We will spend the whole semester introducing various abstractions and
tools.  To begin, we concentrate on proofs, studying them in relation
to abstractions we already know.

\subsection{Propositions}

Knowledge consists of {\em propositions}, such as
\begin{itemize}
\item 2+3=5
\item if $a=b$ and $b=c$ then $a=c$
\item The sum of the interior angles of a triangle is $180^\circ$
\item Every even integer greater than 2 is the sum of two prime
numbers (Goldbach's conjecture).
\item For all $n \ge 1$, $1+2+\cdots+n = n(n+1)/2$
\item For all $n \ge 0$, $n^2+n+41$ is a prime number.
\item With perfect play, chess is a win for white.
\item The Pentium chip divides properly.
\item Every map can be colored with four colors, so that no two
adjacent regions have the same color (Four Color Theorem).
\item With a fair coin, the probability of getting 50 heads in 100
tosses is 1/2.
\end{itemize}

Each of these propositions is either {\em true} or {\em false.} We (and
Intel) would like to know which.

Notes:
\begin{itemize}
\item Not all sentences are propositions:
     \begin{itemize}
     \item $+2**=3$
     \item What time is it?
     \item this proposition is false
     \end{itemize}
\item Propositions involve previously {\em defined} terms:
     \begin{itemize}
     \item prime, map, triangle, chess, fair coin, probability
     \item $+$, $=$, $1$, $\ge$
     \end{itemize}
\end{itemize}

Many ways to decide what's true:
\begin{itemize}
\item evidence (eg, general relativity, big bang),
\item reputable authority (eg, Professor),
\item inner conviction (eg, religion),
\end{itemize}
But these methods can go wrong:
\begin{itemize}
\item evidence: $n^2+n+41$.  Program works fine on all test cases, but$\ldots$,
\item authority: Intel says Pentium is fine
\item conviction: there aren't any bugs in {\em my} programs$\ldots$
\end{itemize}
so mathematics focuses on a particularly convincing kind of
argument: a {\em proof.}
\begin{itemize}
\item begin with true propositions
\item combine using specific inference rules
\item derive more true propositions
\end{itemize}
Goal: know and admit {\em all} unproven assumptions.

\begin{theorem} $\frac{d}{dx} \ln (3x+1) = \frac{3}{3x+1}$
\end{theorem}
\begin{proof}
\begin{eqnarray*}
\frac{d}{dx} 1 &= &0\\
\frac{d}{dx} 3x &= &3\\
\frac{d}{dx} (u+v) &= &\frac{d}{dx} u + \frac{d}{dx} v\\
\end{eqnarray*}
Combine, with $u=3x$, $v=1$:
\begin{eqnarray*}
\frac{d}{dx} (3x+1) &= &3\\
\frac{d}{dx} \ln u &= &\frac{1}{u}\frac{du}{dx}\\
\end{eqnarray*}
Combine, with $u=3x+1$.
 \end{proof}

This was a {\em direct proof:} start with knowns, plug together till
you get desired result.

\subsection{Why Proofs?}

Proofs convince others.

A proof assures you haven't made mistakes.

A proof can often be reused, like a well written program.

A proof pins down {\em why} something is true, so you can know whether
it will stay true when things change.

A failure to prove something often reveals the reason it is false.

Program verification: proof that a program does the right thing.
\begin{itemize}
\item Pentium
\item Airbus A300
\item Therac 25
\end{itemize}

\section{Nuts and Bolts}

\subsection{Logical Proof Systems}

A logical proof system consists of:
\begin{itemize}
\item A {\bf language} for stating propositions
\item {\bf Axioms:} statments accepted as true
\item {\bf Rules of inference:} acceptable ways of combining propositions
\item {\bf Theorems:} propositions that can be derived by applying the
inference rules to the axioms.
\end{itemize}

Note: we must always have some axioms: there are no ``self evident''
propositions.  

A system is 
\begin{itemize}
\item {\bf consistent} if a statement and its complement cannot
both be derived.
\item {\bf complete} if can prove or disprove every proposition
\end{itemize}

Russell and Whitehead, {\em Principia Mathematica}, tried to completely
axiomatize mathematics but failed.

G\"odel's Theorems:
\begin{itemize}
\item no axiomatization of arithmetic is complete and consistent.
\item ``arithmetic is consistent'' is a proposition that cannot be
proved in arithmetic.
\item Gensen: ``arithmetic is consistent'' can be proved by adding
some reasonable-sounding axioms, but these axioms can't be proved
consistent.
\end{itemize}

There are true facts in math that cannot be proven!

\subsection{Our Language}

\subsubsection{Boolean Operators} 

Boolean symbols are useful for brevity and precision, just like
arithmetic symbols.  If
\begin{itemize}
\item  $p$ denotes ``I like chocolate''
\item  $q$ denotes ``I like ice cream''
\end{itemize}
then
\begin{itemize}
\item $p \wedge q$ means ``$p$ and $q$'' (I like chocolate
and I like ice cream).  True iff $p$ and $q$ are both true.
\item $p \vee q$ means ``$p$ or $q$.''  True iff {\em one or both} of
$p$ and $q$ is true.  {\em Not} an exclusive or. (How could I
formulate exclusive or?)
\item $p \implies q$ means ``$p$ implies $q$'' or ``if $p$ then $q$''
(If I like chocolate, then I like ice cream).  True iff $p$ being true
makes $q$ true.
\item {\bf note:} $p\implies q$ is certainly true when $p$ is false!
\end{itemize}

\subsubsection{Sets}

A {\em set} is a collection of objects:
\begin{itemize}
\item $x \in S$ means ``$x$ is in the set $S$''
\item $\emptyset$ is the empty set  (contains no elements).
\item $A \cap B$ means ``the intersection of $A$ and $B$'' (the set of elements
in both sets).
\item $A \cup B$ means ``the union of $A$ and $B$'' (elements in
either set).
\end{itemize}

We won't be axiomatic about sets (``naive set theory'').

\subsubsection{Predicates}

Predicates are ``propositions'' that depend on variables.  $P(x,y,z)$
denotes a predicate on variables $x,y,z$.  For example, define:
\begin{itemize}
\item $R(x)$: $x$ is an odd number
\item $Q(x)$: $x > 2$
\item $P(x)$: $x$ is a prime number
\end{itemize}
These predicates are {\em not} propositions, because they can be true
or false depending on $x$.  They are like functions from variables to
truth values. 
\begin{itemize} 
\item $P(2)$ is true
\item $R(2)$ is false
\item $P(4) \vee R(3)$ is true
\item $Q(3) \wedge R(4)$ is false
\item $Q(1) \implies R(2)$ is true.
\end{itemize}

\subsection{Quantifiers}

Many propositions assert that something is true for all or some elements
of a given domain (e.g., all numbers).  Let's agree in advance on a
{\em universe of discourse.}

\begin{itemize}
\item ``$\forall$'' means ``for all.'' $\forall x P(x)$ is a statement
that is true if $P(x)$ is true for {\em every} $x$ in the universe of
discourse. 
\item ``$\exists$'' means ``there exists.'' $\exists x P(x)$ is true
if $P(x)$ is true for {\em at least one} $x$ in the universe of
discourse.
\item ``$\exists !$'' means ``there exists {\em exactly} one.''
\item ``$\forall x \in S$'' means ``for every $x$ in the set $S$.''
$(\forall x \in S) P(x)$ is equivalent to $(\forall x) (x \in S
\implies P(x)).$
\end{itemize}

Quantifies can turn predicates into propositions, e.g.
\[
\forall x, P(x) \wedge Q(x) \implies R(x)
\]
This expression is a (true) proposition, because the variable in the
predicates is {\em bound}.

$\forall x \exists y$ is {\em different} from $\exists y \forall
x$:
\begin{itemize}
\item $S(x,y):$ student $x$ falls asleep in class $y$.
\item $\forall y \exists x P(x,y):$ ``In every class, some student will fall asleep''
\item $\exists x \forall y P(x,y):$ ``There exists a student who will
fall asleep in every class.''
\item what is my universe of discourse above?
\end{itemize}

\subsection{Axioms}

Axioms are propositions that are {\em assumed} to be true (``axiom''
comes from a greek ``to think worthy,'' not ``to be true'').  It is
not wrong to make assumptions (in fact, it is unavoidable), but to be
rigorous you have to state your assumptions explicitly.

$a=b$ and $b=c$ implies $a=c$.

Euclidean geometry has an axiom: Given a line $l$ and a point $p$ not
on $l$, there is exactly one line through $p$ parallel to $l$.

Spherical geometry has an axiom contradicting Euclid's: Given a line
$l$ and a point $p$ not on $l$, there is {\em no} line through $p$
parallel to $l$.

So does hyperbolic geometry: Given a line $l$ and a point $p$ not on
$l$, there are {\em infinitely many} lines through $p$ parallel to
$l$.

None of these axioms is ``better'' than any other: in fact, all yield
equally consistent logical proof systems.

Modern mathematicians still argue about which axioms are ``right,''
e.g., the Axiom of Choice (whose affirmation and negation are equally
consistent).

Of course, different axioms lead to very different theorems.  But
anyone who agrees with your axioms and inference rules has to accept
your theorems.

\subsection{Inference Rules for Propositions}

When does one proposition follow from another?

Let $p$ and $q$ be propositions.  Then if $p$ is true, and $p\implies
q$ (read $p$ {\em implies} $q$) is true, we can conclude that $q$ is
true.  This is a rule called {\em modus ponens.}

\newcommand{\alaw}[1]{\parbox[t]{1in}{
\begin{tabular}{l}
#1
\end{tabular}}}

Modus Ponens: \alaw{$p$\\
$p\implies q$\\
\hline
$q$}

Syllogism: \alaw{
$p\implies q$\\
$q\implies r$\\
\hline
$p\implies r$}

Modus Tolens: 
\alaw{$p\implies q$\\
$\neg q$\\
\hline
$\neg p$}

Boolean Algebra is a useful aid in reasoning and inferring.  For
example, 
\[
[(p \vee q) \wedge \neg p] \implies q
\] so we can derive an
inference rule:

Disjunctive Syllogism: \alaw{$p \vee q$\\ $\neg p$ \\ \hline $q$}


\subsection{Inference Rules for Predicates}

Negation:
\begin{itemize}
\item $(\forall x) S(x)$ is equivalent to $\neg (\exists x) \neg S(x)$
    \begin{itemize}
    \item $(\forall x) S(x):$ For all primes $x \ge 2$, $x$ is odd.
    \item $\neg(\exists x) S(x):$ There is no prime $x \ge 2$ such
that $x$ is not odd.
    \end{itemize}
\item $(\exists x) S(x)$ is equivalent to $\neg (\forall x) \neg
S(x)$.
\end{itemize}

Universal generalization is a way to prove $\forall x P(x)$:
\begin{itemize}
\item ``Let $x \ge 2$.  Then $x$ is prime or composite.''
\item  Conclude: $\forall x \ge 2$, $x$ is prime or composite (explain
$\forall x\ge 2$). 
\end{itemize}

We often leave out universal quantifiers if they are implicit.

Like axioms, inference rules are an {\em agreement} to believe certain
inferences.  For example, the intuitionists (e.g. Brouwer) {\em reject}
the claim that $\neg\forall x \neg P(x)$ implies $\exists x P(x)$.
They claim that to prove something exists, you actually have to
construct it.

\subsection{Peano's Axioms and Addition}

Briefly, we will carefully follow a logical proof system (generally,
we won't be so careful).

Peano's Axioms define the natural numbers $\naturals$.  We add two
primitive symbols: $0$ and $'$ (successor).
\begin{enumerate}
\item $0 \in \naturals$
\item $\forall x \in \naturals,\ x' \in \naturals$
\item $\forall x,y \in \naturals,\ x'=y' \implies x = y$ (no two
numbers have same successor)
\item $\neg\exists x \in \naturals$ such that $0 = x'$  (equivalently, $\forall x
\in \naturals, x' \ne 0$)
\item (Induction) $\forall S \subseteq N$, if $0 \in S$ and $(x \in S
\implies x' \in S)$, then $S = \naturals$.
\end{enumerate}

Notation: $1 = 0'$, $2 = 1'$, etc.

We now {\em define} addition:
\begin{itemize}
\item $n+0 = n$ (implicit universal quantification)
\item $n+k' = (n+k)'$
\end{itemize}
This is a {\em recursive} definition: it lets us compute $n+k$ for any
$n, k$.  For example, 
\begin{eqnarray*}
3+2 &= &3+1'\\ &= &(3+1)'\\ &= &(3+0')'\\ &= &((3+0)')'\\ &=
&(3')'\\ &= &4'\\ &= &5.\\
\end{eqnarray*}

Addition is {\em commutative:} $m+n = n+m$.  How can we prove this?

\begin{lemma}
\label{lem:1}
$0+n=n$
\end{lemma}
\begin{proof}
Let $S = \{n\in \naturals \mid 0+n = n\}$ (``The set of all
$n\in\naturals$ such that $0+n=n$'').  We prove $S=\naturals$.
\begin{itemize} 
\item $0 \in S$ since $0+0 = 0$ by definition of $+$.
\item if $x\in S$, so that $0+x = x$, then 
\begin{eqnarray*}
0+x' &= &(0+x)'\quad\mbox{(definition of $+$)}\\
     &= &x', \quad\mbox{(since $x \in S$)}\\
\end{eqnarray*}
so $x'\in S$.  In other words, $\forall x, (x\in S) \implies (x' \in S)$.
\end{itemize}
Therefore, by the induction axiom, $S = \naturals$.
\end{proof}

\begin{lemma}
$m'+n = m+n'$
\end{lemma}
\begin{proof}
Fix $m$.  Let $S = \{n \mid m'+n = m+n'\}$. We prove $S = \naturals$. 
\begin{itemize}
\item $0 \in S$, since $m'+0 = m' = (m+0)' = m+0'$
\item if $n \in S$, so that $m'+n = m+n'$, then
\begin{eqnarray*}
m'+n' &= &(m'+n)'\quad \mbox{(definition of $+$)}\\
      &= &(m+n')'\quad \mbox{(true for $n$)}\\
      &= &(m+(n')'\quad \mbox{(definition of $+$)}
\end{eqnarray*}
\end{itemize}
Since $0\in S$, and $n \in S  \implies n' \in S$, the induction axiom
proves $S=\naturals$.  We proved $P(m)$, therefore by universal
generalization, we know that $(\forall m)P(m)$.
\end{proof}

\begin{lemma}
$m+n = n+m$
\end{lemma}
\begin{proof}
Let $S = \{n \mid ( \forall m)m+n = n+m\}$. We prove $S = \naturals$. 
\begin{itemize}
\item $0 \in S$, since $m+0 = m = 0+m$ by Lemma~\ref{lem:1}.
\item Suppose $n \in S$, so that $(\forall m) m+n=n+m$.  Then
\begin{eqnarray*}
m+n' &= &(m+n)' \quad \mbox{(definition)}\\
     &= &(n+m)' \quad \mbox{(true for $n$)}\\
     &= &n+m'   \quad \mbox{(definition)}\\
     &= &n'+m   \quad \mbox{(previous lemma)}
\end{eqnarray*}
\end{itemize}
Therefore, $S=\naturals$ by induction axiom.
\end{proof}

Have we been rigorous?  No: naive set theory.  Set theory axioms are
harder than you might think.

Real numbers can be defined by about 10 axioms.

\section{How To Prove Things}

\subsection{The Real World}

Rigorous logical proof systems are nice, but no one really
has the time or energy to be so careful.  We prove things in a less
formal way.   The objective is to convince everyone that a truly
rigorous proof could be built if someone took the time to do it.  
As a result, even great mathematicians can goof proofs.
\begin{itemize}
\item Andrew Wiles and Fermat's Last Theorem
\item Kempe's invalid ``proof'' of the Four Color Theorem stood for 10
years (1879--1890)
\item Gauss's 1799 Ph.D. thesis is usually referred to as being the
first rigorous proof of the Fundamental Theorem of Algebra (every
polynomial has a zero over the complex numbers).  But it contains
quotes like
\begin{quote}
  "If a branch of an algebraic curve enters a bounded region, it
   must necessarily leave it again. ... Nobody, to my knowledge,
   has ever doubted [this fact].  But if anybody desires it, then
   on another occasion I intend to give a demonstration which will
   leave no doubt."
\end{quote}
Fields Medalist Steve Smale writes about this, calling it an "immense
gap" in the proof that was not filled in until 1920, more than a hundred
years later.
\item In 1900 Poincare carelessly claimed a certain very simple topological 
characterization of the 3-dimensional sphere.  Later realizing it was 
not so obvious, he demoted the claim to the status of a "conjecture" 
in 1904.  The Poincare Conjecture is now one of the biggest open questions
in mathematics (two Fields Medals have been given out for partial progress
on it).
\item In the 1940's Paul Erdos conjectured a certain combinatorial fact about 
arithmetic progressions (every set of natural numbers of positive density 
contains arbitrarily long arithmetic progressions), and offered \$1000 for a
proof or disproof.  Endre Szemeredi proved the conjecture in 1972, but
the proof was so long and badly written that Erdos was not sure whether
to believe it.  Finally, Andras Hajnal stepped in and wrote a much clearer
version of the same proof, which was eventually published under Szemeredi's
name.  At some point during the write-up, Hajnal informed Erdos that
he was now confident enough of the proof that he was willing to buy it 
from Szemeredi for \$500.
\item  There's also the story of Newton waiting 20 years to publish
the Principia because he didn't see how to prove one could assume all
the mass of a sphere to be concentrated at its center when calculating
gravitational attraction.  The proof ultimately required the invention 
of calculus ...

\end{itemize}

\subsection{What we Expect}

Basic objective: like a scientific experiment, it has to be possible
for someone else to ``replicate'' (ie, understand) your proof.

In the real world, anything that can be cited can be used without
proof.  But in homework, where everything we ask you to prove is already
known, this defeats the purpose (namely, learning how to prove
something that isn't already known).  

We don't expect you to reprove arithmetic.  Anything from high school
math can be used without proof.  

Once something has been proved, you can use it again without proof,
citing the theorem.  Once it has been used so often as to become
commonplace, you can even stop citing the theorem.

No new axioms!

When in doubt about whether something can be stated without proof,
prove it!

Elements of a proof:
\begin{itemize}
\item correctness
\item clarity
\item brevity
\item elegance
\end{itemize}
``The book proof'' (Paul Erdos).

There are lots of ways to prove things, we now give some examples.

\subsection{Direct Proof}

Direct proofs are the most straightforward: we mix together previous
axioms and theorems until the desired claim is inferred.

We say $a$ {\em divides} $b$ if there exists an integer $t$ such that
$a=bt$.  We write $a \mid b$.
\begin{itemize}
\item $3 \mid 6$
\item $3\not |~7$
\end{itemize}

\begin{theorem}
If $a \mid b$ and $a \mid c$, then $a \mid b+c$.
\end{theorem}
\begin{proof}
By definition of divisibility, $(\exists t) b = at$ and $(\exists s) c
= as$.\\  Therefore, $b+c = at+as = a(t+s)$.\\  Therefore, by definition,
$a \mid b+c$.
\end{proof}

Note: distributivity was assumed without mention.

\subsection{Proof by Contradiction}

\alaw{$p \implies FALSE$ \\ \hline $\neg p$}

Proofs can go ``backwards'':
\begin{itemize}
\item Begin by assuming the desired theorem is false.
\item Using inference rules, conclude something known false.
\item Conclude that the assumption is wrong.
\end{itemize}

\begin{theorem} $\sqrt{2}$ is an irrational number.
\end{theorem}
\begin{proof} (Indirect).  Assume $\sqrt{2}$ is rational.  

Conclude $\sqrt{2}$ can be written as a fraction $a/b$ in lowest
terms.\\ Then $2b^2 = a^2$.\\ In other words, $a^2$ is even (since
$2b^2$ is even).\\ Therefore, $a$ is even (the square of an odd number
is odd).\\ Therefore, $a^2$ is divisible by 4.\\ But $b$ is odd (since
$a/b$ is in lowest terms and $a$ is even).\\ Thus $2b^2$ is not
divisible by 4.\\ Thus $4$ divides $a^2$, but not $2b^2 = a^2$,
contradiction.

Since our assumption leads to a false conclusion, it must be false.
Thus, $\sqrt{2}$ is not rational.
\end{proof}

Note: this process is based on the assumption that math is consistent,
since otherwise it would be possible to prove something false.

We freely used lots of basic facts about divisibility, lowest terms
for fractions, definitions of square, all without reference or proof.

Pythagoras and his followers knew this proof, but suppressed it because
they axiomatically denied the existence of irrational numbers (so
their system was not consistent, because they also had an axiom that
every line had a numeric length).

\subsection{A Nonconstructive Existence Proof}

\begin{theorem}
For any number $n$, there is a prime number greater than $n$.
\end{theorem}
\begin{proof}
Fix $n$, and consider $n!+1=(1\cdot2\cdot3\cdots(n-1)\cdot n)+1$.  If
$n!+1$ is prime, we are done.  Otherwise, $n!+1$ has a prime factor
$x$ (relies on the prime number theorem).  By definition, $n!+1$ is
divisible by $x$ (without leaving a remainder).  But if $n!+1$ is
divided by a number less than $n$, the remainder is 1.  Therefore,
$x>n$.
\end{proof}

(Note: $n!+1$ need not be prime.  $5!+1 = 11^2$.)

We don't know what $x$ is, only that it exists.

Intuitionists would deny this is a proof.

\subsection{Proof by Cases}

Proof by cases: 
    \begin{itemize}
    \item show $p\implies (a \vee b)$
    \item show $a \implies q$ and $b \implies q$
    \item deduce $p \implies q$
    \end{itemize}

\begin{theorem}
$(\forall x P(x)) \vee A$ implies $\forall x (P(x)
\vee A)$
\end{theorem}
\begin{proof}
To prove the theorem, we need to show that if the hypothesis is true,
then the consequent is true.  So suppose the hypothesis is true.
There are two cases: either $A$  is true or $A$ is false.

Case 1: $A$ if true.  If $A$ is true, then $P(x) \vee A$ is true
regardless of the truth of $P(x)$.  Thus, $\forall x (P(x) \vee A)$ is
true.

Case 2: $A$ is false.  If $A$ is false, then the only way for the
hypothesis to be true is for the other disjunct, namely $(\forall x
P(x))$, to be true.  But if $P(x)$ is always true then certainly $P(x)
\vee A$ is always true, in other words $\forall x (P(x) \vee A)$.
\end{proof}



\subsection{Other Proof Methods}

\begin{itemize}
\item Indirect proof: from $\neg q \implies \neg p$, deduce $p
\implies q$ (similar to proof by contradiction).
\item Vacuous proof: if $p$ is false, then $p\implies q$ is true.
\begin{itemize}
\item if $x$ is an even prime greater than 2, then $x$ is a perfect
square.
\end{itemize}
\end{itemize}

\subsection{Fallacies}

There are several ways to generate in incorrect proof.

\begin{eqnarray*}
\sqrt{-1} &= &\sqrt{-1}\\
\sqrt{\frac{1}{-1}} &= &\sqrt{\frac{-1}{1}}\\
\frac{\sqrt{1}}{\sqrt{-1}} &= &\frac{\sqrt{-1}}{\sqrt{1}}\\
\sqrt{1}\cdot\sqrt{1} &= &\sqrt{-1}\cdot\sqrt{-1}\\
1 &= &-1\\
\end{eqnarray*}

Where's the bug?

There are several common fallacies:
\begin{description}
\item[Affirming the conclusion:]
\begin{itemize}
\item If you are tired, you will fall asleep
\item You fall asleep
\item therefore, you are tired
\end{itemize}
The fact that the conclusion is true does not make the hypothesis
true.  Maybe you are just bored.

\item[Denying the hypothesis:]
\begin{itemize}
\item If you work hard, you will pass the course
\item You don't work hard
\item therefore, you will fail the course.
\end{itemize}
Even if the hypothesis is false, the conclusion can be true.  Maybe
you are smart enough to pass without working.

\item[Circular reasoning:] proposition: If $n^2$ is not divisible by 3,
then $n$ is not divisible by 3.
\begin{itemize}
\item If $n^2$ is not divisible by 3, then $n^2$ is not
equal to $3k$ for any integer  $k$.
\item therefore, $n$ does not equal $3l$ for any integer $l$.
\item therefore, $n$ is not divisible by $3$.
\end{itemize}


\end{description}

If you assume (or prove) something FALSE, you can prove anything!

\end{document}
