Linear Algebra

$ \newcommand{\blah}{blah-blah-blah} \newcommand{\eqb}[1]{\begin{eqnarray*}#1\end{eqnarray*}} \newcommand{\eqbn}[1]{\begin{eqnarray}#1\end{eqnarray}} \newcommand{\bb}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\begin{bmatrix}#1\end{bmatrix}} $

Different ways of writing a proof

Proposition 2.1 $\sqrt{2}$ is not rational.

We'll use the proof of Proposition 2.1 to explore a number of notions about proofs.

First, some nomenclature:

You often see the terms theorem, lemma, proposition, and corollary in stating mathematical results.
A theorem is a major or "main" result, worth remembering and something that is often an important part of a larger body of work.
A lemma is a result that you prove on the way to proving a theorem, a sort of "helper" result. Often, a long proof has minor results along the way: it helps to write these as lemmas.
A proposition is sometimes used for results that aren't necessarily deep or important to the body of work, but are minor.

First version

Proof: (by contradiction)
Let $y = \sqrt{2}$ and assume $y$ is rational. Since $y$ is rational, $y$ can be expressed as a ratio of integers in simplest form: $y = \frac{p}{q}$. Which means that $\frac{p}{q} = \sqrt{2}$ or $p^2 = 2q^2$ and thus $p^2$ is even. But even squares are squares of even numbers, and thus $p$ is even, which means we can write $p$ as $p=2r$ for some number $r$. From this, $p^2 = 4r^2$. Combining this with $p^2=2q^2$, we see that $4r^2 = 2q^2$ or $q^2 = 2r^2$, and thus $q$ is even. Since both $p$ and $q$ are even, the ratio $\frac{p}{q}$ is not in the simplest form, which leads to a contradiction. $\Box$

Observe the following:

The proof is written in a narrative style with all the math in-lined.

There are phrases like "which means" and "from this" that direct the flow of logic.

There is a result that wasn't proved but assumed: the square root of an even square is even.

It was the second sentence, the first assertion, that was contradicted.

A proof by contradition can contradict any earlier assertion that flows from the assumptions.

Second version

Proof: (by contradiction)
Let $y = \sqrt{2}$ $$ \begin{array}{lll} \Rightarrow \;\;\;\;\; & \;\;\;\;\; y = \frac{p}{q} \;\;\;\;\; & \;\;\;\;\; \mbox{in simplied form for some integers } p,q \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; \frac{p}{q} = \sqrt{2} \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; p^2 = 2q^2 \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; p^2 \mbox{ is even} \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; p \mbox{ is even} \;\;\;\;\; & \;\;\;\;\; \mbox{because square roots of even squares are even} \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; p = 2r \;\;\;\;\; & \;\;\;\;\; \mbox{for some integer } r \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; p^2 = 4r^2 \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; 2q^2 = 4r^2 \;\;\;\;\; & \;\;\;\;\; \mbox{because $p^2 = 2q^2$ from earlier} \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; q^2 = 2r^2 \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; \mbox{$q$ is even} \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; \mbox{both $p$ and $q$ are even} \;\;\;\;\; & \;\;\;\;\; \\ \Rightarrow \;\;\;\;\; & \;\;\;\;\; \frac{p}{q} \mbox{ is not in simplest form} \;\;\;\;\; & \;\;\;\;\; \\ \end{array} $$ This contradicts the earlier assertion that $\frac{p}{q}$ is in simplest form, that arose from the assumption that $y$ is rational. $\Box$

Observe the following:

We could call this a three column style of writing a proof:

The first column is not really a column: it consists of narrative "glue" sentences like "Let $y=\sqrt{2}$" and the very last sentence above.
The second column is the combination of $\Rightarrow$ and a mathematical statement like $\Rightarrow y = \frac{p}{q}$.
The third column has an annotation to help understand the corresponding mathematical statement in the second column.

In general, three-column proofs are easier to read.

A larger proof is often broken up into sections, each of which might be in three-column form.

Some proofs are just better suited to narrative form.

Third version

Proof sketch: (by contradiction) Let $y = \sqrt{2}$ and assume $y$ is rational. Since $y$ is rational, $y$ can be expressed as a ratio of integers in simplest form: $y = \frac{p}{q}$. Squaring to get $p^2 = 2q^2$ shows that $p^2$ and therefore $p$ is even. A similar argument shows that $q$ is even, which contradicts the simplest form assumption for $\frac{p}{q}$.

Note:

A proof sketch is not a complete proof. Many pieces will be missing or statements will be glossed over.

The purpose of a proof sketch is to outline a proof idea.