© Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Contents

• What's this?

• Chapter 1 : Course background
  • Terminology and notation
  • Natural numbers, induction and recursion
  • Finite sets
  • Countable sets
  • Uncountable sets
  • Equivalence relations
• Exercises for Chapter 1
• Chapter 2 : Propositional logic
  • Syntax
  • Semantics
  • Truth tables
  • A deduction system
  • Deduction vs. truth
  • A proof system
• Exercises for Chapter 2
• Chapter 3 : First-order logic
  • Syntax
  • Structures
  • Semantics
  • Tautologies
  • Basic semantic principles
  • A deduction system
  • Low hanging fruit
  • Gödel completeness theorem
• Exercises for Chapter 3
• Chapter 4 : Model theory
  • Downward Löwenheim-Skolem
  • Upward Löwenheim-Skolem
  • Dense linear orderings
  • Nonstandard analysis
  • Universal theories
  • Chains of structures
  • Ultraproducts
• Exercises for Chapter 4
• Chapter 5 : Arithmetic
  • Theories of arithmetic
  • Nonstandard models of arithmetic via compactness
  • Nonstandard models of arithmetic via ultrapowers
  • Arithmetic definability hierarchy
  • True existential sentences are theorems of Robinson Arithmetic
  • Coding tuples of natural numbers
  • Quantifiers and coding
  • Representable functions
• Exercises for Chapter 5
• Chapter 6 : Incompleteness
• Universal relations
• Self-reference
• Peano Arithmetic is incomplete
• The incompleteness theorem
• The second incompleteness theorem
• Additional results
• Exercises for Chapter 6
• Selection of related reading