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