Preface xiii
Acknowledgments xv
List of Symbols xvii
1 Propositional Logic 1
1.1 Symbolic Logic 1
Propositions 2
Propositional Forms 5
Interpreting Propositional Forms 7
Valuations and Truth Tables 10
1.2 Inference 19
Semantics 21
Syntactics 23
1.3 Replacement 31
Semantics 31
Syntactics 34
1.4 Proof Methods 40
Deduction Theorem 40
Direct Proof 44
Indirect Proof 47
1.5 The Three Properties 51
Consistency 51
Soundness 55
Completeness 58
2 First-Order Logic 63
2.1 Languages 63
Predicates 63
Alphabets 67
Terms 70
Formulas 71
2.2 Substitution 75
Terms 75
Free Variables 76
Formulas 78
2.3 Syntactics 85
Quantifier Negation 85
Proofs with Universal Formulas 87
Proofs with Existential Formulas 90
2.4 Proof Methods 96
Universal Proofs 97
Existential Proofs 99
Multiple Quantifiers 100
Counterexamples 102
Direct Proof 103
Existence and Uniqueness 104
Indirect Proof 105
Biconditional Proof 107
Proof of Disunctions 111
Proof by Cases 112
3 Set Theory 117
3.1 Sets and Elements 117
Rosters 118
Famous Sets 119
Abstraction 121
3.2 Set Operations 126
Union and Intersection 126
Set Difference 127
Cartesian Products 130
Order of Operations 132
3.3 Sets within Sets 135
Subsets 135
Equality 137
3.4 Families of Sets 148
Power Set 151
Union and Intersection 151
Disjoint and Pairwise Disjoint 155
4 Relations and Functions 161
4.1 Relations 161
Composition 163
Inverses 165
4.2 Equivalence Relations 168
Equivalence Classes 171
Partitions 172
4.3 Partial Orders 177
Bounds 180
Comparable and Compatible Elements 181
Well-Ordered
Sets 183
4.4 Functions 189
Equality 194
Composition 195
Restrictions and Extensions 196
Binary Operations 197
4.5 Injections and Surjections 203
Injections 205
Surjections 208
Bijections 211
Order Isomorphims 212
4.6 Images and Inverse Images 216
5 Axiomatic Set Theory 225
5.1 Axioms 225
Equality Axioms 226
Existence and Uniqueness Axioms 227
Construction Axioms 228
Replacement Axioms 229
Axiom of Choice 230
Axiom of Regularity 234
5.2 Natural Numbers 237
Order 239
Recursion 242
Arithmetic 243
5.3 Integers and Rational Numbers 249
Integers 250
Rational Numbers 253
Actual Numbers 256
5.4 Mathematical Induction 257
Combinatorics 260
Euclid’s Lemma 264
5.5 Strong Induction 268
Fibonacci Sequence 268
Unique Factorization 271
5.6 Real Numbers 274
Dedekind Cuts 275
Arithmetic 278
Complex Numbers 280
6 Ordinals and Cardinals 283
6.1 Ordinal Numbers 283
Ordinals 286
Classification 290
BuraliForti and Hartogs 292
Transfinite Recursion 293
6.2 Equinumerosity 298
Order 300
Diagonalization 303
6.3 Cardinal Numbers 307
Finite Sets 308
Countable Sets 310
Alephs 313
6.4 Arithmetic 316
Ordinals 316
Cardinals 322
6.5 Large Cardinals 327
Regular and Singular Cardinals 328
Inaccessible Cardinals 331
7 Models 333
7.1 First-Order Semantics 333
Satisfaction 335
Groups 340
Consequence 346
Coincidence 348
Rings 353
7.2 Substructures 361
Subgroups 363
Subrings 366
Ideals 368
7.3 Homomorphisms 374
Isomorphisms 380
Elementary Equivalence 384
Elementary Substructures 388
7.4 The Three Properties Revisited 394
Consistency 394
Soundness 397
Completeness 399
7.5 Models of Different Cardinalities 409
Peano Arithmetic 410
Compactness Theorem 414
Lowenheim–Skolem Theorems 415
The von Neumann Hierarchy 417
Appendix: Alphabets 427
References 429
Index 435
