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