Computability Theory

The arithmetic hierarchy

Classifying sets by the quantifier complexity of their definitions, Post's theorem linking it to the jump, the classification of index sets, arithmetic definability, and codes for sets.

Intermediate5 lessons≈ 195 min18 questions
Progress0/18 questions answered
StartProgress is saved in this browser.

The Σ⁰ₙ, Π⁰ₙ and Δ⁰ₙ sets and their closure properties; Post's theorem, which identifies the levels of the hierarchy with the sets c.e. or computable in the iterated jumps; the classification of the basic index sets; the equivalence between the arithmetic hierarchy and definability in the language of arithmetic, with Tarski's theorem and the first incompleteness theorem; and the kinds of indices used to describe sets.

Contents

  1. 1

    Σ⁰ₙ and Π⁰ₙ sets

    The arithmetic hierarchy defined by alternations of quantifiers over computable relations; normal forms, closure properties, relativization and many-one reductions.

    1. 1.1 Definition
    2. 1.2 Normal forms
    3. 1.3 Closure properties
    4. 1.4 Relativization and reductions
    5. 1.5 Exercises
    6. 1.6 Notes and references
    35 min
  2. 2

    Post's theorem

    The levels of the arithmetic hierarchy are the sets c.e. or computable in the iterated jumps; the iterated jumps are complete at each level; the hierarchy is strict.

    1. 2.1 One jump for one quantifier
    2. 2.2 Post's theorem
    3. 2.3 Exercises
    4. 2.4 Notes and references
    40 min
  3. 3

    Classifying index sets

    Upper bounds by counting quantifiers, lower bounds by reductions; Fin is Σ⁰₂-complete, Tot and Inf are Π⁰₂-complete, Cof is Σ⁰₃-complete.

    1. 3.1 The method
    2. 3.2 The second level
    3. 3.3 The third level
    4. 3.4 Summary
    5. 3.5 Exercises
    6. 3.6 Notes and references
    45 min
  4. 4

    Arithmetic definability

    The arithmetic sets are the sets definable in the language of arithmetic; Σ₁-definable means c.e.; truth in ℕ is not arithmetic, and the first incompleteness theorem.

    1. 4.1 The language of arithmetic
    2. 4.2 Computations are Σ₁-definable
    3. 4.3 Definable sets are arithmetic
    4. 4.4 Truth is not arithmetic
    5. 4.5 Exercises
    6. 4.6 Notes and references
    40 min
  5. 5

    Codes for sets

    Indices of computable, c.e., finite and low sets; the information each kind of index provides, and fixed point arguments showing what cannot be recovered uniformly.

    1. 5.1 Kinds of indices
    2. 5.2 What cannot be recovered
    3. 5.3 Lowness indices
    4. 5.4 Exercises
    5. 5.5 Notes and references
    35 min