# MAT5423

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

Catalog entry

Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.

Contents: (1) Propositional logic: Axioms and Rules of Inference. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms. (2) Predicate Logic: Existential and universal quantification, free variables and substitutions. Discussion of the various axiomatic systems for first-order logic (including axioms and rules of inference). The power and the limitations of axiomatic systems for logic: Informal discussion of the completeness and incompleteness theorems. (3) Sets and boolean algebras: Operations on sets. Correspondence between finitary set operations and propositional logic. Correspondence between infinitary operations and quantifiers. The power and limitations of the language of set theory: Informal discussion of the set-theoretic paradoxes and the need for axiomatic systems for set theory. (4) Relations: Special relations: Equivalence relations, partially ordered sets, maximum/minimum, maximal/minimal elements, least upper bounds and greatest lower bounds, totally ordered sets. (5) Functions: Operations of functions, direct image and inverse image. (6) Well-ordered sets: Correspondence between well-ordering relations and induction. Correspondence between well-ordering relations and choice functions. (7) Introduction to computability. Classical models of computation (recursive functions, and Turing models). Limitations of computation (the Halting Problem, fast-growing functions). Contemporary models of computation.

Sample textbooks:

[1] Gordon Pace, Mathematics of Discrete Structures foe Computer Science, Springer, 2012

[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
• Semigroups
• groups