skip to primary navigationskip to contentDiscrete 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.
Lecture 5:
reciprocal in modular arithmetic; negation; proof by contradiction;
proof by contrapositive; natural numbers; monoids; commutativity.
Lecture 6:
semirings; cancellation; inverses; integers; rationals; rings; fields.
division theorem; division algorithm.
Lecture 7:
modular arithmetic; integer linear combinations;
sets; membership; comprehension; set equality; sets of common
divisors; gcd; Euclid's Algorithm.
Lecture 8:
Euclid's Algorithm; properties of gcds; Euclid's Theorem; extended
Euclid's Algorithm.
Lecture 9:
reciprocals in modular arithmetic; key exchange; mathematical
induction; Fundamental Theorem of Arithmetic.
Lecture 10:
Euclid's infinitude of primes; 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.
Lecture 12:
products; big unions; big intersections; union axiom; disjoint
unions.
Lent term
Lecture 13:
relations; internal diagrams; relational extensionality; relational
composition; matrices.
Lecture 14:
relations and matrices; directed graphs; adjacency matrix;
preorders; reflexive-transitive closure.
Lecture 15:
partial functions; functions; inductive definitions.
Lecture 16:
retractions and sections; bijections; equal cardinality; equivalence relations;
set partitions.
Lecture 17:
calculus of bijections; characteristic functions; finite cardinality;
infinity axiom.
Lecture 18:
surjections and injections; axiom of choice; enumerability;
uncountable and unbounded cardinality.
Lecture 19:
direct and inverse images; replacement axiom; set-indexed
constructions; foundation axiom.
Formal Languages and Automata
Learning Materials
Additional notes
