Math · 03
Attempt these before you open a book or a video. Write the argument in the work box and the conclusion in the answer box. Check counts the problem only when both pass, and it does not open the solution. The solution stays locked for twenty minutes after you start the timer.
Attack 1
Prove that there is no rational number whose square is 2. Paragraph form.
Timer not started. Twenty minutes of real work before a solution.
Suppose \(p/q\) is in lowest terms and \((p/q)^2=2\). Then \(p^2=2q^2\), so \(p\) is even, say \(p=2k\). Then \(4k^2=2q^2\), so \(q^2=2k^2\) and \(q\) is even. Both even contradicts lowest terms. Hence no such rational exists.
Attack 2
Prove by induction that \(1+2+\cdots+n=n(n+1)/2\) for every positive integer \(n\).
Timer not started. Twenty minutes of real work before a solution.
Base \(n=1\): both sides equal 1. If the formula holds for \(n=k\), then the sum through \(k+1\) is \(k(k+1)/2+(k+1)=(k+1)(k/2+1)=(k+1)(k+2)/2\). By induction it holds for all positive integers.
Attack 3
Give an injective function \(\mathbb{N}\to\mathbb{N}\) that is not surjective. Say what this forbids you from concluding about “size.”
Timer not started. Twenty minutes of real work before a solution.
\(f(n)=n+1\), with \(\mathbb{N}=\{0,1,2,\ldots\}\) or \(\{1,2,\ldots\}\), either works. It misses 0 or 1. For infinite sets, injection does not imply surjection, so you cannot treat “into a proper subset” as a proof that a set is smaller in the finite sense. Cardinality needs a bijection, or a pair of injections and Cantor–Bernstein.
A proof is a finite piece of writing in which every sentence is either a definition, a hypothesis, or a consequence of earlier sentences by a rule you could name. Logic and set theory are the grammar of those sentences: connectives, quantifiers, membership, functions, relations. Induction is the one extra rule that talks about the natural numbers. Cardinality is the first place the grammar says something your intuition will reject, and that is why it is on this page.
You are not collecting logical symbols for their own sake. You are learning to block the three moves that produce fake mathematics: proving the converse instead of the statement, hiding a quantifier, and using an example as a proof of a universal claim. Enderton’s book is the ceiling for the logic itself. You do not need it to start analysis. You need Hammack’s chapters cold, including the calculus chapter, because ε–δ will otherwise feel like a new religion instead of a definition.
Write proofs as paragraphs. A stack of arrows with no verbs is not a proof. If you cannot read it aloud to someone who has not seen the problem, it is not finished.
Statements only. Write the argument before you reveal it. A revealed proof you did not attempt is a paragraph you will not be able to rebuild at 2am.
Quantifiers. A statement \(\forall x\in S,\, P(x)\) is false exactly when one counterexample exists. A statement \(\exists x\in S,\, P(x)\) is proved by exhibiting one element and checking \(P\). Negation swaps the quantifiers and negates the predicate.
This is the meaning of the symbols, not a theorem. The skill is mechanical: the negation of \(\forall\varepsilon>0\,\exists\delta>0\,\ldots\) is \(\exists\varepsilon>0\,\forall\delta>0\,\ldots\) with the inner inequality flipped. Write three examples until it is boring.
Sets, functions, relations. \(A\subseteq B\) means every element of \(A\) is in \(B\). \(A=B\) means both inclusions. A relation is a set of ordered pairs. It is an equivalence relation when it is reflexive, symmetric, and transitive, and then the equivalence classes partition the set. A function is injective, surjective, or bijective in the usual senses.
To prove inclusion, take an arbitrary element and chase membership. To prove two sets equal, write both inclusions. The partition claim: reflexivity puts each element in its own class; symmetry and transitivity make overlap of classes imply equality.
Proof patterns. Direct proof assumes the hypothesis and reaches the conclusion. Contrapositive proves \(\neg Q\Rightarrow\neg P\) instead of \(P\Rightarrow Q\). Contradiction assumes the negation of the claim and derives a false sentence. Existence may be constructive or not. Uniqueness is a separate sentence: any two objects satisfying the property are equal.
The contrapositive is equivalent to the implication because both fail only in the case \(P\) true and \(Q\) false. Contradiction is the observation that if \(\neg C\) implies a falsehood, then \(\neg C\) is false. These are schemas. A proof still has to contain the content of the problem.
Induction. If \(P(1)\) holds and \(P(k)\) implies \(P(k+1)\) for every \(k\ge 1\), then \(P(n)\) holds for every positive integer \(n\). Strong induction allows the inductive step to use all earlier cases. The well-ordering principle (every nonempty subset of the positive integers has a least element) is equivalent.
If some positive integer failed, the set of failures would have a least element \(m\). Then \(m\ne 1\), and \(m-1\) would satisfy \(P\), hence so would \(m\), a contradiction. That argument uses well-ordering. Going the other way is the usual least-element proof written as induction.
Cardinality. Two sets have the same cardinality when a bijection exists between them. \(\mathbb{N}\), \(\mathbb{Z}\), and \(\mathbb{Q}\) are countable. \(\mathbb{R}\) is not: Cantor’s diagonal argument. If there are injections both ways between two sets, there is a bijection (Cantor–Bernstein).
Countability of \(\mathbb{Q}\) is the zigzag through fractions in lowest terms. Diagonalization: any list of real numbers in \((0,1)\) misses the number whose \(n\)th digit differs from the \(n\)th digit of the \(n\)th listed number. Cantor–Bernstein can be quoted once you have used it; the proof is a chain argument you should read in Hammack and then rewrite.
Four rungs, in order. Do not skip a rung because the next one looks more serious.
Watch or read once. Do not study from this.
Hammack, Book of Proof, the landing page
Read once, do not study from this. Read the description and the table of contents so you see that counting, induction, relations, and a chapter of ε–δ are all in one book. Then close the page and open the PDF.
The thing you work through.
Richard Hammack, Book of Proof, 3rd edition, revision 3.4 (5 February 2025), ISBN 978-0-9894721-2-8
Free legal PDF, Creative Commons, AIM open textbook. This replaces Velleman as the working text because you can start tonight. Velleman, How to Prove It, ISBN 978-1-108-43953-4, is the paid book to buy if you want a second, slightly stricter pass. The ISBN was confirmed against the Open Library catalog; a stable publisher page was not.
The problem book.
Hammack, every exercise in Chapters 1–14, written
The book is the problem set. Do not use the solution section until a writeup exists. Munkres’s Chapter 1 exercises are the harder set-theory drill once Hammack feels short; the book is paid, ISBN 978-0-13-181629-9 for the 2nd edition catalog entry, and the topology page sends you there properly.
The hardest questions that exist at this level.
Kedlaya, The Putnam Archive
The public ceiling for timed proof-writing. Enderton, A Mathematical Introduction to Logic, ISBN 978-0-12-238452-3, is the paid logic ceiling; no free copy was verified, so it is named and not linked.
Names and links. The problem text stays on the source site. Copyrighted contest problems are not copied here. What follows is where they are and why they hurt.
Pass: twenty proofs from Hammack, at least two from each of direct proof, contrapositive, contradiction, induction, relations, and cardinality, written in paragraphs and read aloud. Plus the irrationality of \(\sqrt{2}\) and one diagonal argument, from memory, on a blank page. Fail if any proof uses an example as a universal claim.
Five sets. Finish a set before you touch the next. Full sentences, not a circled answer.
Ten problems to meet again. Logging a writeup schedules them at 1 day, 7 days, and 30 days in this browser.
Define injection and surjection, prove the sum formula by induction, and explain why a single example cannot prove a universal statement. Blank page.