Annotated Sample Proofs
These proofs are annotated to give you an idea of what goes into a proof and what is going on in each of them:
Corollary to Fermat’s Theorem (from Elementary Number Theory, 7th ed., Burton, 2011, p. 88)
If p is a prime, then ap ≡ a (mod p) for any integer a.
Proof. When1 p|a, the statement obviously holds; for, in this setting, ap ≡ 0 ≡ a (mod p)2 . If p|a, then according to Fermat’s theorem3 , we have ap−1 ≡ 1 (mod p). When this congruence is multiplied by a, the conclusion ap ≡ a (mod p) follows.
Annotations of Rationale
1This proof contains an implicit breakdown into two cases: when p divides a, and when it does not. It is valid because we know for certain one must be true, and we can therefore assume them one by one to complete the proof.
2This illustrates the idea of a direct proof: deriving elementary facts from the given circumstances.
3Another tenet of the direct proof (and most proofs in general) is citing previously established claims and theorems, either to set up the ongoing proof or to ”skip” proving something over again.
Theorem 1.1: Archimedean Property (ibid, p. 2)
If a and b are any positive integers, then there exists a positive integer n such that na ≥ b.
Proof. Assume that the statement of the theorem is not true4 , so that for some a and b, na < b for every5 positive integer n. Then the set
S = {b − na|n a positive integer}
consists entirely of pisitive integers. By the Well-Ordering Principle6 , S will possess a least element, say, b − ma. Notice that b − (m + 1)a also lies in S, because S contains all integers of this form. Furthermore, we have
b − (m + 1)a = (b − ma) − a < b − ma
contrary to the choice of b−ma as the smallest integer in S7 . This contradiction arose out of our original assumption that the Archimedean property did not hold; hence, this property is proven true8.
Annotations of Rationale
4Here, it is made quite clear this is a proof by contradiction. This is what we do in one of those, precisely: assume the outcome is not true.
5Note that some of the wording changed when we assumed the opposite. A proof by contradiction requires one to assume every piece of the conclusion is false and negate the entirety of the statement.
6Note that, after the key assumption of the statement’s falsehood, the proof continues through a string of true deductions similarly to a direct proof.
7This is the crux of the proof by contradiction: reaching a fundamental, inevitable impossibility from our set of assumptions.
8This review of the contradiction is thorough, but not always necessary
A False Statement (from the mind of Ian Kimmel for the purposes of this project)
Any one-to-one function f : R → R is also onto.
Counterexample. Consider f(x) = ex . This function is one-to-one on R9 ; however, it is not onto, as the range of the function does not cover any of (−∞, 0]10.
Annotated Rationale
9A valid counterexample to a statement meets all of its assumptions; here, we want a function from the set of real numbers to the set of real numbers that is one-to-one.
10As one would expect intuitively, a valid counterexample fails to meet the conclusion of the statement; here, our function does not cover the entire set of real numbers in its range. What a shame.