E-grāmata: Mathematical Foundations of Computer Science: Sets, Relations, and Induction

1 Elementary Set Theory.- 1.1 Introduction.- 1.2 Sets, Members,
Subsets.- 1.3 Building New Sets.- 1.4 Exercises and Supplements.- 1.5
Bibliographical Comments.- 2 Relations and Functions.- 2.1 Introduction.- 2.2
Relations.- 2.3 Functions.- 2.4 Sequences, Words, and Matrices.- 2.5 Images
of Sets Under Relations.- 2.6 Relations and Directed Graphs.- 2.7 Special
Classes of Relations.- 2.8 Equivalences and Partitions.- 2.9 General
Cartesian Products.- 2.10 Operations.- 2.11 Representations of Relations and
Graphs.- 2.12 Relations and Databases.- 2.13 Exercises and Supplements.- 2.14
Bibliographical Comments.- 3 Partially Ordered Sets.- 3.1 Introduction.- 3.2
Partial Orders and Hasse Diagrams.- 3.3 Special Elements of Partially Ordered
Sets.- 3.4 Chains.- 3.5 Duality.- 3.6 Constructing New Posets.- 3.7 Functions
and Posets.- 3.8 Complete Partial Orders.- 3.9 The Axiom of Choice and Zorns
Lemma.- 3.10 Exercises and Supplements.- 3.11 Bibliographical Comments.- 4
Induction.- 4.1 Introduction.- 4.2 Induction on the Natural Numbers.- 4.3
Inductively Defined Sets.- 4.4 Proof by Structural Induction.- 4.5 Recursive
Definitions of Functions.- 4.6 Constructors.- 4.7 Simultaneous Inductive
Definitions.- 4.8 Propositional Logic.- 4.9 Primitive Recursive and Partial
Recursive Functions.- 4.10 Grammars.- 4.11 Peanos Axioms.- 4.12 Well-Founded
Sets and Induction.- 4.13 Fixed Points and Fixed Point Induction.- 4.14
Exercises and Supplements.- 4.15 Bibliographical Comments.- 5 Enumerability
and Diagonalization.- 5.1 Introduction.- 5.2 Equinumerous Sets.- 5.3
Countable and Uncountable Sets.- 5.4 Enumerating Programs.- 5.5 Abstract
Families of Functions.- 5.6 Exercises and Supplements.- 5.7 Bibliographical
Comments.- References.