10 found
Order:
  1.  3
    Turing Degrees in Polish Spaces and Decomposability of Borel Functions.Vassilios Gregoriades, Takayuki Kihara & Keng Meng Ng - 2020 - Journal of Mathematical Logic 21 (1):2050021.
    We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  10
    The ∀∃-Theory of the Effectively Closed Medvedev Degrees is Decidable.Joshua A. Cole & Takayuki Kihara - 2010 - Archive for Mathematical Logic 49 (1):1-16.
    We show that there is a computable procedure which, given an ∀∃-sentence ${\varphi}$ in the language of the partially ordered sets with a top element 1 and a bottom element 0, computes whether ${\varphi}$ is true in the Medvedev degrees of ${\Pi^0_1}$ classes in Cantor space, sometimes denoted by ${\mathcal{P}_s}$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  10
    Effective Strong Nullness and Effectively Closed Sets.Kojiro Higuchi & Takayuki Kihara - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 303--312.
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  16
    Unified Characterizations of Lowness Properties Via Kolmogorov Complexity.Takayuki Kihara & Kenshi Miyabe - 2015 - Archive for Mathematical Logic 54 (3-4):329-358.
    Consider a randomness notion C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. A uniform test in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} is a total computable procedure that each oracle X produces a test relative to X in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. We say that a binary sequence Y is C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}-random uniformly relative to (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  16
    On the Strength of Marriage Theorems and Uniformity.Makoto Fujiwara, Kojiro Higuchi & Takayuki Kihara - 2014 - Mathematical Logic Quarterly 60 (3):136-153.
  6.  19
    The Binary Expansion and the Intermediate Value Theorem in Constructive Reverse Mathematics.Josef Berger, Hajime Ishihara, Takayuki Kihara & Takako Nemoto - 2019 - Archive for Mathematical Logic 58 (1-2):203-217.
    We introduce the notion of a convex tree. We show that the binary expansion for real numbers in the unit interval ) is equivalent to weak König lemma ) for trees having at most two nodes at each level, and we prove that the intermediate value theorem is equivalent to \ for convex trees, in the framework of constructive reverse mathematics.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  5
    Decomposing Functions of Baire Class on Polish Spaces.Longyun Ding, Takayuki Kihara, Brian Semmes & Jiafei Zhao - 2020 - Journal of Symbolic Logic 85 (3):960-971.
    We prove the Decomposability Conjecture for functions of Baire class $2$ from a Polish space to a separable metrizable space. This partially answers an important open problem in descriptive set theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  11
    A Hierarchy of Immunity and Density for Sets of Reals.Takayuki Kihara - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 384--394.
    Direct download  
     
    Export citation  
     
    Bookmark  
  9.  9
    On a Metric Generalization of the Tt-Degrees and Effective Dimension Theory.Takayuki Kihara - 2019 - Journal of Symbolic Logic 84 (2):726-749.
    In this article, we study an analogue of tt-reducibility for points in computable metric spaces. We characterize the notion of the metric tt-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  5
    Searching for an Analogue of Atr0 in the Weihrauch Lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
    There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark