26 found
Order:
  1. On a Conjecture of Dobrinen and Simpson Concerning Almost Everywhere Domination.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman & Reed Solomon - 2006 - Journal of Symbolic Logic 71 (1):119 - 136.
  2.  6
    Separating Principles Below Ramsey's Theorem for Pairs.Manuel Lerman, Reed Solomon & Henry Towsner - 2013 - Journal of Mathematical Logic 13 (2):1350007.
    In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from RT, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below RT has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that ADS is not equivalent to CAC and that EM is not equivalent to RT.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  3. Effectiveness for Infinite Variable Words and the Dual Ramsey Theorem.Joseph S. Miller & Reed Solomon - 2004 - Archive for Mathematical Logic 43 (4):543-555.
    We examine the Dual Ramsey Theorem and two related combinatorial principles VW(k,l) and OVW(k,l) from the perspectives of reverse mathematics and effective mathematics. We give a statement of the Dual Ramsey Theorem for open colorings in second order arithmetic and formalize work of Carlson and Simpson [1] to show that this statement implies ACA 0 over RCA 0 . We show that neither VW(2,2) nor OVW(2,2) is provable in WKL 0 . These results give partial answers to questions posed by (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4. Degrees of Orders on Torsion-Free Abelian Groups.Asher M. Kach, Karen Lange & Reed Solomon - 2013 - Annals of Pure and Applied Logic 164 (7-8):822-836.
    We show that if H is an effectively completely decomposable computable torsion-free abelian group, then there is a computable copy G of H such that G has computable orders but not orders of every degree.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  28
    Enumerations in Computable Structure Theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
    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 computable isomorphic copy.A computable structure is (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  6. Stability and Posets.Carl Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693 - 711.
    Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite $\Pi _1^0 $ chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  32
    A Δ20 Set with No Infinite Low Subset in Either It or its Complement.Rod Downey, Denis R. Hirschfeldt, Steffen Lempp & Reed Solomon - 2001 - Journal of Symbolic Logic 66 (3):1371-1381.
    We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of RCA 0 + SRT 2 2 must contain a nonlow set.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  8. – CA 0 and Order Types of Countable Ordered Groups.Reed Solomon - 2001 - Journal of Symbolic Logic 66 (1):192-206.
  9.  19
    Reverse Mathematics and the Equivalence of Definitions for Well and Better Quasi-Orders.Peter Cholak, Alberto Marcone & Reed Solomon - 2004 - Journal of Symbolic Logic 69 (3):683-712.
  10. A Computably Stable Structure with No Scott Family of Finitary Formulas.Peter Cholak, Richard A. Shore & Reed Solomon - 2006 - Archive for Mathematical Logic 45 (5):519-538.
  11. Ordered Groups: A Case Study in Reverse Mathematics.Reed Solomon - 1999 - Bulletin of Symbolic Logic 5 (1):45-58.
  12. Reverse Mathematics and Fully Ordered Groups.Reed Solomon - 1998 - Notre Dame Journal of Formal Logic 39 (2):157-189.
    We study theorems of ordered groups from the perspective of reverse mathematics. We show that suffices to prove Hölder's Theorem and give equivalences of both (the orderability of torsion free nilpotent groups and direct products, the classical semigroup conditions for orderability) and (the existence of induced partial orders in quotient groups, the existence of the center, and the existence of the strong divisible closure).
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  13.  24
    Computable Categoricity of Trees of Finite Height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
    We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical but (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  14.  48
    Jump Degrees of Torsion-Free Abelian Groups.Brooke M. Andersen, Asher M. Kach, Alexander G. Melnikov & Reed Solomon - 2012 - Journal of Symbolic Logic 77 (4):1067-1100.
    We show, for each computable ordinal α and degree $\alpha > {0^{\left( \alpha \right)}}$, the existence of a torsion-free abelian group with proper α th jump degree α.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  15.  19
    Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
    We divide the class of infinite computable trees into three types. For the first and second types, 0' computes a nontrivial self-embedding while for the third type 0'' computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite Π01 antichain. This result is optimal and has connections (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16.  14
    Π10 Classes and Orderable Groups.Reed Solomon - 2002 - Annals of Pure and Applied Logic 115 (1-3):279-302.
    It is known that the spaces of orders on orderable computable fields can represent all Π10 classes up to Turing degree. We show that the spaces of orders on orderable computable abelian and nilpotent groups cannot represent Π10 classes in even a weak manner. Next, we consider presentations of ordered abelian groups, and we show that there is a computable ordered abelian group for which no computable presentation admits a computable set of representatives for its Archimedean classes.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  17.  15
    The Complexity of Central Series in Nilpotent Computable Groups.Barbara F. Csima & Reed Solomon - 2011 - Annals of Pure and Applied Logic 162 (8):667-678.
    The terms of the upper and lower central series of a nilpotent computable group have computably enumerable Turing degree. We show that the Turing degrees of these terms are independent even when restricted to groups which admit computable orders.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  18.  11
    2010 North American Annual Meeting of the Association for Symbolic Logic.Reed Solomon - 2011 - Bulletin of Symbolic Logic 17 (1):127-154.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  1
    The Determined Property of Baire in Reverse Math.Eric P. Astor, Damir Dzhafarov, Antonio Montalbán, Reed Solomon & Linda Brown Westrick - 2020 - Journal of Symbolic Logic 85 (1):166-198.
    We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$, which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$. Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part of an ω-model (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  23
    And the Existence of Strong Divisible Closures (ACA0). Section 8 Deals More Directly with Computability Issues and Discusses the Relationship Between Π0. [REVIEW]Reed Solomon - 1999 - Bulletin of Symbolic Logic 5 (1).
  21.  21
    The Lindenbaum Algebra of the Theory of the Class of All Finite Models.Steffen Lempp, Mikhail Peretyat'kin & Reed Solomon - 2002 - Journal of Mathematical Logic 2 (02):145-225.
    In this paper, we investigate the Lindenbaum algebra ℒ of the theory T fin = Th of the class M fin of all finite models of a finite rich signature. We prove that this algebra is an atomic Boolean algebra while its Gödel numeration γ is a [Formula: see text]-numeration. Moreover, the quotient algebra /ℱ, γ/ℱ) modulo the Fréchet ideal ℱ is a [Formula: see text]-algebra, which is universal over the class of all [Formula: see text] Boolean algebras. These conditions (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  22.  11
    The Uniform Content of Partial and Linear Orders.Eric P. Astor, Damir D. Dzhafarov, Reed Solomon & Jacob Suggs - 2017 - Annals of Pure and Applied Logic 168 (6):1153-1171.
  23.  16
    New Orleans Marriott and Sheraton New Orleans New Orleans, Louisiana January 7–8, 2007.Matthew Foreman, Su Gao, Valentina Harizanov, Ulrich Kohlenbach, Michael Rathjen, Reed Solomon, Carol Wood & Marcia Groszek - 2007 - Bulletin of Symbolic Logic 13 (3).
    Direct download  
     
    Export citation  
     
    Bookmark  
  24.  12
    Reverse Mathematics and Infinite Traceable Graphs.Peter Cholak, David Galvin & Reed Solomon - 2012 - Mathematical Logic Quarterly 58 (1-2):18-28.
    We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  25.  16
    Embeddings of Computable Structures.Asher M. Kach, Oscar Levin & Reed Solomon - 2010 - Notre Dame Journal of Formal Logic 51 (1):55-68.
    We study what the existence of a classical embedding between computable structures implies about the existence of computable embeddings. In particular, we consider the effect of fixing and varying the computable presentations of the computable structures.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  26. Lowness for Isomorphism, Countable Ideals, and Computable Traceability.Johanna N. Y. Franklin & Reed Solomon - 2020 - Mathematical Logic Quarterly 66 (1):104-114.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark