8 citations · 16 across the 8 of their papers we have counts for
8 papers
Halin's Infinite Ray Theorems: Complexity and Reverse Mathematics: Version E
James S. Barnes, Jun Le Goh, Richard A. Shore
Halin [1965] proved that if a graph has many pairwise disjoint rays for each then it has infinitely many pairwise disjoint rays. We analyze the complexity of this and other…
Lattice initial segments of the hyperdegrees
Richard A. Shore, Bjørn Kjos-Hanssen
We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, . In fact, we…
The Strength of the Grätzer-Schmidt Theorem
Katie Brodhead, Mushfeq Khan, Bjørn Kjos-Hanssen +3
The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this the…
Computing Maximal Chains
Alberto Marcone, Antonio Montalbán, Richard A. Shore
In 1967 Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that…
Computably enumerable partial orders
Peter A. Cholak, Damir D. Dzhafarov, Noah Schweber +1
We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain…
The maximal linear extension theorem in second order arithmetic
Alberto Marcone, Richard A. Shore
We show that the maximal linear extension theorem for well partial orders is equivalent over RCA_0 to ATR_0. Analogously, the maximal chain theorem for well partial orders is equiv…