A First Course in Mathematical Logic and Set Theory (Hardcover)

Preface xiii

Acknowledgments xv

List of Symbols xvii

1 Propositional Logic 1

1.1 Symbolic Logic 1

Propositions 2

Propositional Forms 6

Interpreting Propositional Forms 8

Valuations and Truth Tables 11

1.2 Inference 20

Semantics 22

Syntactics 24

1.3 Replacement 32

Semantics 32

Syntactics 35

1.4 Proof Methods 41

Deduction Theorem 41

Direct Proof 46

Indirect Proof 48

1.5 The Three Properties 53

Consistency 53

Soundness 57

Completeness 60

2 FirstOrder

Logic 65

2.1 Languages 65

Predicates 65

Alphabets 69

Terms 72

Formulas 73

2.2 Substitution 77

Terms 77

Free Variables 79

Formulas 80

2.3 Syntactics 87

Quantifier Negation 87

Proofs with Universal Formulas 89

Proofs with Existential Formulas 93

2.4 Proof Methods 98

Universal Proofs 100

Existential Proofs 101

Multiple Quantifiers 103

Counterexamples 104

Direct Proof 105

Existence and Uniqueness 107

Indirect Proof 108

Biconditional Proof 110

Proof of Disunctions 114

Proof by Cases 114

3 Set Theory 119

3.1 Sets and Elements 119

Rosters 120

Famous Sets 121

Abstraction 123

3.2 Set Operations 128

Union and Intersection 128

Set Difference 129

Cartesian Products 132

Order of Operations 134

3.3 Sets within Sets 137

Subsets 137

Equality 139

3.4 Families of Sets 150

Power Set 153

Union and Intersection 154

Disjoint and Pairwise Disjoint 157

4 Relations and Functions 163

4.1 Relations 163

Composition 165

Inverses 167

4.2 Equivalence Relations 170

Equivalence Classes 173

Partitions 175

4.3 Partial Orders 179

Bounds 183

Comparable and Compatible Elements 184

WellOrdered Sets 186

4.4 Functions 192

Equality 197

Composition 198

Restrictions and Extensions 200

Binary Operations 200

4.5 Injections and Surjections 207

Injections 208

Surjections 211

Bijections 214

Order Isomorphims 215

4.6 Images and Inverse Images 220

5 Axiomatic Set Theory 227

5.1 Axioms 227

Equality Axioms 228

Existence and Uniqueness Axioms 229

Construction Axioms 230

Replacement Axioms 231

Axiom of Choice 232

Axiom of Regularity 236

5.2 Natural Numbers 239

Order 241

Recursion 244

Arithmetic 245

5.3 Integers and Rational Numbers 251

Integers 252

Rational Numbers 255

Actual Numbers 258

5.4 Mathematical Induction 259

Combinatorics 263

Euclid?s Lemma 267

5.5 Strong Induction 270

Fibonacci Sequence 271

Unique Factorization 273

5.6 Real Numbers 277

Dedekind Cuts 278

Arithmetic 280

Complex Numbers 283

6 Ordinals and Cardinals 285

6.1 Ordinal Numbers 285

Ordinals 288

Classification 292

BuraliForti and Hartogs 294

Transfinite Recursion 295

6.2 Equinumerosity 300

Order 302

Diagonalization 305

6.3 Cardinal Numbers 309

Finite Sets 310

Countable Sets 312

Alephs 315

6.4 Arithmetic 318

Ordinals 318

Cardinals 324

6.5 Large Cardinals 330

Regular and Singular Cardinals 331

Inaccessible Cardinals 334

7 Models 337

7.1 FirstOrder

Semantics 337

Satisfaction 339

Groups 344

Consequence 350

Coincidence 352

Rings 357

7.2 Substructures 365

Subgroups 367

Subrings 370

Ideals 372

7.3 Homomorphisms 379

Isomorphisms 384

Elementary Equivalence 388

Elementary Substructures 393

7.4 The Three Properties Revisited 399

Consistency 399

Soundness 402

Completeness 404

7.5 Models of Different Cardinalities 414

Peano Arithmetic 415

Compactness Theorem 419

Löwenheim?Skolem Theorems 420

The von Neumann Hierarchy 422

Appendix: Alphabets 433

References 435

Index 441