Course pages 2015–16
Discrete Mathematics
Lectures 1-17: Proofs, Numbers, and Sets
- Notes and Workouts
- Supervision exercises
Michaelmas term
Xmas break
2015 Paper 2 Question 9 (a) [solution notes]
2015 Paper 2 Question 8 (a) & (b) [solution notes]
2015 Paper 2 Question 7 (a) & (b) [solution notes]
2014 Paper 2 Question 7 [solution notes]
2007 Paper 2 Question 3 [solution notes]
2006 Paper 2 Question 3 [solution notes]
2006 Paper 2 Question 4 [solution notes]
Lent term
Easter break
2015 Paper 2 Question 9 (b) & (c) [solution notes]
2015 Paper 2 Question 8 (c) [solution notes]
2015 Paper 2 Question 7 (c) [solution notes]
2014 Paper 2 Question 8 [solution notes]
2013 Paper 2 Question 5 [solution notes]
2011 Paper 2 Question 5 [solution notes]
2009 Paper 1 Question 4 [solution notes]
2008 Paper 2 Question 3 [solution notes]
2007 Paper 2 Question 5 [solution notes]
2006 Paper 2 Question 5 [solution notes] - A note on enumerability.
- Q&A forum
- Lecture slides and topics
Michaelmas term
Lecture 1 (Nov 6): proof; implication.
Lecture 2 (Nov 9): contrapositive; modus ponens; bi-implication; divisibility; congruence.
Lecture 3 (Nov 11): divisibility; congruence; universal quantification; equality; conjunction.
Lecture 4 (Nov 13): existential quantification; unique existence; disjunction.
Lecture 5 (Nov 16): Fermat's Little Theorem.
Lecture 6 (Nov 18): negation; contrapositive; proof by contradiction.
Lecture 7 (Nov 20): natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; division theorem and algorithm.
Lecture 8 (Nov 23): modular arithmetic; sets; membership; comprehension; gcd; Euclid's Algorithm.
Lecture 9 (Nov 25): Euclid's Algorithm; properties of gcds; Euclid's Theorem; fields of modular arithmetic; Extended Euclid's Algorithm.
Lecture 10 (Nov 27): Extended Euclid's Algorithm; linear combinations; Diffie-Hellman cryptographic method: shared secret key, key exchange;
Lecture 11 (Nov 30): Mathematical induction; Fundamental Theorem of Arithmetic; Euclid's infinitude of primes; sets; extensionality; subsets and supersets; separation principle; Russell's paradox.
Lecture 12 (Dec 2): empty set; cardinality; powerset axiom; cardinality of powersets; powerset Boolean algebra; pairing axiom; ordered pairs; products; big unions.
Lent term
Lecture 13 (Jan 15): big unions; big intersections; union axiom; disjoint unions; relations; internal diagrams; relational composition; relational extensionality.
Lecture 14 (Jan 18): relations and matrices; directed graphs; adjacency matrix; reflexive-transitive closure;
Lecture 15 (Jan 20): preorders; partial functions; functions; retractions; sections; bijections; equal cardinality;
Lecture 16 (Jan 22): equivalence relations; set partitions; calculus of bijections; characteristic functions; finite cardinality; infinity axiom.
Lecture 17 (Jan 25): surjections; enumerability; injections; direct and inverse images; replacement axiom; set-indexed constructions; foundation axiom.