-
Logic in the History and Philosophy of Mathematical PracticeIn Bharath Sriraman (ed.), Handbook of the History and Philosophy of Mathematical Practice, Springer. pp. 1905-1920. 2024.Mathematical logic is the study of reasoning about mathematical objects and the degree to which mathematical and scientific reasoning can be formalized and mechanized. Logic provides the foundations of mathematics and of theoretical computer science. Classical logic defined truth, developed the theory of infinite numbers, resolved paradoxes of naive set theory, defined what an algorithm is, and established that certain mathematical principles are independent from the rest of mathematics. Modern …Read more
-
3Computability TheoryIn Bharath Sriraman (ed.), Handbook of the History and Philosophy of Mathematical Practice, Springer. pp. 1933-1961. 2024.Computability theory is the mathematical theory of algorithms, which explores the power and limitations of computation. Classical computability theory formalized the intuitive notion of an algorithm and provided a theoretical basis for digital computers. It also demonstrated the limitations of algorithms and showed that most sets of natural numbers and the problems they encode are not decidable (Turing computable). Important results of modern computability theory include the classification of th…Read more
-
Countable Nonstandard Models: Following Skolem’s ApproachIn Bharath Sriraman (ed.), Handbook of the History and Philosophy of Mathematical Practice, Springer. pp. 1989-2009. 2024.In 1934, Skolem gave a remarkable construction of a countable nonstandard model of arithmetic. His construction contains ideas of the ultrapower construction which was introduced in model theory 20 years later. However, typical ultrapower constructions produce uncountable models. Skolem’s construction can also be connected with ideas from computability theory, formalized by Turing and others in 1936. The proof of one of Skolem’s key statements can be interpreted using computability-theoretic not…Read more
-
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
-
19Belegradek, O., Verbovskiy, V. and Wagner, FO, CosetAnnals of Pure and Applied Logic 121 (1): 287. 2003.
-
13On 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
-
12Interpreting 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.
-
27Sergei 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.
-
21Computability-theoretic categoricity and Scott familiesAnnals of Pure and Applied Logic 170 (6): 699-717. 2019.
-
36Σ 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
-
19Some effects of Ash–Nerode and other decidability conditions on degree spectraAnnals of Pure and Applied Logic 55 (1): 51-65. 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 recursive-syntacti…Read more
-
47Chains and antichains in partial orderingsArchive for Mathematical Logic 48 (1): 39-53. 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
-
69Isomorphism relations on computable structuresJournal of Symbolic Logic 77 (1): 122-132. 2012.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 ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω
-
30San Antonio Convention Center San Antonio, Texas January 14–15, 2006Bulletin of Symbolic Logic 12 (4). 2006.
-
26Turing degrees of hypersimple relations on computable structuresAnnals of Pure and Applied Logic 121 (2-3): 209-226. 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 computability-theoretic 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
-
59Computability 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
-
25Effective categoricity of Abelian p -groupsAnnals of Pure and Applied Logic 159 (1-2): 187-197. 2009.We investigate effective categoricity of computable Abelian p-groups . We prove that all computably categorical Abelian p-groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p-groups are categorical and relatively categorical
-
17Regular relations and the quantifier “there exist uncountably many”Mathematical Logic Quarterly 29 (3): 151-161. 1983.
-
55Computability-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
-
54New Orleans Marriott and Sheraton New Orleans New Orleans, Louisiana January 7–8, 2007Bulletin of Symbolic Logic 13 (3). 2007.
-
64Intrinsic 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
-
24The 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
-
George Washington UniversityRegular Faculty
Areas of Interest
Logic and Philosophy of Logic |
General Philosophy of Science |