13 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.  28
    Embeddings Into the Medvedev and Muchnik Lattices of Π0 1 Classes.Stephen Binns & Stephen G. Simpson - 2004 - Archive for Mathematical Logic 43 (3):399-414.
    Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  3.  23
    A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
    This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  4.  10
    Π⁰₁ Classes with Complex Elements.Stephen Binns - 2008 - Journal of Symbolic Logic 73 (4):1341-1353.
    An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some sense. We give (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  22
    Small Π0 1 Classes.Stephen Binns - 2006 - Archive for Mathematical Logic 45 (4):393-410.
    The property of smallness for Π0 1 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π0 1 class depends only on the Muchnik degree of a Π0 1 class. A comparison is made with the idea of thinness for Π0 1 classesmsthm.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  6.  6
    Hyperimmunity in 2sp ℕ.Stephen Binns - 2007 - Notre Dame Journal of Formal Logic 48 (2):293-316.
    We investigate the notion of hyperimmunity with respect to how it can be applied to Π{\sp 0}{\sb 1} classes and their Muchnik degrees. We show that hyperimmunity is a strong enough concept to prove the existence of Π{\sp 0}{\sb 1} classes with intermediate Muchnik degree—in contrast to Post's attempts to construct intermediate c.e. degrees.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  7.  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  
  8.  17
    Finding Paths Through Narrow and Wide Trees.Stephen Binns & Bjørn Kjos-Hanssen - 2009 - Journal of Symbolic Logic 74 (1):349-360.
    We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak König's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  9.  31
    Compressibility and Kolmogorov Complexity.Stephen Binns & Marie Nicholson - 2013 - Notre Dame Journal of Formal Logic 54 (1):105-123.
    This paper continues the study of the metric topology on $2^{\mathbb {N}}$ that was introduced by S. Binns. This topology is induced by a directional metric where the distance from $Y\in2^{\mathbb {N}}$ to $X\in2^{\mathbb {N}}$ is given by \[\limsup_{n}\frac{C(X\upharpoonright n|Y\upharpoonright n)}{n}.\] This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on $2^{\mathbb {N}}$ and that under it the functions $X\mapsto\operatorname{dim}_{\mathcal{H}}X$ and $X\mapsto\operatorname{dim}_{p}X$ are continuous. We also investigate (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  33
    Relative Kolmogorov Complexity and Geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.
    We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  19
    Hyperimmunity in 2.Stephen Binns - 2007 - Notre Dame Journal of Formal Logic 48 (2).
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  2
    Mass Problems and Density.Stephen Binns, Richard A. Shore & Stephen G. Simpson - 2016 - Journal of Mathematical Logic 16 (2):1650006.
    Recall that [Formula: see text] is the lattice of Muchnik degrees of nonempty effectively compact sets in Euclidean space. We solve a long-standing open problem by proving that [Formula: see text] is dense, i.e. satisfies [Formula: see text]. Our proof combines an oracle construction with hyperarithmetical theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  7
    Completeness, Compactness, Effective Dimensions.Stephen Binns - 2013 - Mathematical Logic Quarterly 59 (3):206-218.