Sets, Logic, Computation

by Richard Zach et al.

Read here Read at LibreTextsPDF

Sets, Logic, Computation is an introductory textbook on metalogic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. The audience is undergraduate students with some background in formal logic.

Description from LibreTexts.

Publisher
Open Logic Project
Subjects
Humanities, Philosophy
Licence
CC BY, as LibreTexts states it
Who can read
Teens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. Preface
  7. 1: I- Sets, Relations, Functions
  8. 1.1: Sets
  9. 1.1.1: Extensionality
  10. 1.1.2: Subsets and Power Sets
  11. 1.1.3: Some Important Sets
  12. 1.1.4: Unions and Intersections
  13. 1.1.5: Pairs, Tuples, Cartesian Products
  14. 1.1.6: Russell’s Paradox
  15. 1.1.7: Summary
  16. 1.2: Relations
  17. 1.2.1: Relations as Sets
  18. 1.2.2: Philosophical Reflections
  19. 1.2.3: Special Properties of Relations
  20. 1.2.4: Equivalence Relations
  21. 1.2.5: Orders
  22. 1.2.6: Graphs
  23. 1.2.7: Operations on Relations
  24. 1.2.8: Summary
  25. 1.3: Functions
  26. 1.3.1: Basics
  27. 1.3.2: Kinds of Functions
  28. 1.3.3: Functions as Relations
  29. 1.3.4: Inverses of Functions
  30. 1.3.5: Composition of Functions
  31. 1.3.6: Isomorphism
  32. 1.3.7: Partial Functions
  33. 1.3.8: Summary
  34. 1.4: The Size of Sets
  35. 1.4.1: Introduction
  36. 1.4.2: Enumerations and Countable Sets
  37. 1.4.3: Cantor’s Zig-Zag Method
  38. 1.4.4: Pairing Functions and Codes
  39. 1.4.5: An Alternative Pairing Function
  40. 1.4.6: Uncountable Sets
  41. 1.4.7: Reduction
  42. 1.4.8: Equinumerosity
  43. 1.4.9: Sets of Different Sizes, and Cantor’s Theorem
  44. 1.4.10: The Notion of Size, and Schröder-Bernstein
  45. 1.4.11: Summary
  46. 2: II- First-order Logic
  47. 2.1: Syntax and Semantics
  48. 2.1.1: Introduction
  49. 2.1.2: First-Order Languages
  50. 2.1.3: Terms and Formulas
  51. 2.1.4: Unique Readability
  52. 2.1.5: Main operator of a Formula
  53. 2.1.6: Subformulas
  54. 2.1.7: Free Variables and Sentences
  55. 2.1.8: Substitution
  56. 2.1.9: Structures for First-order Languages
  57. 2.1.10: Covered Structures for First-order Languages
  58. 2.1.11: Satisfaction of a Formula in a Structure
  59. 2.1.12: Variable Assignments
  60. 2.1.13: Extensionality
  61. 2.1.14: Semantic Notions
  62. 2.1.15: Summary
  63. 2.2: Theories and Their Models
  64. 2.2.1: Introduction
  65. 2.2.2: Expressing Properties of Structures
  66. 2.2.3: Examples of First-Order Theories
  67. 2.2.4: Expressing Relations in a Structure
  68. 2.2.5: The Theory of Sets
  69. 2.2.6: Expressing the Size of Structures
  70. 2.2.7: Summary
  71. 2.3: Derivation Systems
  72. 2.3.1: Introduction
  73. 2.3.2: The Sequent Calculus
  74. 2.3.3: Natural Deduction
  75. 2.3.4: Tableaux
  76. 2.3.5: Axiomatic Derivations
  77. 2.4: The Sequent Calculus
  78. 2.4.1: Rules and Derivations
  79. 2.4.2: Propositional Rules
  80. 2.4.3: Quantifier Rules
  81. 2.4.4: Structural Rules
  82. 2.4.5: Derivations
  83. 2.4.6: Examples of Derivations
  84. 2.4.7: Derivations with Quantifiers
  85. 2.4.8: Proof-Theoretic Notions
  86. 2.4.9: Derivability and Consistency
  87. 2.4.10: Derivability and the Propositional Connectives
  88. 2.4.11: Derivability and the Quantifiers
  89. 2.4.12: Soundness
  90. 2.4.13: Derivations with Identity predicate
  91. 2.4.14: Soundness with Identity predicate
  92. 2.4.15: Summary
  93. 2.5: Natural Deduction
  94. 2.5.1: Rules and Derivations
  95. 2.5.2: Propositional Rules
  96. 2.5.3: Quantifier Rules
  97. 2.5.4: Derivations
  98. 2.5.5: Examples of Derivations
  99. 2.5.6: Derivations with Quantifiers
  100. 2.5.7: Proof-Theoretic Notions
  101. 2.5.8: Derivability and Consistency
  102. 2.5.9: Derivability and the Propositional Connectives
  103. 2.5.10: Derivability and the Quantifiers
  104. 2.5.11: Soundness
  105. 2.5.12: Derivations with Identity predicate
  106. 2.5.13: Soundness with Identity predicate
  107. 2.5.14: Summary
  108. 2.6: The Completeness Theorem
  109. 2.6.1: Introduction
  110. 2.6.2: Outline of the Proof
  111. 2.6.3: Complete Consistent Sets of Sentences
  112. 2.6.4: Henkin Expansion
  113. 2.6.5: Lindenbaum’s Lemma
  114. 2.6.6: Construction of a Model
  115. 2.6.7: Identity
  116. 2.6.8: The Completeness Theorem
  117. 2.6.9: The Compactness Theorem
  118. 2.6.10: A Direct Proof of the Compactness Theorem
  119. 2.6.11: The Löwenheim-Skolem Theorem
  120. 2.6.12: Summary
  121. 2.7: Beyond First-order Logic
  122. 2.7.1: Overview
  123. 2.7.2: Many-Sorted Logic
  124. 2.7.3: Second-Order logic
  125. 2.7.4: Higher-Order logic
  126. 2.7.5: Intuitionistic Logic
  127. 2.7.6: Modal Logics
  128. 2.7.7: Other Logics
  129. 3: III- Turing Machines
  130. 3.1: Turing Machine Computations
  131. 3.1.1: Introduction
  132. 3.1.2: Representing Turing Machines
  133. 3.1.3: Turing Machines
  134. 3.1.4: Configurations and Computations
  135. 3.1.5: Unary Representation of Numbers
  136. 3.1.6: Halting States
  137. 3.1.7: Combining Turing Machines
  138. 3.1.8: Variants of Turing Machines
  139. 3.1.9: The Church-Turing Thesis
  140. 3.1.10: Summary
  141. 3.2: Undecidability
  142. 3.2.1: Introduction
  143. 3.2.2: Enumerating Turing Machines
  144. 3.2.3: The Halting Problem
  145. 3.2.4: The Decision Problem
  146. 3.2.5: Representing Turing Machines
  147. 3.2.6: Verifying the Representation
  148. 3.2.7: The Decision Problem is Unsolvable
  149. 3.2.8: Summary
  150. Back Matter
  151. Index
  152. Glossary
  153. Appendix A: Proofs
  154. 1.1: A.1- Introduction
  155. 1.2: A.2- Starting a Proof
  156. 1.3: A.3- Using Definitions
  157. 1.4: A.4- Inference Patterns
  158. 1.5: A.5- An Example
  159. 1.6: A.6- Another Example
  160. 1.7: A.7- Proof by Contradiction
  161. 1.8: A.8- Reading Proofs
  162. 1.9: A.9- I Can’t Do It!
  163. 1.10: A.10- Other Resources
  164. Appendix B: Induction
  165. 1.1: B.1- Introduction
  166. 1.2: B.2- Induction on ℕ
  167. 1.3: B.3- Strong Induction
  168. 1.4: B.4- Inductive Definitions
  169. 1.5: B.5- Structural Induction
  170. 1.6: B.6- Relations and Functions
  171. Appendix C: Biographies
  172. 1.1: C.1- Georg Cantor
  173. 1.2: C.2- Alonzo Church
  174. 1.3: C.3- Gerhard Gentzen
  175. 1.4: C.4- Kurt Gödel
  176. 1.5: C.5- Emmy Noether
  177. 1.6: C.6- Bertrand Russell
  178. 1.7: C.7- Alfred Tarski
  179. 1.8: C.8- Alan Turing
  180. 1.9: C.9- Ernst Zermelo
  181. Bibliography
  182. About the Open Logic Project
  183. Detailed Licensing