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

Michael L. O'Leary (Autor)

eBook Download: PDF

2015
John Wiley & Sons (Verlag)
978-1-118-54801-1 (ISBN)

Infos

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 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.

 

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.

---

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 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.

Inhalt

Cover 1
Title Page 5
Copyright 6
Dedication 7
Contents 9
Preface 15
Acknowledgments 17
List of Symbols 19
Chapter 1 Propositional Logic???????????????????????????????????????????????????????????????????????? 23
1.1 Symbolic Logic?????????????????????????????????????????????????? 23
Propositions?????????????????????????????????????? 24
Propositional Forms???????????????????????????????????????????????????? 27
Interpreting Propositional Forms?????????????????????????????????????????????????????????????????????????????? 29
Valuations and Truth Tables???????????????????????????????????????????????????????????????????? 32
1.2 Inference???????????????????????????????????????? 41
Semantics???????????????????????????????? 43
Syntactics?????????????????????????????????? 45
1.3 Replacement???????????????????????????????????????????? 53
Semantics???????????????????????????????? 53
Syntactics?????????????????????????????????? 56
1.4 Proof Methods???????????????????????????????????????????????? 62
Deduction Theorem???????????????????????????????????????????????? 62
Direct Proof?????????????????????????????????????? 66
Indirect Proof?????????????????????????????????????????? 69
1.5 The Three Properties?????????????????????????????????????????????????????????????? 73
Consistency???????????????????????????????????? 73
Soundness???????????????????????????????? 77
Completeness?????????????????????????????????????? 80
Chapter 2 First-Order Logic???????????????????????????????????????????????????????????????????? 85
2.1 Languages???????????????????????????????????????? 85
Predicates?????????????????????????????????? 85
Alphabets???????????????????????????????? 89
Terms???????????????????????? 92
Formulas?????????????????????????????? 93
2.2 Substitution?????????????????????????????????????????????? 97
Terms???????????????????????? 97
Free Variables?????????????????????????????????????????? 98
Formulas?????????????????????????????? 100
2.3 Syntactics?????????????????????????????????????????? 107
Quantifier Negation???????????????????????????????????????????????????? 107
Proofs with Universal Formulas?????????????????????????????????????????????????????????????????????????? 109
Proofs with Existential Formulas?????????????????????????????????????????????????????????????????????????????? 112
2.4 Proof Methods???????????????????????????????????????????????? 118
Universal Proofs?????????????????????????????????????????????? 119
Existential Proofs?????????????????????????????????????????????????? 121
Multiple Quantifiers?????????????????????????????????????????????????????? 122
Counterexamples???????????????????????????????????????????? 124
Direct Proof?????????????????????????????????????? 125
Existence and Uniqueness?????????????????????????????????????????????????????????????? 126
Indirect Proof?????????????????????????????????????????? 127
Biconditional Proof???????????????????????????????????????????????????? 129
Proof of Disunctions?????????????????????????????????????????????????????? 133
Proof by Cases?????????????????????????????????????????? 134
Chapter 3 Set Theory?????????????????????????????????????????????????????? 139
3.1 Sets and Elements???????????????????????????????????????????????????????? 139
Rosters???????????????????????????? 140
Famous Sets???????????????????????????????????? 141
Abstraction???????????????????????????????????? 143
3.2 Set Operations?????????????????????????????????????????????????? 148
Union and Intersection?????????????????????????????????????????????????????????? 148
Set Difference?????????????????????????????????????????? 149
Cartesian Products?????????????????????????????????????????????????? 152
Order of Operations???????????????????????????????????????????????????? 154
3.3 Sets within Sets?????????????????????????????????????????????????????? 157
Subsets???????????????????????????? 157
Equality?????????????????????????????? 159
3.4 Families of Sets?????????????????????????????????????????????????????? 170
Power Set???????????????????????????????? 173
Union and Intersection?????????????????????????????????????????????????????????? 173
Disjoint and Pairwise Disjoint?????????????????????????????????????????????????????????????????????????? 177
Chapter 4 Relations and Functions???????????????????????????????????????????????????????????????????????????????? 183
4.1 Relations???????????????????????????????????????? 183
Composition???????????????????????????????????? 185
Inverses?????????????????????????????? 187
4.2 Equivalence Relations???????????????????????????????????????????????????????????????? 190
Equivalence Classes???????????????????????????????????????????????????? 193
Partitions?????????????????????????????????? 194
4.3 Partial Orders?????????????????????????????????????????????????? 199
Bounds?????????????????????????? 202
Comparable and Compatible Elements?????????????????????????????????????????????????????????????????????????????????? 203
Well-Ordered Sets???????????????????????????????????????????????? 205
4.4 Functions???????????????????????????????????????? 211
Equality?????????????????????????????? 216
Composition???????????????????????????????????? 217
Restrictions and Extensions???????????????????????????????????????????????????????????????????? 218
Binary Operations???????????????????????????????????????????????? 219
4.5 Injections and Surjections?????????????????????????????????????????????????????????????????????????? 225
Injections?????????????????????????????????? 227
Surjections???????????????????????????????????? 230
Bijections?????????????????????????????????? 233
Order Isomorphims???????????????????????????????????????????????? 234
4.6 Images and Inverse Images???????????????????????????????????????????????????????????????????????? 238
Chapter 5 Axiomatic Set Theory?????????????????????????????????????????????????????????????????????????? 247
5.1 Axioms?????????????????????????????????? 247
Equality Axioms???????????????????????????????????????????? 248
Existence and Uniqueness Axioms???????????????????????????????????????????????????????????????????????????? 249
Construction Axioms???????????????????????????????????????????????????? 250
Replacement Axioms?????????????????????????????????????????????????? 251
Axiom of Choice???????????????????????????????????????????? 252
Axiom of Regularity???????????????????????????????????????????????????? 256
5.2 Natural Numbers???????????????????????????????????????????????????? 259
Order???????????????????????? 261
Recursion???????????????????????????????? 264
Arithmetic?????????????????????????????????? 265
5.3 Integers and Rational Numbers???????????????????????????????????????????????????????????????????????????????? 271
Integers?????????????????????????????? 272
Rational Numbers?????????????????????????????????????????????? 275
Actual Numbers?????????????????????????????????????????? 278
5.4 Mathematical Induction?????????????????????????????????????????????????????????????????? 279
Combinatorics???????????????????????????????????????? 282
Euclid's Lemma?????????????????????????????????????????? 286
5.5 Strong Induction?????????????????????????????????????????????????????? 290
Fibonacci Sequence?????????????????????????????????????????????????? 290
Unique Factorization?????????????????????????????????????????????????????? 293
5.6 Real Numbers?????????????????????????????????????????????? 296
Dedekind Cuts???????????????????????????????????????? 297
Arithmetic?????????????????????????????????? 300
Complex Numbers???????????????????????????????????????????? 302
Chapter 6 Ordinals and Cardinals?????????????????????????????????????????????????????????????????????????????? 305
6.1 Ordinal Numbers???????????????????????????????????????????????????? 305
Ordinals?????????????????????????????? 308
Classification?????????????????????????????????????????? 312
Burali-Forti and Hartogs?????????????????????????????????????????????????????????????? 314
Transfinite Recursion???????????????????????????????????????????????????????? 315
6.2 Equinumerosity?????????????????????????????????????????????????? 320
Order???????????????????????? 322
Diagonalization???????????????????????????????????????????? 325
6.3 Cardinal Numbers?????????????????????????????????????????????????????? 329
Finite Sets???????????????????????????????????? 330
Countable Sets?????????????????????????????????????????? 332
Alephs?????????????????????????? 335
6.4 Arithmetic?????????????????????????????????????????? 338
Ordinals?????????????????????????????? 338
Cardinals???????????????????????????????? 344
6.5 Large Cardinals???????????????????????????????????????????????????? 349
Regular and Singular Cardinals?????????????????????????????????????????????????????????????????????????? 350
Inaccessible Cardinals?????????????????????????????????????????????????????????? 353
Chapter 7 Models?????????????????????????????????????????????? 355
7.1 First-Order Semantics???????????????????????????????????????????????????????????????? 355
Satisfaction?????????????????????????????????????? 357
Groups?????????????????????????? 362
Consequence???????????????????????????????????? 368
Coincidence???????????????????????????????????? 370
Rings???????????????????????? 375
7.2 Substructures???????????????????????????????????????????????? 383
Subgroups???????????????????????????????? 385
Subrings?????????????????????????????? 388
Ideals?????????????????????????? 390
7.3 Homomorphisms???????????????????????????????????????????????? 396
Isomorphisms?????????????????????????????????????? 402
Elementary Equivalence?????????????????????????????????????????????????????????? 406
Elementary Substructures?????????????????????????????????????????????????????????????? 410
7.4 The Three Properties Revisited?????????????????????????????????????????????????????????????????????????????????? 416
Consistency???????????????????????????????????? 416
Soundness???????????????????????????????? 419
Completeness?????????????????????????????????????? 421
7.5 Models of Different Cardinalities???????????????????????????????????????????????????????????????????????????????????????? 431
Peano Arithmetic?????????????????????????????????????????????? 432
Compactness Theorem???????????????????????????????????????????????????? 436
Löwenheim-Skolem Theorems 437
The von Neumann Hierarchy???????????????????????????????????????????????????????????????? 439
Appendix: Alphabets???????????????????????????????????????????????????? 449
References?????????????????????????????????? 451
Index???????????????????????? 457
EULA 466

Produkt-Details

• Erscheint lt. Verlag: 14.9.2015
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Technik
• Schlagworte: abstract algebra • cardinals • Discrete Mathematics • Diskrete Mathematik • First-Order Logic • Functions • group theory • Logic • Logic & Foundations • Logik • Logik u. Grundlagen der Mathematik • <p>Mathematics • Mathematical Induction • Mathematics • Mathematik • Mathematische Logik • model Theory • Number Theory • ordinals</p> • Philosophical Logic • Philosophie • Philosophische Logik • Philosophy • Predicate logic • propositional logic • Relations • set theory
• ISBN-10: 1-118-54801-9 / 1118548019
• ISBN-13: 978-1-118-54801-1 / 9781118548011