Course Notes for Linear Algebra

Subsection 1.5.1 What Is A Proof?

Subsection 1.5.2 How to Write a Proof

• Remember that a proof is a chain of logical arguments. You should see this structure in the proofs you write. Look out for any sudden jumps or gaps in the logic.
• Use your starting assumptions. If you are proving something about a prime number, but never use the fact that it is prime, something very strange is going on. Either you are making a mistake, or the assumption that the number is prime is unnecessary.
• Don’t assume what you are trying to prove. The statement that you want to prove should show up at the very end of your proof. You can’t start with the statement you want to prove — logical implications don’t work that way. A proof should be a logical chain that starts with the assumptions of the proof and end with the desired conclusion.
• There is a huge difference between the rough work that goes into sketching a proof and the final proof. In the rough work, I will often start with the conclusion and make various attempts to see how I might get there. I try things, play around with ideas, do test cases. But when I write up a proof, I take all this rough work and try to put it into a formal logical chain with the desired statement coming at the end, as a conclusion.
• A good proof includes good writing as well as good symbolic mathematics. Write clear, complete sentences. Treat proof-writing with the same level of care as you would any academic writing.
• There are a number of special proof techniques that are worth some attention. I’ll spend the next section on two of these techniques. Not all proofs need a named technique, but these two are common enough to point out at the start.
• I can’t prove by example. Proof is not inductive reasoning, like that which is used in scientific experiments. A proof should prove all possible instances of the proposition, without exception. A bunch of examples are interesting and can provide hints, but they never constitue a proof. (That said, working with examples is often a great idea when working on a proof. Example gives insight and often show the way to the general arguent. They just can’t be used as the persuasive evidence in the proof.)
• Similarly, I can’t prove by diagram, drawing or illustration. Drawing pictures of what is going on is often a great way to build intuition, to understand the situation. It can often guild you in the right direction for constructing a proof. But a visualization itself does not constitute a complete logical argument. It doesn’t meet the standard that mathematics has set for a proof.

Subsection 1.5.3 Proof by Contradiction

• Step 1: Assume the statement is false. The statement says there are infinitely many prime numbers. If that is false, there must be only finitely many prime numbers. So my assumption is that there are finitely many prime numbers.
• Step 2: Work from the assumption to build a contradiction. The assumption says that there are finitely many prime numbers. Since there are only finitely many, I can index them: \(p_1, p_2, p_3, \ldots p_k\text{.}\) This is a finite list of some length \(k\text{.}\) Then consider a very large number formed by multiplying these all together and adding 1.

  \begin{equation*} m = p_1p_2 \ldots p_k + 1 \end{equation*}

  What are the prime factors of this number \(m\text{?}\) I know that all numbers break down uniquely into prime factors, so it must have prime factors. However, every prime number \(p_i\) in my list (which, by assumption, is all prime numbers) is a factor of \(m-1\text{.}\) A prime number can’t be the factor of two consecutive numbers, so none of the prime numbers are factors of \(m\text{.}\)
• Step 3: State the contradiction. The number \(m\) must have prime factors, but cannot have prime factors, since none of the primes \(p_i\) are factors. This is a contradiction: the number must have prime factors but has none.
• Step 4: Conclude that the original statement was false, which finishes the proof. The assumption that there were only finitely many prime numbers led to a contradiction. Therefore, by contradiction, I have proved that there are infinitely many prime numbers.

• Step 1: Assume the statement is false. The statement says that \(\sqrt{2}\) is irrational. If that is false, then \(\sqrt{2}\) must be rational. Therefore, my assumption is that \(\sqrt{2}\) is rational.
• Step 2: Work from the assumption to build a contradiction. If \(\sqrt{2}\) is rational, then there are integers \(a\) and \(b\) such that \(\sqrt{2} = \frac{a}{b}\text{.}\) Since any fraction can be written in the simplest terms, I can assume that \(a\) and \(b\) have no common factors. Then I can do some arithmetic with this equation.

  \begin{align*} \sqrt{2} \amp = \frac{a}{b}\\ 2 \amp = \frac{a^2}{b^2} \\ 2b^2 \amp = a^2 \end{align*}

  \(2\) divides the left side of the equation, so it must divide the right side as well, meaning that \(a^2\) must be even. But the squares of odd numbers are odd, and the squares of even numbers are even. Therefore, \(a\) must be even. I can write \(a = 2c\) for some integer \(c\text{.}\) Then I’ll replace \(a\) by \(2c\) in the equation and do a bit more arithmetic.

  \begin{align*} 2b^2 \amp = a^2 \\ 2b^2 \amp = (2c)^2 \\ 2b^2 \amp = 4c^2 \\ b^2 \amp = 2c^2 \end{align*}

  Now \(2\) divides the right side of the equation, so it must divide the left as well. That means that \(b^2\) is even, so \(b\) must be even.
• Step 3: State the contradiction. I assumed that \(a\) and \(b\) have no common factors since I wrote the fraction in the simplest terms. Now I have proved that both numbers are even, so \(2\) is a factor of both. This is a contradiction: \(a\) and \(b\) have no common factors, but \(2\) is a common factor.
• Step 4: Conclude that the original statement was false, which finishes the proof. The assumption that \(\sqrt{2}\) was rational produced to a contradiction, so I have proved that \(\sqrt{2}\) must be irrational.