CONTENTS
PREFACE x
Notation xiii
0 MATHEMATICAL MODELS 1
0.0 Introduction 1
0.1 Principles and Models 1
0.2 Mathematical Models 2
0.3 Purposes of Models 6
1 MATHEMATICAL REASONING 8
0 Introduction 8
1 Propositions 9
2 Predicates and Quantifiers 20
3 Quantifiers and Logical Operators 29
4 Logical Inference 39
5 Methods of Proof 47
6 Program Correctness 57
Axioms of Assignment 69
2 SETS 75
0 Introduction 75
1 The Primitives of Set Theory 75
2 The Paradoxes of Set Theory 79
3 Relations Between Sets 82
4 Operations on Sets 85
5 Induction 95
Inductive Definition of Sets 95
Recursive Procedures 98
Inductive Proofs 100
6 The Natural Numbers 108
7 Set Operations on I* 111
3 BINARY RELATIONS 120
0 Introduction 120
1 Binary Relations and Digraphs 120
2 Trees 131
Search Trees 136
Tree Traversal Algorithms 140
3 Special Properties of Relations 145
4 Composition of Relations 149
5 Closure Operations on Relations 155
6 Order Relations 164
{Some Additional Concepts for Posets 173
7 Equivalence Relations and Partitions 178
{Sums and Products of Partitions 187
4 FUNCTIONS 193
0 Introduction 193
1 Basic Properties of Functions 193
Inductively Defined Functions 199
Partial Functions 201
2 Special Classes of Functions 204
Inverse Functions 209
One-Sided Inverse Functions 213
5 COUNTING AND ALGORITHM ANALYSIS 218
0 Introduction 218
1 Basic Counting Techniques 218
Permutations and Combinations 222 Decision Trees 225
2 Asymptotic Behavior of Functions 232
Some Important Classes of Asymptotic Behavior
3 Recurrence Systems 243
Divide and Conquer Algorithms 248
4 Analysis of Algorithms 258
Searching Algorithms 262 Sorting Algorithms 265
6 INFINITE SETS 275
0 Introduction 275
1 Finite and Infinite Sets 275
2 Countable and Uncountable Sets 279
Comparison of Cardinal Numbers 288
4 Cardinal Arithmetic 295
7 ALGEBRAS 300
0 Introduction 300
1 The Structure of Algebras 301
2 Some Varieties of Algebras 309
Semigroups 309 Monoids 310 Groups 311 Boolean Algebras 312
3 Homomorphisms 315
4 Congruence Relations 322
5 New Algebraic Systems from Old 327
Quotient Algebras 327 Product Algebras 329
APPENDIX: THE PROGRAMMING LANGUAGE 332
ANSWERS TO SFI FP.TFD FXFROISFS 339
BIBLIOGRAPHY 391
INDEX 393