Discrete Mathematics: A Concise Introduction

✍ Scribed by George Tourlakis

• Publisher: Springer
• Year: 2024
• Tongue: English
• Leaves: 266
• Series: Synthesis Lectures on Mathematics & Statistics
• Edition: 1
• Category: Library

✦ Synopsis

This book is ideal for a first or second year discrete mathematics course for mathematics, engineering, and computer science majors. The author has extensively class-tested early conceptions of the book over the years and supplements mathematical arguments with informal discussions to aid readers in understanding the presented topics. “Safe” – that is, paradox-free – informal set theory is introduced following on the heels of Russell’s Paradox as well as the topics of finite, countable, and uncountable sets with an exposition and use of Cantor’s diagonalisation technique. Predicate logic “for the user” is introduced along with axioms and rules and extensive examples. Partial orders and the minimal condition are studied in detail with the latter shown to be equivalent to the induction principle. Mathematical induction is illustrated with several examples and is followed by a thorough exposition of inductive definitions of functions and sets. Techniques for solving recurrence relations including generating functions, the O- and o-notations, and trees are provided. Over 200 end of chapter exercises are included to further aid in the understanding and applications of discrete mathematics.

✦ Table of Contents

Preface
What to Include? What to Omit?
The Chapters
Contents
1 Some Elementary Informal Set Theory
[DELETE]
1.1 Russell's Paradox'' 2 Safe Set Theory [DELETE] 2.1 TheReal Sets''
2.2 What Caused Russell's Paradox
2.3 Some Useful Sets
2.4 Operations on Classes and Sets
2.5 The Powerset
2.6 The Ordered Pair and Finite Sequences
2.7 The Cartesian Product
2.7.1 Strings or Expressions Over an Alphabet
2.8 Exercises
3 Relations and Functions
[DELETE]
3.1 Relations
3.2 Transitive Closure
3.2.1 Computing the Transitive Closure
3.2.2 The Special Cases of Reflexive Relations on Finite Sets
3.2.3 Warshall's Algorithm
3.3 Equivalence Relations
3.4 Partial Orders
3.5 Functions
3.5.1 Lambda Notation
3.5.2 Kleene Extended Equality for Function Calls
3.5.3 Function Composition
3.6 Finite and Infinite Sets
3.7 Diagonalisation and Uncountable Sets
3.8 Operators and the Cantor-Bernstein Theorem
3.8.1 An Application of Operators to Cardinality
3.9 Exercises
4 A Tiny Bit of Informal Logic
4.1 Enriching Our Proofs to Manipulate Quantifiers
4.2 Exercises
5 Induction
[DELETE]
5.1 Inductiveness Condition (IC)
5.2 IC Over mathbbN
5.2.1 Well-Foundedness
5.2.2 Induction Examples
5.3 Inductive Definitions of Functions
5.3.1 Examples on Inductive Function Definitions
5.3.2 Fibonacci-like Inductive Definitions; Course-of-Values Recursion
5.4 Exercises
6 Inductively Defined Sets; Structural Induction
[DELETE]
6.1 Set Closures
6.2 Induction Over a Closure
6.3 Closure Versus Definition by Stages
6.4 Exercises
7 Recurrence Equations and Their Closed-Form Solutions
[DELETE]
7.1 Big-O, Small-o, and the ``Other'' sim
7.2 Solving Recurrences; the Additive Case
7.3 Solving Recurrences; the Multiplicative Case
7.4 Generating Functions
7.5 Exercises
8 An Addendum to Trees
[DELETE]
8.1 Trees: More Terminology
8.2 A Few Provable Facts About Trees
8.3 An Application to Summations
8.4 How Many Trees?
8.5 Exercises
References
Index

✦ Subjects

Discrete Mathematics; Relations; Functions; Recurrence Equations; Generating Functions; Informal Set Theory; Spanning Trees; Diagonalisation