Characterizing the computable structures: Boolean algebras and linear orders.

摘要

A countable structure (with finite signature) is computable if its universe can be identified with o in such a way as to make the relations and operations computable functions. In this thesis, I study which Boolean algebras and linear orders are computable.; Making use of Ketonen invariants, I study the Boolean algebras of low Ketonen depth, both classically and effectively. Classically, I give an explicit characterization of the depth zero Boolean algebras; provide continuum many examples of depth one, rank o Boolean algebras with range o + 1; and provide continuum many examples of depth o, rank one Boolean algebras. Effectively, I show for sets S ⊆ o + 1 with greatest element, the depth zero Boolean algebras BuS and BvS are computable if and only if S {lcub}o{rcub} is n2n+30 in the Feiner Sigma-hierarchy.; Making use of the existing notion of limitwise monotonic functions and the new notion of limit infimum functions, I characterize which shuffle sums of ordinals below o + 1 have computable copies. Additionally, I show that the notions of limitwise monotonic functions relative to 0' and limit infimum functions coincide.