A First Course in Mathematical Logic and Set Theory

A mathematical introduction to the theory and applications of logic and set theory with an emphasis on writing proofs

Highlighting the applications and notations of basic mathematical concepts within the framework of logic and set theory, A First Course in Mathematical Logic and SetTheory introduces how logic is used to prepare and structure proofs and solve more complex problems.

The book begins with propositional logic, including two-column proofs and truth table applications, followed by first-order logic, which provides the structure for writing mathematical proofs. Set theory is then introduced and serves as the basis for defining relations, functions, numbers, mathematical induction, ordinals, and cardinals. The book concludes with a primer on basic model theory with applications to abstract algebra. A First Course in Mathematical Logic and Set Theory also includes:

• Section exercises designed to show the interactions between topics and reinforce the presented ideas and concepts
• Numerous examples that illustrate theorems and employ basic concepts such as Euclid?s lemma, the Fibonacci sequence, and unique factorization
• Coverage of important theorems including the well-ordering theorem, completeness theorem, compactness theorem, as well as the theorems of Löwenheim?Skolem, Burali-Forti, Hartogs, Cantor?Schröder?Bernstein, and König

An excellent textbook for students studying the foundations of mathematics and mathematical proofs, A First Course in Mathematical Logic and Set Theory is also appropriate for readers preparing for careers in mathematics education or computer science. In addition, the book is ideal for introductory courses on mathematical logic and/or set theory and appropriate for upper-undergraduate transition courses with rigorous mathematical reasoning involving algebra, number theory, or analysis.

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

Löwenheim–Skolem Theorems 415

The von Neumann Hierarchy 417

Appendix: Alphabets 427

References 429

Index 435

Michael L. O'Leary, PhD, is Professor of Mathematics at the College of DuPage in Glen Ellyn, Illinois. He received his doctoral degree in mathematics from the University of California, Irvine in 1994 and is the author of Revolutions of Geometry, also published by Wiley.