Thư viện Trường Đại học Phú Xuân
|
PXU E-LIB
Đăng nhập
Sets, Logic, Computation

Nguồn ngoài

Sets, Logic, Computation

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.

PhilosophyHumanities
Tác giả
Richard Zach et al.
Nhà xuất bản
Open Logic Project
Nguồn
LibreTexts
Giấy phép
CC BY
Ngôn ngữ
EN
Đọc trực tuyến Tải PDF (nguồn mở)
Mục lục· 143 mục
  1. 01: I- Sets Relations Functions
  2. 1.01: Sets
  3. 1.1.01: Extensionality
  4. 1.1.02: Subsets and Power Sets
  5. 1.1.03: Some Important Sets
  6. 1.1.04: Unions and Intersections
  7. 1.1.05: Pairs Tuples Cartesian Products
  8. 1.1.06: Russells Paradox
  9. 1.1.07: Summary
  10. 1.02: Relations
  11. 1.2.01: Relations as Sets
  12. 1.2.02: Philosophical Reflections
  13. 1.2.03: Special Properties of Relations
  14. 1.2.04: Equivalence Relations
  15. 1.2.05: Orders
  16. 1.2.06: Graphs
  17. 1.2.07: Operations on Relations
  18. 1.2.08: Summary
  19. 1.03: Functions
  20. 1.3.01: Basics
  21. 1.3.02: Kinds of Functions
  22. 1.3.03: Functions as Relations
  23. 1.3.04: Inverses of Functions
  24. 1.3.05: Composition of Functions
  25. 1.3.06: Isomorphism
  26. 1.3.07: Partial Functions
  27. 1.3.08: Summary
  28. 1.04: The Size of Sets
  29. 1.4.01: Introduction
  30. 1.4.02: Enumerations and Countable Sets
  31. 1.4.03: Cantors Zig-Zag Method
  32. 1.4.04: Pairing Functions and Codes
  33. 1.4.05: An Alternative Pairing Function
  34. 1.4.06: Uncountable Sets
  35. 1.4.07: Reduction
  36. 1.4.08: Equinumerosity
  37. 1.4.09: Sets of Different Sizes and Cantors Theorem
  38. 1.4.10: The Notion of Size and Schroder-Bernstein
  39. 1.4.11: Summary
  40. 02: II- First-order Logic
  41. 2.01: Syntax and Semantics
  42. 2.1.01: Introduction
  43. 2.1.02: First-Order Languages
  44. 2.1.03: Terms and Formulas
  45. 2.1.04: Unique Readability
  46. 2.1.05: Main operator of a Formula
  47. 2.1.06: Subformulas
  48. 2.1.07: Free Variables and Sentences
  49. 2.1.08: Substitution
  50. 2.1.09: Structures for First-order Languages
  51. 2.1.10: Covered Structures for First-order Languages
  52. 2.1.11: Satisfaction of a Formula in a Structure
  53. 2.1.12: Variable Assignments
  54. 2.1.13: Extensionality
  55. 2.1.14: Semantic Notions
  56. 2.1.15: Summary
  57. 2.02: Theories and Their Models
  58. 2.2.01: Introduction
  59. 2.2.02: Expressing Properties of Structures
  60. 2.2.03: Examples of First-Order Theories
  61. 2.2.04: Expressing Relations in a Structure
  62. 2.2.05: The Theory of Sets
  63. 2.2.06: Expressing the Size of Structures
  64. 2.2.07: Summary
  65. 2.03: Derivation Systems
  66. 2.3.01: Introduction
  67. 2.3.02: The Sequent Calculus
  68. 2.3.03: Natural Deduction
  69. 2.3.04: Tableaux
  70. 2.3.05: Axiomatic Derivations
  71. 2.04: The Sequent Calculus
  72. 2.4.01: Rules and Derivations
  73. 2.4.02: Propositional Rules
  74. 2.4.03: Quantifier Rules
  75. 2.4.04: Structural Rules
  76. 2.4.05: Derivations
  77. 2.4.06: Examples of Derivations
  78. 2.4.07: Derivations with Quantifiers
  79. 2.4.08: Proof-Theoretic Notions
  80. 2.4.09: Derivability and Consistency
  81. 2.4.10: Derivability and the Propositional Connectives
  82. 2.4.11: Derivability and the Quantifiers
  83. 2.4.12: Soundness
  84. 2.4.13: Derivations with Identity predicate
  85. 2.4.14: Soundness with Identity predicate
  86. 2.4.15: Summary
  87. 2.05: Natural Deduction
  88. 2.5.01: Rules and Derivations
  89. 2.5.02: Propositional Rules
  90. 2.5.03: Quantifier Rules
  91. 2.5.04: Derivations
  92. 2.5.05: Examples of Derivations
  93. 2.5.06: Derivations with Quantifiers
  94. 2.5.07: Proof-Theoretic Notions
  95. 2.5.08: Derivability and Consistency
  96. 2.5.09: Derivability and the Propositional Connectives
  97. 2.5.10: Derivability and the Quantifiers
  98. 2.5.11: Soundness
  99. 2.5.12: Derivations with Identity predicate
  100. 2.5.13: Soundness with Identity predicate
  101. 2.5.14: Summary
  102. 2.06: The Completeness Theorem
  103. 2.6.01: Introduction
  104. 2.6.02: Outline of the Proof
  105. 2.6.03: Complete Consistent Sets of Sentences
  106. 2.6.04: Henkin Expansion
  107. 2.6.05: Lindenbaums Lemma
  108. 2.6.06: Construction of a Model
  109. 2.6.07: Identity
  110. 2.6.08: The Completeness Theorem
  111. 2.6.09: The Compactness Theorem
  112. 2.6.10: A Direct Proof of the Compactness Theorem
  113. 2.6.11: The Lowenheim-Skolem Theorem
  114. 2.6.12: Summary
  115. 2.07: Beyond First-order Logic
  116. 2.7.01: Overview
  117. 2.7.02: Many-Sorted Logic
  118. 2.7.03: Second-Order logic
  119. 2.7.04: Higher-Order logic
  120. 2.7.05: Intuitionistic Logic
  121. 2.7.06: Modal Logics
  122. 2.7.07: Other Logics
  123. 03: III- Turing Machines
  124. 3.01: Turing Machine Computations
  125. 3.1.01: Introduction
  126. 3.1.02: Representing Turing Machines
  127. 3.1.03: Turing Machines
  128. 3.1.04: Configurations and Computations
  129. 3.1.05: Unary Representation of Numbers
  130. 3.1.06: Halting States
  131. 3.1.07: Combining Turing Machines
  132. 3.1.08: Variants of Turing Machines
  133. 3.1.09: The Church-Turing Thesis
  134. 3.1.10: Summary
  135. 3.02: Undecidability
  136. 3.2.01: Introduction
  137. 3.2.02: Enumerating Turing Machines
  138. 3.2.03: The Halting Problem
  139. 3.2.04: The Decision Problem
  140. 3.2.05: Representing Turing Machines
  141. 3.2.06: Verifying the Representation
  142. 3.2.07: The Decision Problem is Unsolvable
  143. 3.2.08: Summary