Computable Structure Theory

The computable structure theory is the branch of model theory which deals questions of computability as they apply to model-theoretical structures. In the course different approaches will be considered including the definability in special admissible sets and the definability in the infinite languages.

Topics:

1) Computable structures. The definitions, basic properties and examples. Constructive ordinals. The Kleene’s O.

2) Infinitary languages. The hyperarithmetic hierarchy. The analytical hierarchy. The Pi-1-1 completeness of O.

3) Scott families. Scott Isomorfism Theorem. Scott Families and Rank. Computable infinite languages. The Barweise-Kreisel Compactness Theorem

4) Noncomputable structures. The degree spectra of structures and relations. The Wehner-Slaman structure. Intristically computable sets and relations. Forcing in computability theory.

5) Back-and-forth relations. Standard back-and-forth relations. Ranks. Examples in arithmetic, vector spaces, linear orderings and Boolean algebras.

6) KPU-models and admissible sets. The axioms of KPU. Admissible sets. The Gandy Theorem. Hereditary finite superstructures.

7) Reducibility of structures. The Muchnik and Medvedev reducibility of mass problems of presentability. The Sigma-reducibility. Examples and counterexamples.

8) Jumps of Structures. The definition of jump of a structure. The Jump Inversion Theorem for Sigma-degrees. The least jump property.

C. J. Ash and J. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, vol. 144. Elsevier, Amsterdam etc. 2000.

Yu.L. Ershov. Definability and computability. – New York: Plenum, 1996 (Siberian School of Algebra and Logic)