Discrete Mathematics

Proofs, Numbers, and Sets

Notes
Lectures
Michaelmas term
  Lecture 1: introduction; proof; implication; modus ponens; bi-implication.
  Lecture 2: divisibility; congruence; universal quantification; equality.
  Lecture 3: conjunction; existential quantification; unique existence.
  Lecture 4: unique existence; disjunction; Fermat's Little Theorem; reciprocal in modular arithmetic; negation; proof by contradiction.
  Lecture 5: proof by contrapositive; natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; rings; fields.
  Lecture 6: division theorem; division algorithm; modular arithmetic; integer linear combinations.
  Lecture 7: sets; membership; comprehension; set equality; sets of common divisors; gcd; Euclid's Algorithm.
  Lecture 8: properties of gcds; Euclid's Theorem; extended Euclid's Algorithm; Diffie-Hellman cryptographic method: shared secret key, key exchange.
  Lecture 9: mathematical induction; Fundamental Theorem of Arithmetic; Euclid's infinitude of primes.
  Lecture 10: sets; extensionality; subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom; cardinality of powersets.
  Lecture 11: powerset Boolean algebra; pairing axiom; ordered pairs; products.
  Lecture 12: big unions; big intersections; union axiom; disjoint unions.