MAT3003

Introduction to the mathematics of discrete structures with emphasis on structures for computer science.

Catalog entry

Prerequisite: Combinatorics and Probability MAT2313, or Applied Graph Theory MAT4323, or instructor consent.

Contents: Partially ordered sets, maximum/maximal and minimum/minimal elements. Well-ordered sets. Maximality principlies (Zorn's lemma, Well-ordering principle, Hausdorff maximality lemma). Boolean algebras and the Stone representation theorem. Generalizations of the Stone representation theorem.

Sample textbooks:

[2] Vladlen Koltun, Discrete Structures Lecture Notes, Stanford University, 2008. Freely available here.

Topics List

Week	Topic	Sections from Pace's book		Sections from Pace's book	Prerequisites.
1	Propositional logic	2.1-2.4	Proofs boolean models connections between boolean models and proofs	MAT1313 or CS2233/2231, or equivalent.
2	Completeness and soundness	2.5	Completeness and soundness of propositional logic
5-6	Predicate calculus	3.1-3.5	Limits of propositional logic free variables and substitution.
7	Sets and boolean algebras	4.1-4.5	Set comprehension. Finitary and general operations on sets.
8	Sets and boolean algebras	4.6	Boolean algebras and boolean rings.
9	Relations	5.1-5.7	Relations and sets Inverse of a relation and composition of relations Beyond binary relations
10	Classifying Relations	6.1-6.3	Totality Surjectivity Injectivity Functionality
11-12	Discrete structures	7.1-8.4	Graphs Binary operations Semigroups groups
13-14	Reasoning about programs	10.1-10.4	Algorithms Program semantics Uncomputability