Antonio Montalbán

Knight and Stob proved that every low 4 _4 Boolean algebra is 0 ( 6 ) 0^{(6)} -isomorphic to a computable one. Furthermore, for n = 1 , 2 , 3 , 4 n=1,2,3,4 , every low n _n Boolean algebra is 0 ( n + 2 ) 0^{(n+2)} -isomorphic to a computable one. We show that this is not true for n = 5 n=5 : there is a low 5 _5 Boolean algebra that is not 0 ( 7 ) 0^{(7)} -isomorphic to any computable Boolean algebra. It is worth remarking that, because of the machinery developed, the proof uses at most a 0 ′ ′ 0^{\prime \prime } -priority argument. The technique used to construct this Boolean algebra is new and might be useful in other applications, such as to solve the low n _n Boolean algebra problem either positively or negatively.

Although classical computable model theory is most naturally concerned with countable domains, several methods – some old, some new – have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. Furthermore, uncountable computable model theory is still in an early stage of development, and, in particular, there has been relatively little work on connecting and comparing the various available approaches. Two Effective Mathematics of the Uncountable workshops were held at the CUNY Graduate Center in New York on August 18–22, 2008 and August 17–21, 2009, organized by Noam Greenberg, Joel Hamkins, Denis Hirschfeldt, and Russell Miller, with support from a Templeton Foundation “Exploring the Infinite” program grant. The aim of these workshops was to introduce a variety of approaches to uncountable computable model theory to researchers and students in computability theory and related fields, and to encourage collaboration between those who have developed and studied different facets of the effective content of uncountable mathematics. Speaking at the EMU workshops were researchers with a wide range of backgrounds and motivations: Nate Ackerman, Wesley Calvert, Samuel Coskey, Noam Greenberg, Joel Hamkins, Denis Hirschfeldt, Julia Knight, Peter Koepke, David Linetsky, Robert Lubarsky, Russell Miller, Antonio Montalbán, Ansten Mørch Klev, Kerry Ojakian, Gerald Sacks, Richard Shore, Alexei Stukachev, and Philip Welch.

Classical computable model theory is most naturally concerned with countable domains. There are, however, several methods – some old, some new – that have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. This book contains introductions to eight major approaches to computable uncountable mathematics: descriptive set theory; infinite time Turing machines; Blum-Shub-Smale computability; Sigma-definability; computability theory on admissible ordinals; E-recursion theory; local computability; and uncountable reverse mathematics. This book provides an authoritative and multifaceted introduction to this exciting new area of research that is still in its early stages. It is ideal as both an introductory text for graduate and advanced undergraduate students and a source of interesting new approaches for researchers in computability theory and related areas.

Assuming that 0^# exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure such that where is the set of Turing degrees which compute a copy of More interesting than the result itself is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full “nth-order arithmetic for all n, cannot prove the existence of such a structure.

Toward establishing the decidability of the two-quantifier theory of the Δ 2 0 \Delta ^0_2 Turing degrees with join, we study extensions of embeddings of upper-semi-lattices into the initial segments of Turing degrees determined by computably enumerable sets, in particular, the degree of the halting set 0 ′ \boldsymbol {0}’ . We obtain a good deal of sufficient and necessary conditions.

We propose a framework to study the computational complexity of definable relations on a structure. Many of the notions we discuss are old, but the viewpoint is new. We believe that all the pieces fit together smoothly under this new point of view. We also survey related results in the area. More concretely, we study the space of sequences of relations over a given structure. On this space, we develop notions of c.e.-ness, reducibility, join and jump. These notions are equivalent to other notions studied in other settings. We explain the equivalences and differences between these notions.

We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all equivalence relations on hyperarithmetical subsets of ω.