Proofs

Formal proofs like we just did are very precise.
- Very mechanical manipulation of the pieces of logic.
- Time consuming, but we know they're right.
- Not very practical for doing “real” proofs.
Usually, proofs are written much more informally.
- Easier for people to write and read.
- All of the logic is still there, we just don't have to be explicit about every detail.
Writing good proofs is an important skill for this course.
The goal is the same as with the more formal proofs: things you know are true imply the thing you want to prove.
Some terms:
- Conjecture: a statement that you think is true and can be proven (but hasn't been proven yet).
- Theorem: a statement that has been shown to be true with a proof.
- Proof: a valid argument that shows that a theorem is true.
- Premise: a condition for the theorem, like “if \(n\) is an even number…”.
- Lemma: a small theorem that we need to get to the proof we're interested in.
- Corollary: a small theorem that follows from the more important one.
There are some common ways to approach a proof.
- Knowing them will often get you started on a proof.
- No way to list them all, but can do the most common ones.

Disproving Conjectures

Theorems are usually implicitly “for all” statements.
- e.g. we will write “Let \(x\) and \(y\) be integers…” but mean “For all integers \(x\) and \(y\)…”
- In that case, disproving a conjecture is easy: find one example where it isn't true. (\(\neg\forall \equiv \exists\neg\))
e.g. Disprove the following conjecture: “If \(\sqrt{x}\) is irrational (i.e. cannot be written as an integer fraction), then \(x\) is irrational.”
Your answer: This is false for \(x=2\). [We will prove that \(\sqrt{2}\) is irrational later: for now, trust me.]

Direct Proof

Direct proof: when we want to prove a conditional statement \(p\rightarrow q\), we assume that \(p\) is true, and follow implications to get to show that \(q\) is then true.
- Mostly an application of hypothetical syllogism, \([(p\rightarrow r)\wedge(r\rightarrow q)]\rightarrow (p\rightarrow q)\).
- We just have to find the propositions that lead us to \(q\).
An example direct proof:
Theorem: If \(m\) is even and \(n\) is odd, then their sum is odd.

Proof: Since \(m\) is even, there is an integer \(j\) such that \(m=2j\). Since \(n\) is odd, there is an integer \(k\) such that \(n=2k+1\). Then, \[\begin{align*} m+n &= (2j) + (2k+1) \\ &= 2(j+k) + 1\,. \end{align*}\] Since \(j+k\) is an integer, we see that \(m+n\) is odd.∎
Some notes about a theorem and proof:
- The “Theorem” and “Proof” parts are clearly labelled.
- Some small details are left out where they are obvious. (e.g. the definition of “even” and “odd”)
- Everything is written in sentence form.
- … even the math: there is a period after “\(2(j+k) + 1\)” since that's where the sentence ends.
- The ∎ symbol marks the end of the proof. Some use □ or “Q.E.D.”. The book uses ◀.
In the example proof, it should be clear that we have proved this to be a tautology: \[(\mbox{\(m\) is even and \(n\) is odd}) \rightarrow (\mbox{\(m+n\) is odd.})\]
- … and we did it by following a path of implications from the premise to the conclusion.
- That's a direct proof.
Another example:
Theorem: If \(n\) is an even integer, then \(n^2\) is even.

Proof: Since \(n\) is even, there is an integer \(k\) such that \(n=2k\). Then, \[\begin{align*} n^2 &= (2k)^2 \\ &= 4k^2 \\ &= 2(2k^2)\,. \end{align*}\] Since \(2k^2\) is an integer, \(n^2\) is even.∎
Other types of proofs are indirect proofs.

Proof by Contraposition

We know that \(p\rightarrow q\equiv \neg q\rightarrow \neg p\).
So, if we want to prove \(p\rightarrow q\), it would certainly be good enough to directly prove \(\neg q\rightarrow \neg p\).
- That is a proof by contraposition.
- Can be much easier, depending on the theorem.
An example proof by contraposition:
Theorem: If \(x\) is an irrational number, then \(1/x\) is also irrational.

Proof: Suppose for contraposition that \(1/x\) is rational. Then there must be integers \(m\) and \(n\) so that, \[\begin{align*} 1/x &= m/n\\ 1/(1/x) &= 1/(m/n) \\ x &= n/m \,. \end{align*}\] By contraposition, we see that the theorem is true.∎
There is something very awkward about writing contraposition proofs. I never would, but would do a proof by contradiction instead…

Proof by Contradiction

Proof by contradiction is very powerful.
The idea is based on this tautology (where we want to prove \(p\)): \((\neg p\rightarrow\mathrm{F})\rightarrow p\).
- If we assume our conjecture is false, and then manage to prove a contradiction (proposition that's always false), then the only possible conclusion is that \(p\) is true.
- Or informally: if it doesn't make any sense for \(p\) to be false, it must be true.
If we're proving an implication (which we usually are), assuming the conjecture is false means assuming that \[\neg(p\rightarrow q) \equiv \neg(\neg p\vee q) \equiv p\wedge\neg q\,.\]
- In other words, assume all of the premises are true, but that the conclusion is false.
- Try to get from there to a contradiction.
An example proof by contradiction:
Theorem: If \(n\) is an even perfect square with both \(m\) and \(n\) integers and \(n=m^2\), then \(m\) is even.

Proof: Suppose \(n\) is even, but assume for contradiction that \(m\) is not. Then \(m\) can be written as \(m=2k+1\) for some integer \(k\). Then, \[\begin{align*} n &= m^2 \\ &= (2k+1)^2 \\ &= 4k^2 + 4k + 1 \\ &= 2(2k^2 + 2k) + 1\,. \end{align*}\] Since \(k\) is an integer, we see that \(n\) is odd.

This contradicts the premise that \(n\) is even, so by contradiction we conclude that \(m\) is even.∎
Remember what's happening:
1. Assume the conclusion you want to be true is false. (\(m\) is odd.)
2. Work your way to a contradiction. (\(n\) is both even and odd.)
3. By contradiction, conclude that the conjecture is true. (\(m\) is even.)
Another example:
Theorem: \(\sqrt{2}\) is irrational.

Proof: Suppose for contradiction that \(\sqrt{2}\) is rational and can be written in lowest terms as \(\sqrt{2}=m/n\) with integers \(m\) and \(n\). Then, \[\begin{align*} \sqrt{2} &= m/n \\ \sqrt{2}^2 &= (m/n)^2 \\ 2 &= m^2/n^2 \\ 2n^2 &= m^2\,. \end{align*}\] But if \(2n^2 = m^2\), then \(m^2\) is even, so \(m\) must be even and we can find an integer with \(m=2k\). Then, \[\begin{align*} 2n^2 &= (2k)^2 \\ 2n^2 &= 4k^2 \\ n^2 &= 2k^2 \\ \end{align*}\]

So, \(n\) must also be even. Thus \(m\) and \(n\) have a common factor of 2: this contradicts the assumption that \(m/n\) was in lowest terms. By contradiction we conclude that \(\sqrt{2}\) is irrational.∎

Proof by Cases

Sometimes, it's not possible (or very difficult) to prove the whole theorem at once.
- e.g. a “For all integers…” theorem might be very different for evens and odds, or for primes and non-primes, or …
- If we could prove each case separately, that would be enough.
A proof by cases relies on this equivalence: \[(p_1\vee p_2\vee\cdots\vee p_n) \rightarrow q \equiv (p_1\rightarrow q)\wedge (p_2\rightarrow q)\wedge\cdots\wedge (p_n\rightarrow q)\,.\]
- So, if we can divide the premise up into cases, and prove each case (by any method we like), we're done.
An example proof by cases:
Theorem: If \(n\) is an integer, then \(3n^2+n+10\) is even.

Proof: We will show by cases, for even and odd \(n\).
Case 1: Suppose \(n\) is even. Then there is a \(k\) such that \(n=2k\) and, \[\begin{align*} 3n^2+n+10 &= 3(2k)^2 + 2k + 10 \\&= 6k^2 + 2k + 10 \\&= 2(3k^2 + k + 5)\,. \end{align*}\]
Case 2: Suppose \(n\) is odd. Then there is a \(k\) such that \(n=2k+1\) and, \[\begin{align*} 3n^2+n+10 &= 3(2k+1)^2 + (2k+1) + 10 \\&= 3(4k^2+4k+1) + (2k+1)+ 10 \\&= 12k^2+14k+14 \\&= 2(6k^2+7k+7)\,. \end{align*}\]
By cases, we see that the theorem is true for all integers.∎
Note: make sure the cases you come up with really cover all possibilities. (Don't miss zero, or prime numbers, or some other easy-to-forget case.)
Proof by exhaustion is similar, but can be used when there is a small set of cases.
- … and you can just try them all.
- e.g. “Show that there is no integer \(0\le n < 5\) such that…”. Just try \(n=0, 1, 2, 3, 4\) and show that none of them work.

Existence Proofs

So far, all of the theorems we have been looking at have been “for all…” statements.
- … even if they didn't say “for all” explicitly.
Theorems in the form “there exists a…” are usually much easier to prove true.
- Just find one.
- That might be hard, but at least the idea is easy.
An example existence proof:
Theorem: There is an integer \(n\) with the property \(|n^2-5| ≤ 1\).

Proof: For \(n=2\), we have \(|n^2-5|=1\).∎
Another example that's less obvious:
Theorem: Between each two rational numbers, there is an irrational number.

Proof strategy: We know that adding a rational number and an irrational number gives an irrational number. We just have to find an irrational number small enough to add to stay in between.

Proof: Let \(x\) and \(y\) be two rational numbers. Without loss of generality, assume that \(x<y\). Let \(d=y-x\) be the difference between the two.
Let \(z=x+d\sqrt{2}/2\). We know that \(\sqrt{2}/2\) is between 0 and 1 (it's approximately 0.707), so \(x<z<y\). We know that it is irrational, so \(z\) is irrational and between \(x\) and \(y\).∎
Note on “without loss of generality”…
- It gets said a lot in proofs.
- It means something like “we know things must be one way or the other and it doesn't matter which; let's just assume one and go from there.”
- In the above proof, we labelled the two numbers \(x\) and \(y\), without anything to distinguish them. (There's nothing special about \(x\) yet.) One of them has to be the biggest one: we'll pick \(y\) just so we know.
- You have to be careful that you really are making an arbitrary choice. (Above: we hadn't said anything about \(x\) that might have made it the larger in some cases.)
Disproving a “there exists” statement is harder: \(\neg\exists\equiv\forall\neg\).
- To show that such a statement is false, you must prove that the negation is true for all values.

Other Methods

There are many other ways to prove a theorem.
- But the goal is always the same: show that it is a tautology.
- We will talk about a few more, but no single course could cover them all.
- You are always allowed to use any (valid) inference rules. You don't need to exactly follow one of these methods.
- There are probably many ways to prove a particular theorem. Any valid proof counts.
If you need to prove a “if and only if” statement, it is necessary to prove both directions: \(p\rightarrow q\) and \(q\rightarrow p\).
- In examples above, we proved that for integers \(m\) and \(n\) with \(n=m^2\), \(n\) is even if and only if \(m\) is even.
- The two halves can use completely different proof methods.
Finding proofs is hard.
- And it's the reason mathematics is interesting.
- You didn't think it was all “follow this recipe”, did you?
Tips:
- It never hurts to try a contradiction. Suppose the conclusion is false and see what happens.
  - Maybe you do a direct proof: erase the assumption.
  - Maybe you ignore the premises and do an contraposition proof.
  - Maybe you get to a contradiction: proof by contradiction.
- You can always use other proven theorems. (e.g. above, we used that the sum of a rational and irrational was irrational: that is proved somewhere in the text.) Finding related theorems can be very helpful.
- Even if the theorem doesn't help, its proof might. Maybe a similar proof can work for your conjecture.
- Try working back from the conclusion. Since we're usually building a chain of implications, try finding things that the premises imply, or that would imply the conclusion. If you can meet in the middle, you're done.
- Always rewrite so it looks like you knew what you were doing the whole time.
The next topics (sets, functions, sequences, integers, …) are important on their own, so we need to study them. They will also provide many opportunities to prove things.