Difference between revisions of "MAT5433"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Created page with "Introduction to basic discrete structures. '''Sample textbooks''': [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available...")
 
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
Introduction to basic discrete structures.
+
== Catalog entry ==
  
'''Sample textbooks''':  
+
''Prerequisite'':
 +
Discrete Mathematics (MAT 3003) or Real Analysis I (MAT 4213), or instructor consent.
  
[1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available online [https://web.stanford.edu/class/cs103x/cs103x-notes.pdf here]
+
''Contents''
 
+
 The Zermelo-Fraenkel axioms, ordinals and cardinals, the Axiom of Foundation, the Reflection Principle, ordinal-definable sets, relative consistency of the Axiom of Choice, Fraenkel-Mostowski models, relative consistency of the negation of the Axiom of Choice, consistency of the Generalized Continuum Hypothesis.
[2]
 
 
 
 
 
'''Catalog entry'''
 
 
 
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
 
 
 
Catalog entry:
 
 
 
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. 
 
 
 
Contents
 
(1) Relations: Cartesian products, relations, properties of relations, equivalence relations and partitions. (2) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles, Zorn's Lemma, lattices, boolean algebras, circuit design. (3) Graphs: Euler and Hamiltonian paths and circuits, matching, graph coloring, Ramsey’s theorem, trees and searching. (4) Binary operations: Groups and semigroups, products and quotients of groups, other algebraic structures.
 
 
 
 
 
 
 
 
 
 
 
 
 
==Topics List==
 
{| class="wikitable sortable"
 
! Week !! Topic !! Sections from Koltuns's book !! Prerequisite
 
|-
 
|  1-
 
|| [[Counting]]
 
|| 10.1-10-2
 
|| MAT1313, CS2233/2231, or instructor consent.
 
|-
 
|  3 
 
|| [[Inclusion-Exclusion Principle]]
 
|| 2.5-2.7.
 
||
 
|-
 
|  4 
 
|| [[The Pigeonhole Principle]]
 
|| 12.1-12.3
 
||
 
|-
 
|  Graphs 
 
|| [[Asymptotics]]
 
|| 13.1-13.2
 
||
 
|-
 
|  8 
 
|| [[Relations]]
 
|| 5.1-6.3
 
||
 
|-
 
|  9-10 
 
|| [[Discrete structures]]
 
|| 7.1-8.4
 
||
 
|-
 
|  10-16 
 
|| [[Models of computation]]
 
|| 10.1-10.4
 
||
 
|}
 

Latest revision as of 19:30, 24 March 2026

Catalog entry

Prerequisite: Discrete Mathematics (MAT 3003) or Real Analysis I (MAT 4213), or instructor consent.

Contents  The Zermelo-Fraenkel axioms, ordinals and cardinals, the Axiom of Foundation, the Reflection Principle, ordinal-definable sets, relative consistency of the Axiom of Choice, Fraenkel-Mostowski models, relative consistency of the negation of the Axiom of Choice, consistency of the Generalized Continuum Hypothesis.