Definability and Computability

Computability theory is one of the main areas of mathematical logic since the fundamental work of A. Turing, K. Gdel, A. Church, S. Kleene in the 1930`s. In particular, formalization of the notion of computation showed that many mathematical problems are undecidable. The general computability theory allows one to classify problems according to their degrees of undecidability. Ideas of computability theory were successfully applied to algebra and model theory, resulting in many applications. One of the important fields is the theory of computable models which studies the algorithmic complexity of countable models on the basis of classical computability. Descriptive set theory is a part of set theory which studies questions of definability of sets of reals. Results and methods of this theory are closely related to those of classical and generalized computability. Moreover, recent results on the effective theory of cardinalities, based on Wadge reducibility, and new results on definability of equivalence relations make the connections even stronger. Many ideas of descriptive set theory are applied in computable model theory, e.g. for classification of isomorphism and bi-embeddability relations on classes of computable structures. Admissible set theory and generalized computability arose in the 1960s in works of S. Kripke, R. Platek, Y. Moschovakis, R. Montague, J. Barwise, G. Kreisel and G. Sacks. The main goal of this theory is the investigation of computability over structures that are significantly different from the naturals: on the reals, on admissible ordinals and on arbitrary admissible sets with urelements. Admissible set theory may serve as a basic tool in the study of computability over abstract structures. The proposed project addresses the main questions in the mentioned fields, as well as new questions that arise from interaction of ideas and approaches typical for the three directions. We plan to investigate algorithmic properties of model-theoretic and set-theoretic objects via a general approach based on suitable notions of algorithm and computability. Among the topics we study are: 1. computability of structures and complexity of classes of computable models and equivalence relations on such classes; 2. structure and complexity of various natural reducibilities between topological spaces; 3. computability over abstract structures.

Mathematical logic entered the modern era through the work of Kurt Gödel, who established his famous Completeness and Incompleteness Theorems in Vienna in the 1930`s. This project, based at the Kurt Gödel Research Center for Mathematical Logic of the University of Vienna, focuses on definability and computability, two important aspects of Gödel`s work. The topics explored in this project were: computable analysis, the metamathematics of ordinal computability, definable structure theory and feasible computation in set theory.