MAT5423 - Revision history

Jose.iovino at 19:44, 29 January 2025

2025-01-29T19:44:48Z

Jose.iovino at 22:59, 24 March 2023

2023-03-24T22:59:07Z

Jose.iovino at 22:16, 24 March 2023

2023-03-24T22:16:57Z

Jose.iovino at 22:15, 24 March 2023

2023-03-24T22:15:30Z

Jose.iovino at 21:31, 24 March 2023

2023-03-24T21:31:12Z

Jose.iovino at 21:18, 24 March 2023

2023-03-24T21:18:26Z

Jose.iovino: /* Topics List */

2023-03-18T23:32:04Z

Topics List

Jose.iovino: /* Topics List */

2023-03-18T23:31:20Z

Topics List

Jose.iovino: /* Topics List */

2023-03-18T22:42:43Z

Topics List

Jose.iovino at 22:12, 18 March 2023

2023-03-18T22:12:54Z

@@ Line 1: / Line 1: @@
 '''Catalog entry'''
-''Prerequisite'': Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
+''Prerequisite'': Combinatorics and Probability [[MAT2313]], or Applied Graph Theory [[MAT4323]], or instructor consent.
 ''Contents'':
-(1) Propositional logic: Axioms and Rules of Inference. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms.
+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.

@@ Line 1: / Line 1: @@
-Introduction to basic discrete structures.
+Introduction to the mathematics of discrete structures with emphasis on structures for computer science.
@@ Line 20: / Line 14: @@
 (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.
@@ Line 42: / Line 44: @@
 || [[Completeness and soundness]]
 || 2.5
-|| Completeness and soundness of propositional logic
+||
 ||
 |-
@@ Line 53: / Line 56: @@
 ||
 |-
-|  5
+|  7
 || [[Sets and boolean algebras]]
 || 4.1-4.5
@@ Line 61: / Line 64: @@
 ||
 |-
-|  6
+|  8
 || [[Sets and boolean algebras]]
 || 4.6
-|| Boolean algebras and boolean rings.
+||
 ||
 |-
-|  7
+|  9
 || [[Relations]]
 || 5.1-5.7
@@ Line 76: / Line 80: @@
 ||
 |-
-|  8
+|  10
 || [[Classifying Relations]]
 || 6.1-6.3
@@ Line 86: / Line 90: @@
 ||
 |-
-|  9-10
+|  11-12
 || [[Discrete structures]]
 || 7.1-8.4
@@ Line 95: / Line 99: @@
 ||
 |-
-|  11-13
+|  13-14
 || [[Reasoning about programs]]
 || 10.1-10.4

@@ Line 74: / Line 74: @@
 * Inverse of a relation and composition of relations
 * Beyond binary relations
+||
 |-
 |  8
@@ Line 84: / Line 84: @@
 * Injectivity
 * Functionality
 |-
 |  9-10
@@ Line 92: / Line 93: @@
 * Semigroups
 * groups
 |-
 |  11-13
@@ Line 100: / Line 102: @@
 * Program semantics
 * Uncomputability
 |}

@@ Line 28: / Line 28: @@
 ==Topics List==
 {| class="wikitable sortable"
-! Week !! Topic !! Sections from Pace's book !! MAT1313, or CS2233/2231, or instructor consent.
+! Week !! Topic !! Sections from Pace's book !! !! Sections from Pace's book !! Prerequisites.
 |-
 |  1
 || [[Propositional logic]]
 || 2.1-2.4
 || MAT1313 or CS2233/2231, or equivalent.
 |-
 |  2
 || [[Completeness and soundness]]
-|| 2.5-2.7.
+|| 2.5
 ||
 |-
-|  3-4
+|  5-6
 || [[Predicate calculus]]
 || 3.1-3.5
 ||
 |-
-|  5-6
+|  5
 || [[Sets and boolean algebras]]
-|| 4.1-4.8
+|| 4.1-4.5
 ||
 |-
-|  7-8
+|  7
 || [[Relations]]
-|| 5.1-6.3
+|| 5.1-5.7
 ||
 |-
 |  9-10
@@ Line 59: / Line 89: @@
 || 7.1-8.4
 ||
 |-
 |  11-13
-|| [[Mathematical models of computation]]
+|| [[Reasoning about programs]]
 || 10.1-10.4
 ||
 |}

@@ Line 13: / Line 13: @@
 ''Contents'':
-(1) Propositional logic: Axioms and Rules of Inference. Boolean Algebras. Limitations of propositional logic: Informal introduction to quantifiers and syllogisms.
+(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: Properties of relations. Special relations: Equivalence relations, partially ordered sets, totally ordered sets.
+(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, the busy beaver problem, fast-growing functions). Contemporary models of computation.
+(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.