Proof and Logic

Patterns that hold for forty cases, or nine hundred million, and then fail, what a proof is and the words that organise one, how to read and write proofs, and first proofs from the definitions of even and odd.

Sentences with a truth value, the five connectives fixed by truth tables, why a conditional with a false hypothesis counts as true, tautologies and the laws of logical equivalence, converse and contrapositive, "necessary", "sufficient", "only if" and "unless", normal forms, and why a single connective is enough to build every truth table.

"For all" and "there exists", why the domain is part of every claim, how to negate any quantified statement mechanically, why the order of quantifiers decides what is said, unique existence, translating mathematical English, and the definitions of limit and continuity read symbol by symbol.

How to prove "if $P$ then $Q$" and "for every $x$" from definitions alone, with divisibility and the division algorithm as working material, proofs that split into cases, the triangle inequality, "if and only if", proofs that something exists with or without naming it, and disproof by counterexample.

Two indirect methods for statements the direct route cannot reach, used to prove that if $n^2$ is even then $n$ is even, that $\sqrt{2}$, $\sqrt{p}$ and ${\log }_{2}3$ are irrational, Euclid's lemma, that the primes never run out (even those of the form $4k+3$), and the pigeonhole principle, with how to choose a method and how to spot a fake contradiction.

Proving a statement for every natural number from two finite checks: ordinary and strong induction, well-ordering and why the three are one principle, sums, inequalities and divisibility, recursive definitions and Fibonacci identities, strengthening the hypothesis, a first look at structural induction, and the proof that all horses are one colour, taken apart.

Membership and set builder notation, subset proofs by element chasing and equality by double inclusion, union, intersection, difference, complement and symmetric difference with their laws, power sets and Cartesian products, unions and intersections of whole families, and Russell's paradox with the axioms that answered it.

A function as a set of ordered pairs with a stated domain and codomain, images and preimages and how they treat unions, intersections and complements, injective, surjective and bijective maps, composition, left, right and two-sided inverses, restriction, and how many functions join two finite sets.

Relations as sets of pairs, the reflexive, symmetric and transitive properties, equivalence classes and the theorem that they are the same thing as partitions, congruence modulo $n$ and the integers modulo $n$, well defined operations on classes, kernels of functions, and the rational numbers built as classes of pairs of integers.

Partial, total, strict and well orders, Hasse diagrams, maximal against greatest, suprema and infima in any poset, divisibility as a lattice, the lexicographic order, chains and antichains with Mirsky's theorem, and Zorn's lemma with what it is for.

Size defined by bijections, finite and countable sets made precise, explicit bijections for the integers, the pairs and the rationals, countable unions and the existence of transcendental numbers, Cantor's diagonal argument and his theorem on power sets, the Schröder and Bernstein theorem with proof, and the continuum hypothesis.

The reals as a complete ordered field, the least upper bound axiom that separates them from the rationals, and what follows from it: the Archimedean property, the density of the rationals and irrationals, square roots, nested intervals, decimal expansions and why $0.999\dots =1$.

Convergence of a sequence written with $\epsilon$ and $N$ and proved from the definition: limits and non-limits, uniqueness, boundedness, the algebra of limits, the squeeze theorem, monotone convergence from completeness, subsequences and the theorem of Bolzano and Weierstrass, and limits and continuity of functions with $\epsilon$ and $\delta$.