Discrete Mathematics

Summary notes

Proofs, Numbers, and Sets

• Notes
• Lectures
  Michaelmas term
    Lecture 1: introduction; proof; implication; modus ponens.
    Lecture 2: bi-implication; divisibility; congruence; universal quantification; equality; conjunction.
    Lecture 3: existential quantification; unique existence.
    Lecture 4: disjunction; Fermat's Little Theorem.
    Lecture 5: reciprocal in modular arithmetic; negation; proof by contradiction; proof by contrapositive.
    Lecture 6: natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; rings; fields; division theorem.
    Lecture 7: division algorithm; modular arithmetic; integer linear combinations.
    Lecture 8: sets; membership; comprehension; set equality; sets of common divisors; gcd.
    Lecture 9: Euclid's Algorithm; properties of gcds; Euclid's Theorem.
    Lecture 10
    Lecture 11: extended Euclid's Algorithm; integer linear combinations; mathematical induction.
    Lecture 12
  Lent term
    Lecture 13: Fundamental Theorem of Arithmetic; Euclid's infinitude of primes; sets; extensionality; subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom.
    Lecture 14: cardinality of powersets; powerset Boolean algebra; pairing axiom.
    Lecture 15: ordered pairs; products; big unions; big intersections; union axiom.
    Lecture 16: disjoint unions; relations; internal diagrams; relational extensionality; relational composition; matrices.
    Lecture 17: relations and matrices; directed graphs; adjacency matrix; reflexive-transitive closure; partial functions; functions.
    Lecture 18
    Lecture 19: inductive definitions; bijections; equal cardinality; calculus of bijections; characteristic functions; finite cardinality; infinity axiom; surjections and injections; axiom of choice; unbounded cardinality; replacement axiom; set-indexed constructions; foundation axiom.
• Exercises
  Solutions with commentary
  Michaelmas term
  1   On proofs
  2   On numbers
  3   More on numbers
  4   On induction
  Lent term
  5   On sets
  6   On relations, partial functions, and functions
  7   On bijections and equivalence relations
  8   On surjections, injections, and countability
• Note on enumerability.

Formal Languages and Automata

(Professor Frank Stajano)

The lectures for this final part of the course are pre-recorded and they are all already available to you right away.

Since I own the copyright and performance rights over my lectures (as does every Cambridge lecturer, according to the Statutes and Ordinances), I have chosen to produce curated videos of my lectures and to make them freely available to all, not just to students from this Department or from this University. You don't have to request access: just head over to my youtube channel, Frank Stajano Explains. Hit the thumbs-up if you benefit from the videos. Subscribe to the channel for new videos weekly.

Besides the videos themselves, you will also benefit from the questions that past students asked, which I answered in the comments section. If you have your own questions, feel free to ask them there as well (pseudonymously if you wish) so that others may also benefit from the answer.

This playlist contains the videos that cover the syllabus, whereas this slightly longer one contains all of those plus some useful extras.

• Lecture notes (2 up, with large margins for your own scribbles)
• Lecture slides (1 up)
• Example sheet