# 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.
• 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 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.