1. On Writing Proofs
Table of Contents | 2. The \(\sup\) and \(\inf\) ≫Since it’s only the very first week of the quarter and there has been only one lecture so far, this is the perfect opportunity to outline some common strategies, techniques, and pitfalls that students encounter when first writing proofs. Most broadly, we’ll be handling problems of the form “\(P\) implies \(Q\)”, where \(P\) and \(Q\) represent mathematical sentences.
\(P\) is called the assumption, or the assumptions if there are multiple statements, and \(Q\) is called the conclusion (or the conclusions). You may see questions posed as “Show that if \(P\), then \(Q\),” or “Suppose \(P\). Prove \(Q\).”
The most familiar method is the method of direct proof. A direct proof of the statement “\(P\) implies \(Q\)” would involve a chain of “direct” implications, either from definitions of mathematical terms or by applying known theorems or propositions (e.g. from lecture). There’s not too much else to say here.
In the first day of lecture, you have hopefully seen the principle of mathematical induction. Generally speaking, if a statement involves an arbitrary natural number \(n\), it’s a good idea to try using induction. It may not work, but it’s worth a try!
Proofs by Contraposition
The first nontrivial proof technique that I’ll present is the proof by contrapositive. The statement “\(P\) implies \(Q\)” is exactly equivalent to “Not \(Q\) implies not \(P\)” — flip the positions of the two statements, then negate the statements! Sometimes, this mirrored version of the statement ends up being easier to prove than the original statement.
Example 1.
Prove the following statement:
Let \(x\) be an integer. If there exists some integer \(n>1\) such that \(x^n\) is even, then \(x\) is also even.
Here, the assumption is “there exists an integer \(n>1\) such that \(x^n\) is even”, and the conclusion is “\(x\) is even”. The contrapositive swaps then negates (or negates and swaps) the two:
If \(x\) is not even, then there exists no integer \(n > 1\) such that \(x^n\) is even.
Phrased equivalently, one could say
If \(x\) is odd, then for every integer \(n > 1\), \(x^n\) is also odd.
This last version of the statement is pretty straightforward — the product of odd numbers is always odd! (You could present a fully rigorous proof by induction if you really wanted to, but this one is obvious enough.) Since the contrapositive of our original statement is true, the original statement is also true.
Remark 2. Negating Complicated Statements
In this example, negating a statement was not too difficult. Later in this course, statements can get very bulky and difficult to logically invert. For instance, what’s the logical negation of the following statement?
For all \(\epsilon > 0\), there exists a \(\delta > 0\) such that for all \(x\neq y\) with \(\left\lvert x-y \right\rvert < \delta \), \(\left\lvert x^2-y^2 \right\rvert < \epsilon \).
It’s too much! The trick is to read through the statement, left-to-right, and swap “for all” with “there exists” and vice-versa. Negate the conclusion of the statement when you get there.
There exists \(\epsilon > 0\) such that for all \(\delta > 0\), there exists \(x \neq y\) with \(\left\lvert x-y \right\rvert < \delta \) such that \(\left\lvert x^2-y^2 \right\rvert \geq \epsilon \).
You’ll inevitably have to restructure the grammar a bit, but that’s all there is to it!
Proofs by Contradiction
A cold-blooded cousin of the proof by contraposition is the proof by contradiction. Instead of proving that \(P\) implies \(Q\), one assumes that both \(P\) and “not \(Q\)” are simultaneously true, then demonstrates a logical contradiction.
Here’s a classic example:
Example 3.
Prove that \(\sqrt 2\) is not rational.
First of all, there are no assumptions. So, we just need to assume the opposite of the conclusion — suppose \(\sqrt 2\) is actually rational. Try working out the rest of the proof from here…
Solution
If \(\sqrt 2\) is rational, there exist integers \(a\) and \(b\) such that \(\sqrt 2 = \frac{a}{b}\). We may additionally assume that they share no common factors (i.e. the fraction is reduced).
Squaring both sides, we get \(2 = \frac{a^2}{b^2}\), so \(2b^2 = a^2\). Thus, \(a^2\) is an even number, and from the previous example, it follows that \(a\) is also even.
Write \(a = 2n\) for some integer \(n\). Then, \(2b^2 = 4n^2\), so \(b^2 = 2n^2\). Wait, \(b^2\) is also even, so \(b\) is even! \(a\) and \(b\) are both even, thus cannot be relatively prime, contradicting an earlier assumption. Thus, \(\sqrt 2\) is not rational. \(\square \)
Remark 4.
The fact that \(\sqrt 2\) is not rational begs an important question — if it’s not rational, what is it? Our reflexes say that \(\sqrt 2\) is irrational, but by definition an irrational number is a real number that’s not rational. So what’s a real number? Who’s to say that \(\sqrt 2\) is any more real than \(\sqrt{-1}\)?
This is the first topic of real analysis, and I’ll let you guys figure things out in lecture.
Bidirectional Statements
Statements of the from “\(P\) if and only if \(Q\)” are bidirectional statements, and it means that both \(P\) implies \(Q\) and \(Q\) implies \(P\). In other words, \(P\) is true whenever \(Q\) is true and vice-versa. If you see the words “if and only if” on a homework problem, that means you actually have to prove two things: first that \(P\) implies \(Q\), and second that \(Q\) implies \(P\).
Similarly, a statement may involve the equality of two sets of things: “If \(P\) is true, then the two sets \(A\) and \(B\) are equal”. To show that two sets \(A\) and \(B\) are equal, you need to show that \(x\in A\) if and only if \(x\in B\). Phrased another way, you need to show that both \(A\subseteq B\) and \(B\subseteq A\).
It’s a very common error to only prove one direction. Please do not do this on your homework or on your exams!
You can mix and match techniques — if you wanted to prove \(P\) if and only if \(Q\), it’s not uncommon to prove \(P\) implies \(Q\) and “not \(P\)” implies “not \(Q\)” (the contrapositive of \(Q\) implies \(P\)).
Some Tips
If you see a problem and you get stuck, don’t panic! Try doing the following:
- Explicitly write out the definitions of any mathematical terms in the assumptions and/or conclusions (e.g., what exactly is a “surjective” function?). This might help highlight an important assumption that you haven’t used yet.
- In a similar vein, if you are attempting a problem that has multiple assumptions (if \(P_1\) and \(P_2\) and \(P_3\), then \(Q\)), make sure you’re using all of the assumptions! If you instead prove something without using every assumption, that’s a sign that you may have overlooked something in your proof. Likewise, if you’re stuck in the middle of a proof, look through the list of assumptions and see if there’s something you haven’t used yet.
- If you’ve tried a direct proof and got stuck, try writing down the contrapositive or the first line of a proof by contradiction. Sometimes, this act will highlight an easier line of reasoning that you haven’t considered yet.
Here are some practise problems for you to feed on:
Problem 5.
Prove that there are no integer solutions to the equation \[6x^2+4y = 3.\]
Problem 6.
Let \(x\) and \(y\) be rational numbers. Prove that if \(x+y \geq 100\), then either \(x \geq 50\) or \(y \geq 50\).
Problem 7.
Let \(f(x)\) be a polynomial. Suppose that \(f ^{-1}(x)\) exists and is also a polynomial. Prove that \(f(x)\) is linear, i.e. \(f(x) = ax + b\) for some constants \(a\) and \(b\) with \(a\neq 0\).
Problem 8.
There are six people named \(A, B, C, D, E\), and \(F\) at a party with no stalkers — every pair of two people either both know each other or both don’t know each other. Prove that there is a trio that all know each other or are all strangers to each other.
Problem 9.
Let \(x\) and \(y\) be rational numbers. Prove that \(\left\lvert x+y \right\rvert = \left\lvert x \right\rvert + \left\lvert y \right\rvert\) if and only if \(xy=\left\lvert xy \right\rvert\).