-
12Cohesive powers of structuresArchive for Mathematical Logic 1-24. forthcoming.A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider its effective power over a cohesive set of natural numbers. A cohesive set is an infinite set of natural numbers that is indecomposable with respect to computably enumerable sets. It plays the role of an ultrafilter, and the elements of a cohesive power are the equivalence classes of certain partial computable functions determined by the cohesive s…Read more
-
17Belegradek, O., Verbovskiy, V. and Wagner, FO, CosetAnnals of Pure and Applied Logic 121 (1): 287. 2003.
-
11On Cohesive Powers of Linear OrdersJournal of Symbolic Logic 88 (3): 947-1004. 2023.Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual pre…Read more
-
11Interpreting a Field in its Heisenberg GroupJournal of Symbolic Logic 87 (3): 1215-1230. 2022.We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Mo…Read more
-
13On the isomorphism problem for some classes of computable algebraic structuresArchive for Mathematical Logic 61 (5): 813-825. 2022.We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.
-
2Logic and Algebraic Structures in Quantum Computing (edited book)Cambridge University Press. 2014.Experts in the field explore the connections across physics, quantum logic, and quantum computing.
-
192005–06 Winter Meeting of the Association for Symbolic LogicBulletin of Symbolic Logic 12 (4): 613-624. 2006.
-
7Computable Structures and the Hyperarithmetical HierarchyBulletin of Symbolic Logic 7 (3): 383-385. 2001.
-
26Sergei 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): 1188-1190. 1998.
-
20Computability-theoretic categoricity and Scott familiesAnnals of Pure and Applied Logic 170 (6): 699-717. 2019.
-
35Σ 1 0 and Π 1 0 equivalence structuresAnnals of Pure and Applied Logic 162 (7): 490-503. 2011.We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures
-
48Computability-theoretic complexity of countable structuresBulletin of Symbolic Logic 8 (4): 457-477. 2002.Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computabl…Read more
-
52New Orleans Marriott and Sheraton New Orleans New Orleans, Louisiana January 7–8, 2007Bulletin of Symbolic Logic 13 (3). 2007.
-
62Intrinsic bounds on complexity and definability at limit levelsJournal of Symbolic Logic 74 (3): 1047-1060. 2009.We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ on A (equivalently,…Read more
-
19The possible turing degree of the nonzero member in a two element degree spectrumAnnals of Pure and Applied Logic 60 (1): 1-30. 1993.We construct a recursive model , a recursive subset R of its domain, and a Turing degree x 0 satisfying the following condition. The nonrecursive images of R under all isomorphisms from to other recursive models are of Turing degree x and cannot be recursively enumerable
-
18Review: C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (review)Bulletin of Symbolic Logic 7 (3): 383-385. 2001.
-
90Simple and immune relations on countable structuresArchive for Mathematical Logic 42 (3): 279-291. 2003.Let ???? be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of ???? in which the image of R (¬R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on ???? and R, a necessary and sufficient condition for the existence of a computable copy ℬ of ???? in which the image of R (¬R, resp.) is simple (immune, resp.).
-
31Spaces of orders and their Turing degree spectraAnnals of Pure and Applied Logic 161 (9): 1134-1143. 2010.We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s …Read more
-
39Effective categoricity of equivalence structuresAnnals of Pure and Applied Logic 141 (1): 61-78. 2006.We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Sin…Read more
-
33Effectively and Noneffectively Nowhere Simple SetsMathematical Logic Quarterly 42 (1): 241-248. 1996.R. Shore proved that every recursively enumerable set can be split into two nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets.…Read more
-
66Enumerations in computable structure theoryAnnals of Pure and Applied Logic 136 (3): 219-246. 2005.We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a com…Read more
-
44Degree spectra of the successor relation of computable linear orderingsArchive for Mathematical Logic 48 (1): 7-13. 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
-
18Uncountable degree spectraAnnals of Pure and Applied Logic 54 (3): 255-263. 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
-
4Review: Sergei S. Goncharov, Countable Boolean Algebras and Decidability (review)Journal of Symbolic Logic 63 (3): 1188-1190. 1998.
-
12Ash 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): 383-385. 2001.
-
16Dependence relations in computably rigid computable vector spacesAnnals of Pure and Applied Logic 132 (1): 97-108. 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 ]
-
28
-
George Washington UniversityRegular Faculty
Areas of Interest
Logic and Philosophy of Logic |
General Philosophy of Science |