25 found
Order:
  1.  7
    Computable Functors and Effective Interpretability.Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller & Antonio Montalbán - 2017 - Journal of Symbolic Logic 82 (1):77-97.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  2. A Note on Cancellation Axioms for Comparative Probability.Matthew Harrison-Trainor, Wesley H. Holliday & Thomas F. Icard - 2016 - Theory and Decision 80 (1):159-166.
    We prove that the generalized cancellation axiom for incomplete comparative probability relations introduced by Rios Insua and Alon and Lehrer is stronger than the standard cancellation axiom for complete comparative probability relations introduced by Scott, relative to their other axioms for comparative probability in both the finite and infinite cases. This result has been suggested but not proved in the previous literature.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  14
    Automatic and Polynomial-Time Algebraic Structures.Nikolay Bazhenov, Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov & Keng Meng Ng - 2019 - Journal of Symbolic Logic 84 (4):1630-1669.
    A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  38
    The Logic of Comparative Cardinality.Yifeng Ding, Matthew Harrison-Trainor & Wesley H. Holliday - 2020 - Journal of Symbolic Logic 85 (3):972-1005.
    This paper investigates the principles that one must add to Boolean algebra to capture reasoning not only about intersection, union, and complementation of sets, but also about the relative size of sets. We completely axiomatize such reasoning under the Cantorian definition of relative size in terms of injections.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  17
    Degrees of Categoricity on a Cone Via Η-Systems.Barbara F. Csima & Matthew Harrison-Trainor - 2017 - Journal of Symbolic Logic 82 (1):325-346.
    We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  10
    Finitely Generated Groups Are Universal Among Finitely Generated Structures.Matthew Harrison-Trainor & Meng-Che “Turbo” Ho - 2021 - Annals of Pure and Applied Logic 172 (1):102855.
    Universality has been an important concept in computable structure theory. A class C of structures is universal if, informally, for any structure of any kind there is a structure in C with the same computability-theoretic properties as the given structure. Many classes such as graphs, groups, and fields are known to be universal. This paper is about the class of finitely generated groups. Because finitely generated structures are relatively simple, the class of finitely generated groups has no hope of being (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  4
    Relationships Between Computability-Theoretic Properties of Problems.Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey & Dan Turetsky - 2022 - Journal of Symbolic Logic 87 (1):47-71.
    A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  5
    Scott Complexity of Countable Structures.Rachael Alvir, Noam Greenberg, Matthew Harrison-Trainor & Dan Turetsky - 2021 - Journal of Symbolic Logic 86 (4):1706-1720.
    We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  53
    Inferring Probability Comparisons.Matthew Harrison-Trainor, Wesley H. Holliday & Thomas Icard - 2018 - Mathematical Social Sciences 91:62-70.
    The problem of inferring probability comparisons between events from an initial set of comparisons arises in several contexts, ranging from decision theory to artificial intelligence to formal semantics. In this paper, we treat the problem as follows: beginning with a binary relation ≥ on events that does not preclude a probabilistic interpretation, in the sense that ≥ has extensions that are probabilistically representable, we characterize the extension ≥+ of ≥ that is exactly the intersection of all probabilistically representable extensions of (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  11
    Borel Functors and Infinitary Interpretations.Matthew Harrison-Trainor, Russell Miller & Antonio Montalbán - 2018 - Journal of Symbolic Logic 83 (4):1434-1456.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11. The Gamma Question for Many-One Degrees.Matthew Harrison-Trainor - 2017 - Annals of Pure and Applied Logic 168 (7):1396-1405.
  12.  5
    Differential-Algebraic Jet Spaces Preserve Internality to the Constants.Zoe Chatzidakis, Matthew Harrison-Trainor & Rahim Moosa - 2015 - Journal of Symbolic Logic 80 (3):1022-1034.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  7
    Non-Density in Punctual Computability.Noam Greenberg, Matthew Harrison-Trainor, Alexander Melnikov & Dan Turetsky - 2021 - Annals of Pure and Applied Logic 172 (9):102985.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  11
    The Tree of Tuples of a Structure.Matthew Harrison-Trainor & Antonio Montalbán - 2022 - Journal of Symbolic Logic 87 (1):21-46.
    Our main result is that there exist structures which cannot be computably recovered from their tree of tuples. This implies that there are structures with no computable copies which nevertheless cannot code any information in a natural/functorial way.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  20
    There is No Classification of the Decidably Presentable Structures.Matthew Harrison-Trainor - 2018 - Journal of Mathematical Logic 18 (2):1850010.
    A computable structure [Formula: see text] is decidable if, given a formula [Formula: see text] of elementary first-order logic, and a tuple [Formula: see text], we have a decision procedure to decide whether [Formula: see text] holds of [Formula: see text]. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is [Formula: see text]-complete. We also show that for each [Formula: see text] (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  16. Some Questions of Uniformity in Algorithmic Randomness.Laurent Bienvenu, Barbara F. Csima & Matthew Harrison-Trainor - 2021 - Journal of Symbolic Logic 86 (4):1612-1631.
    The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $, a universal prefix-free machine U whose halting probability is $\alpha $. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha $, one cannot uniformly produce a left-c.e. real $\beta $ such that $\alpha - \beta $ is neither left-c.e. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17. An Introduction to the Scott Complexity of Countable Structures and a Survey of Recent Results.Matthew Harrison-Trainor - 2022 - Bulletin of Symbolic Logic 28 (1):71-103.
    Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  9
    First-Order Possibility Models and Finitary Completeness Proofs.Matthew Harrison-Trainor - 2019 - Review of Symbolic Logic 12 (4):637-662.
    This article builds on Humberstone’s idea of defining models of propositional modal logic where total possible worlds are replaced by partial possibilities. We follow a suggestion of Humberstone by introducing possibility models for quantified modal logic. We show that a simple quantified modal logic is sound and complete for our semantics. Although Holliday showed that for many propositional modal logics, it is possible to give a completeness proof using a canonical model construction where every possibility consists of finitely many formulas, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  1
    A Minimal Set Low for Speed.Rod Downey & Matthew Harrison-Trainor - forthcoming - Journal of Symbolic Logic:1-37.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  6
    The Property “Arithmetic-is-Recursive” on a Cone.Uri Andrews, Matthew Harrison-Trainor & Noah Schweber - 2021 - Journal of Mathematical Logic 21 (3):2150021.
    We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  21.  7
    The Complexity of Countable Structures.Matthew Harrison-Trainor - 2018 - Bulletin of Symbolic Logic 24 (4):465-466.
  22.  3
    The Property “Arithmetic-is-Recursive” on a Cone.Uri Andrews, Matthew Harrison-Trainor & Noah Schweber - 2021 - Journal of Mathematical Logic 21 (3).
    We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  23.  2
    Computability of Polish Spaces Up to Homeomorphism.Matthew Harrison-Trainor, Alexander Melnikov & Keng Meng Ng - 2020 - Journal of Symbolic Logic 85 (4):1664-1686.
    We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $, an effectively closed set not homeomorphic to any $0^{}$-computable Polish space; this answers a question of Nies. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  2
    Computable Valued Fields.Matthew Harrison-Trainor - 2018 - Archive for Mathematical Logic 57 (5-6):473-495.
    We investigate the computability-theoretic properties of valued fields, and in particular algebraically closed valued fields and p-adically closed valued fields. We give an effectiveness condition, related to Hensel’s lemma, on a valued field which is necessary and sufficient to extend the valuation to any algebraic extension. We show that there is a computable formally p-adic field which does not embed into any computable p-adic closure, but we give an effectiveness condition on the divisibility relation in the value group which is (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  25.  1
    Left-orderable computable groups.Matthew Harrison-Trainor - 2018 - Journal of Symbolic Logic 83 (1):237-255.
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark