Supervised 5 groups in Lent 2024.

Syllabus

Proof [5 lectures]. Proofs in practice and mathematical jargon. Mathematical statements: implication, bi-implication, universal quantification, conjunction, existential quantification, disjunction, negation. Logical deduction: proof strategies and patterns, scratch work, logical equivalences. Proof by contradiction. Divisibility and congruences. Fermat’s Little Theorem.

Numbers [5 lectures]. Number systems: natural numbers, integers, rationals, modular integers. The Division Theorem and Algorithm. Modular arithmetic. Sets: membership and comprehension. The greatest common divisor, and Euclid’s Algorithm and Theorem. The Extended Euclid’s Algorithm and multiplicative inverses in modular arithmetic. The Diffie-Hellman cryptographic method. Mathematical induction: Binomial Theorem, Pascal’s Triangle, Fundamental Theorem of Arithmetic, Euclid’s infinity of primes.

Sets [9 lectures]. Extensionality Axiom: subsets and supersets. Separation Principle: Russell’s Paradox, the empty set. Powerset Axiom: the powerset Boolean algebra, Venn and Hasse diagrams. Pairing Axiom: singletons, ordered pairs, products. Union axiom: big unions, big intersections, disjoint unions. Relations: composition, matrices, directed graphs, preorders and partial orders. Partial and (total) functions. Bijections: sections and retractions. Equivalence relations and set partitions. Calculus of bijections: characteristic (or indicator) functions. Finite cardinality and counting. Infinity axiom. Surjections. Enumerable and countable sets. Axiom of choice. Injections. Images: direct and inverse images. Replacement Axiom: set-indexed constructions. Set cardinality: Cantor-Schoeder-Bernstein Theorem, unbounded cardinality, diagonalisation, fixed-points. Foundation Axiom.

Formal languages and automata [5 lectures]. Introduction to inductive definitions using rules and proof by rule induction. Abstract syntax trees. Regular expressions and their algebra. Finite automata and regular languages: Kleene’s theorem and the Pumping Lemma.