A First Course in Mathematical Logic and Set Theory

ISBN-13: 9780470905883 / Angielski / Twarda / 2015 / 464 str.

Michael O'Leary

Opis

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 Set Theory 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 LOwenheim-Skolem, Burali-Forti, Hartogs, Cantor-SchrOder-Bernstein, and KOnig

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.

Spis treści

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

O autorze

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.

Blurb

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 Set Theory 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. This is 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 and Forti, Hartog, Cantor–Schröeder–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 level transition courses with rigorous mathematical reasoning involving algebra, number theory, or analysis.

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.