Mathematical Foundations of Computer Science Sets, Relations, and Induction / by Peter A. Fejer, Dan A. Simovici.

Mathematical Foundations of Computer Science, Volume I is the first of two volumes presenting topics from mathematics (mostly discrete mathematics) which have proven relevant and useful to computer science. This volume treats basic topics, mostly of a set-theoretical nature (sets, functions and rela...

Full description

Saved in:
Main Authors: Fejer, Peter A. (Author, http://id.loc.gov/vocabulary/relators/aut), Simovici, Dan A. (http://id.loc.gov/vocabulary/relators/aut) eBook English New York, NY : Springer New York : Imprint: Springer, 1991. 1st ed. 1991. Monographs in Computer Science, Springer eBook Collection. Click to view e-book Loaded electronically.Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
• 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 Zorn’s 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 Peano’s 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.