
13Sergei S. Goncharov. Countable Boolean algebras and decidability. English translation of Schetnye bulevy algebry i razreshimost′. Siberian school of algebra and logic. Consultants Bureau, New York, London, and Moscow, 1997, xii + 318 pp (review)Journal of Symbolic Logic 63 (3): 11881190. 1998.

5Computabilitytheoretic categoricity and Scott familiesAnnals of Pure and Applied Logic 170 (6): 699717. 2019.

Downey, R., Fiiredi, Z., Jockusch Jr., CG and Ruhel, LAAnnals of Pure and Applied Logic 93 263. 1998.

Belegradek, O., Verbovskiy, V. and Wagner, FO, CosetAnnals of Pure and Applied Logic 121 287. 2003.

12Degree spectra of the successor relation of computable linear orderingsArchive for Mathematical Logic 48 (1): 713. 2009.We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees

10Uncountable degree spectraAnnals of Pure and Applied Logic 54 (3): 255263. 1991.We consider a recursive model and an additional recursive relation R on its domain, such that there are uncountably many different images of R under isomorphisms from to some recursive model isomorphic to . We study properties of the set of Turing degrees of all these isomorphic images of R on the domain of

27Bounding Homogeneous ModelsJournal of Symbolic Logic 72 (1). 2007.A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a ddecidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a single CD theory T such that every homogene…Read more

2Review: Sergei S. Goncharov, Countable Boolean Algebras and Decidability (review)Journal of Symbolic Logic 63 (3): 11881190. 1998.

3Ash C. J. and Knight J.. Computable structures and the hyperarithmetical hierarchy. Studies in logic and the foundations of mathematics, vol. 144. Elsevier, Amsterdam etc. 2000, xv + 346 pp (review)Bulletin of Symbolic Logic 7 (3): 383385. 2001.

9Dependence relations in computably rigid computable vector spacesAnnals of Pure and Applied Logic 132 (1): 97108. 2005.We construct a computable vector space with the trivial computable automorphism group, but with the dependence relations as complicated as possible, measured by their Turing degrees. As a corollary, we answer a question asked by A.S. Morozov in [Rigid constructive modules, Algebra and Logic, 28 570–583 ; 379–387 ]

7

20Turing degrees of certain isomorphic images of computable relationsAnnals of Pure and Applied Logic 93 (13): 103113. 1998.A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to contain every Turing degree. These conditions imply that if every Turing degre…Read more

201Frequency computations and the cardinality theoremJournal of Symbolic Logic 57 (2): 682687. 1992.

9Partial automorphism semigroupsAnnals of Pure and Applied Logic 156 (2): 245258. 2008.We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism of the subsemigroups yields isomorphism of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a c…Read more

152005–06 Winter Meeting of the Association for Symbolic LogicBulletin of Symbolic Logic 12 (4): 613624. 2006.

9Effective categoricity of Abelian p groupsAnnals of Pure and Applied Logic 159 (12): 187197. 2009.We investigate effective categoricity of computable Abelian pgroups . We prove that all computably categorical Abelian pgroups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian pgroups are categorical and relatively categorical

6Some effects of Ash–Nerode and other decidability conditions on degree spectraAnnals of Pure and Applied Logic 55 (1): 5165. 1991.With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is intrinsically r.e. if and only if a natural recursivesyntacti…Read more

36Chains and antichains in partial orderingsArchive for Mathematical Logic 48 (1): 3953. 2009.We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there is a computa…Read more

26Isomorphism relations on computable structuresJournal of Symbolic Logic 77 (1): 122132. 2012.We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FFreducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω

18Spectra of Structures and RelationsJournal of Symbolic Logic 72 (1). 2007.We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to be spectrally universal. We use our results to answer a question of Goncharov, an…Read more

14San Antonio Convention Center San Antonio, Texas January 14–15, 2006Bulletin of Symbolic Logic 12 (4). 2006.

6Turing degrees of hypersimple relations on computable structuresAnnals of Pure and Applied Logic 121 (23): 209226. 2003.Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computabilitytheoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose d…Read more

13Computability of fraïssé limitsJournal of Symbolic Logic 76 (1). 2011.Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is defi…Read more

8$\Pi _{1}^{0}$ Classes and Strong Degree Spectra of RelationsJournal of Symbolic Logic 72 (3). 2007.We study the weak truthtable and truthtable degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truthtable reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof

George Washington UniversityRegular Faculty
Areas of Interest
Logic and Philosophy of Logic 
General Philosophy of Science 