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-2 
 
−
|| [[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.