Syntactic characterisation of intrinsic computability

Teoria struktur obliczalnych rozważa pytanie, jak własności obliczalne struktur obliczalnych różnią się w ich kopiach obliczalnych. W tej rozprawie rozważam pojęcie wewnętrznej obliczalności i wewnętrznej rekurencyjnej przeliczalności, które zajmują kluczową pozycję w teorii struktur obliczalnych. Te pojęcia dotyczą relacji, które są obliczalne (albo rekurencyjnie przeliczalne) w każdej obliczalnej kopii struktury. Prezentuję przykłady relacji wewnętrznie obliczalnych. Prezentuję również dowody twierdzeń ukazujących zależność między wewnętrzną obliczalnością a innymi ważnymi pojęciami z zakresu teorii struktur obliczalnych, takimi jak obliczalna stabilność i obliczalna kategoryczność. Głównym rezultatem tej pracy jest rekonstrukcja twierdzenia Asha-Nerode'a ukazującego rozbieżność między wewnętrzną rekurencyjną przeliczalnością a definiowalnością za pomocą pewnej klasy nieskończonych formuł w logice infinitarnej (przy założeniu warunku efektywności). Pokazuję pewne zastosowania tego twierdzenia, w szczególności do przestrzeni liniowych.

Computable structure theory considers the question how computational properties of computable structures differ between their isomorphic copies. In this thesis I consider the notions of intrinsic computability and intrinsic computable enumerability which occupy a key position in computable structure theory. These notions refer to relations which are computable (or computably enumerable) in every computable copy of a structure. I present some examples of instrinsically computable relations. I also present proofs of theorems which establish connection between intrinsic computability and other important notions of computable structure theory such as computable stability and computable categoricity. The main result of this paper is the detailed reconstruction of Ash-Nerode theorem establishing connection between intrinsic computable enumerability (and intrinsic computability) and definitability by a certain class of infinitary formulas in $\mathcal{L}_{\omega_{1},\omega}$ logic (under an effectiveness condition). I show certain applications of this theorem, in particular to vector spaces.