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:
Bibliographic Details
Main Authors: Fejer, Peter A. (Author, http://id.loc.gov/vocabulary/relators/aut), Simovici, Dan A. (http://id.loc.gov/vocabulary/relators/aut)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: New York, NY : Springer New York : Imprint: Springer, 1991.
Edition:1st ed. 1991.
Series:Monographs in Computer Science,
Springer eBook Collection.
Subjects:
Online Access:Click to view e-book
Holy Cross Note: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.