Introduction to Proofs

Units

1. 1

   Logic and quantifiers

   3 lessons

   1. Propositions and truth tablesCombine propositions with not, and, or, if-then and if-and-only-if, and build truth tables column by column, including the conditional's rows read as a promise kept or broken.
   2. Logical equivalenceDecide whether two compound propositions are equivalent by comparing truth tables, use De Morgan's laws to negate 'and' and 'or', and tell the contrapositive, which is equivalent to a conditional, from the converse and inverse, which are not.
   3. Predicates and quantifiersRead a predicate P(x) over a domain through its truth set, decide statements with ∀ and ∃, negate them by flipping the quantifier, and see why the order of nested quantifiers matters.
2. 2

   Writing proofs

   4 lessons

   1. Definitions and direct proofsStart a proof from a definition and write it as full sentences with a reason for each step: the sum of two odd integers is even, and if a | b and b | c then a | c.
   2. Proof by casesSplit a proof into cases that cover every possibility (n even or odd, the remainders mod 3, the sign of x) and prove that n² + n is even and |xy| = |x||y|.
   3. Biconditionals and the contrapositiveProve an if-and-only-if statement by proving both directions, one of them by the contrapositive: n is odd if and only if n² is odd; and justify a chain of equivalent statements.
   4. Counterexamples, existence and uniquenessDisprove a universal claim by one counterexample, prove an existence claim by construction, and prove uniqueness by assuming two objects and showing they are equal.
3. 3

   Proof by contradiction

   2 lessons

   1. Contradiction and irrational numbersAssumes the negation and reaches an impossibility: √2 is irrational, and √3, with the lowest-terms step and the negation of the claim written out.
   2. Infinitely many primesEuclid's proof that there are infinitely many primes, the role of the product plus one, and proofs that there is no largest integer and no smallest positive rational.
4. 4

   Induction

   2 lessons

   1. Mathematical inductionProve a statement P(n) for every integer n ≥ 1 by a base case and an inductive step that uses the inductive hypothesis, and write the proof in full sentences.
   2. Strong inductionProve P(n) by assuming P(j) for every case from the base up to k, not only for k itself, and choose the right number of base cases for the step.
5. 5

   Sets

   2 lessons

   1. Proving set statementsProves A ⊆ B by element chasing and A = B by two inclusions: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and De Morgan's law for complements, beside the Venn picture that suggests them.
   2. Power sets and indexed familiesThe power set and its 2ⁿ members, unions and intersections over an index set such as the intervals (−1/n, 1/n), whose intersection is {0}.
6. 6

   Functions

   3 lessons

   1. Injective and surjective functionsProves f(x) = 3x + 5 is injective by assuming f(a) = f(b) and surjective onto R by solving f(x) = y, and shows x² is neither on R by counterexamples, with arrow and graph pictures.
   2. Composition and inversesComposition of injections is injective, of surjections surjective; a function has an inverse exactly when it is a bijection, worked on f(x) = (x − 1)/(x + 2).
   3. Images and preimagesf(A) and f⁻¹(B) for sets, f⁻¹(B ∪ C) = f⁻¹(B) ∪ f⁻¹(C), and why f(A ∩ B) ⊆ f(A) ∩ f(B) can be strict, shown with f(x) = x².
7. 7

   Equivalence relations

   2 lessons

   1. Equivalence relations and partitionsProves a relation is reflexive, symmetric and transitive, finds its equivalence classes, and shows that the classes partition the set and that every partition comes from one.
   2. Congruence classesCongruence mod n as an equivalence relation, the classes of Zₙ, and proof that addition and multiplication of classes are well defined.
8. 8

   Cardinality

   2 lessons

   1. Countable setsTwo sets have the same size when there is a bijection; lists the integers and the positive rationals (the zigzag through the grid) to show they are countable.
   2. Uncountable setsCantor's diagonal argument that the reals in (0, 1) are uncountable, and that no set has a bijection onto its power set.
9. 9

   Limits with epsilon and delta

   2 lessons

   1. Limits of sequencesThe definition of aₙ → L with ε and N, read off a graph of the terms entering a band of width 2ε; proves 1/n → 0 and (3n + 1)/(n + 2) → 3 with scratch work first.
   2. Limits of functionsThe ε-δ definition of lim f(x) = L as a box around the point; proves lim (2x + 1) = 7 as x → 3 and lim x² = 4 as x → 2, choosing δ = min(1, ε/5).