Source author record

Takayuki Kihara

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO Logic in Computer Science math.GN

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Degree spectra of homeomorphism types of compact Polish spaces

A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $0'$ -computable low $_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$ , there exists a Polish space $X_n$ such that exactly the high $_{n}$ -degrees are required to present the homeomorphism type of $X_n$ . We also show that no compact Polish space has a least presentation with respect to Turing reducibility. The first version of this article appeared in April 2020. A major update was made in September 2023, with improved proofs and results. This is the final version from January 2024, with more results on Čech homology groups.

preprint2023arXiv

Ideal presentations and numberings of some classes of effective quasi-Polish spaces

The well known ideal presentations of countably based domains were recently extended to (effective) quasi-Polish spaces. Continuing these investigations, we explore some classes of effective quasi-Polish spaces. In particular, we prove an effective version of the domain-characterization of quasi-Polish spaces, describe effective extensions of quasi-Polish topologies, discover natural numberings of classes of effective quasi-Polish spaces, estimate the complexity of the (effective) homeomorphism relation and of some classes of spaces w.r.t. these numberings, and investigate degree spectra of continuous domains.

preprint2022arXiv

On some topics around the Wadge rank $ω_2$

Kechris and Martin showed that the Wadge rank of the $ω$ -th level of the decreasing difference hierarchy of coanalytic sets is $ω_2$ under the axiom of determinacy. In this article, we give an alternative proof of the Kechris-Martin theorem, by understanding the $ω$ -th level of the decreasing difference hierarchy of coanalytic sets as the (relative) hyperarithmetical processes with finite mind-changes. Based on this viewpiont, we also examine the gap between the increasing and decreasing difference hierarchies of coanalytic sets by relating them to the $Π^1_1$ - and $Σ^1_1$ -least number principles, respectively. We also analyze Weihrauch degrees of related principles.

preprint2021arXiv

A syntactic approach to Borel functions: Some extensions of Louveau's theorem

Louveau showed that if a Borel set in a Polish space happens to be in a Borel Wadge class $Γ$ , then its $Γ$ -code can be obtained from its Borel code in a hyperarithmetical manner. We extend Louveau's theorem to Borel functions: If a Borel function on a Polish space happens to be a $Σ_t$ -function, then one can effectively find its $Σ_t$ -code hyperarithmetically relative to its Borel code. More generally, we prove extension-type, domination-type, and decomposition-type variants of Louveau's theorem for Borel functions.

preprint2020arXiv

Enumeration degrees and non-metrizable topology

The enumeration degrees of sets of natural numbers can be identified with the degrees of difficulty of enumerating neighborhood bases of points in a universal second-countable $T_0$ -space (e.g. the $ω$ -power of the Sierpiński space). Hence, every represented second-countable $T_0$ -space determines a collection of enumeration degrees. For instance, Cantor space captures the total degrees, and the Hilbert cube captures the continuous degrees by definition. Based on these observations, we utilize general topology (particularly non-metrizable topology) to establish a classification theory of enumeration degrees of sets of natural numbers.

preprint2016arXiv

Decomposing Borel functions using the Shore-Slaman join theorem

Jayne and Rogers proved that every function from an analytic space into a separable metric space is decomposable into countably many continuous functions with closed domains if and only if the preimage of each $F_σ$ set under it is again $F_σ$ . Many researchers conjectured that the Jayne-Rogers theorem can be generalized to all finite levels of Borel functions. In this paper, by using the Shore-Slaman join theorem on the Turing degrees, we show the following variant of the Jayne-Rogers theorem at finite and transfinite levels of the hierarchy of Borel functions: For all countable ordinals $α$ and $β$ with $α\leqβ<α\cdot 2$ , every function between Polish spaces having small transfinite inductive dimension is decomposable into countably many Baire class $γ$ functions with $\mathbfΔ^0_{β+1}$ domains such that $γ+α\leqβ$ if and only if the preimage of each $\mathbfΣ^0_{α+1}$ set under that function is $\mathbfΣ^0_{β+1}$ , and the transformation of a $\mathbfΣ^0_{α+1}$ set into the $\mathbfΣ^0_{β+1}$ preimage is continuous.

preprint2016arXiv

Dividing by zero - how bad is it, really?

In computable analysis testing a real number for being zero is a fundamental example of a non-computable task. This causes problems for division: We cannot ensure that the number we want to divide by is not zero. In many cases, any real number would be an acceptable outcome if the divisor is zero - but even this cannot be done in a computable way. In this note we investigate the strength of the computational problem "Robust division": Given a pair of real numbers, the first not greater than the other, output their quotient if well-defined and any real number else. The formal framework is provided by Weihrauch reducibility. One particular result is that having later calls to the problem depending on the outcomes of earlier ones is strictly more powerful than performing all calls concurrently. However, having a nesting depths of two already provides the full power. This solves an open problem raised at a recent Dagstuhl meeting on Weihrauch reducibility. As application for "Robust division", we show that it suffices to execute Gaussian elimination.

preprint2016arXiv

The uniform Martin's conjecture for many-one degrees

We study functions from reals to reals which are uniformly degree-invariant from Turing-equivalence to many-one equivalence, and compare them "on a cone." We prove that they are in one-to-one correspondence with the Wadge degrees, which can be viewed as a refinement of the uniform Martin's conjecture for uniformly invariant functions from Turing- to Turing-equivalence. Our proof works in the general case of many-one degrees on $\mathcal{Q}^ω$ and Wadge degrees of functions $ω^ω\to\mathcal{Q}$ for any better quasi ordering $\mathcal{Q}$ .

preprint2016arXiv

Turing degrees in Polish spaces and decomposability of Borel functions

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 (\eg the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture, and we explore the idea of applying the technique of turning Borel-measurable functions into continuous ones.

preprint2013arXiv

Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism

Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded-learnability is equivalent to finite $(Π^0_1)_2$ -piecewise computability (where $(Π^0_1)_2$ denotes the difference of two $Π^0_1$ sets), error-bounded-learnability is equivalent to finite $Δ^0_2$ -piecewise computability, and learnability is equivalent to countable $Π^0_1$ -piecewise computability (equivalently, countable $Σ^0_2$ -piecewise computability). Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games.

preprint2013arXiv

Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial $Π^0_1$ subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty $Π^0_1$ subsets of Cantor space, we show the existence of a finite- $Δ^0_2$ -piecewise degree containing infinitely many finite- $(Π^0_1)_2$ -piecewise degrees, and a finite- $(Π^0_2)_2$ -piecewise degree containing infinitely many finite- $Δ^0_2$ -piecewise degrees (where $(Π^0_n)_2$ denotes the difference of two $Π^0_n$ sets), whereas the greatest degrees in these three "finite- $Γ$ -piecewise" degree structures coincide. Moreover, as for nonempty $Π^0_1$ subsets of Cantor space, we also show that every nonzero finite- $(Π^0_1)_2$ -piecewise degree includes infinitely many Medvedev (i.e., one-piecewise) degrees, every nonzero countable- $Δ^0_2$ -piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite- $(Π^0_2)_2$ -countable- $Δ^0_2$ -piecewise degree includes infinitely many countable- $Δ^0_2$ -piecewise degrees, and every nonzero Muchnik (i.e., countable- $Π^0_2$ -piecewise) degree includes infinitely many finite- $(Π^0_2)_2$ -countable- $Δ^0_2$ -piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable- $Δ^0_2$ -piecewise degree of a nonempty $Π^0_1$ subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev (Muchnik) degree structure and the finite- $Γ$ -piecewise degree structure of all subsets of Baire space by showing that none of the finite- $Γ$ -piecewise structures are Brouwerian, where $Γ$ is any of the Wadge classes mentioned above.

preprint2011arXiv

Incomputability of Simply Connected Planar Continua

Le Roux and Ziegler asked whether every simply connected compact nonempty planar co-c.e. closed set always contains a computable point. In this paper, we solve the problem of le Roux and Ziegler by showing that there exists a contractible planar co-c.e. dendroid without computable points. We also provide several pathological examples of tree-like co-c.e. continua fulfilling certain global incomputability properties: there is a computable dendrite which does not *-include a co-c.e. tree; there is a co-c.e. dendrite which does not *-include a computable dendrite; there is a computable dendroid which does not *-include a co-c.e. dendrite. Here, a continuum A *-includes a member of a class P of continua if, for every positive real, A includes a P-continuum B such that the Hausdorff distance between A and B is smaller than the real.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Takayuki Kihara

Research overview

Is this your work?

12 publications

Degree spectra of homeomorphism types of compact Polish spaces

Ideal presentations and numberings of some classes of effective quasi-Polish spaces

On some topics around the Wadge rank $ω_2$

A syntactic approach to Borel functions: Some extensions of Louveau's theorem

Enumeration degrees and non-metrizable topology

Decomposing Borel functions using the Shore-Slaman join theorem

Dividing by zero - how bad is it, really?

The uniform Martin's conjecture for many-one degrees

Turing degrees in Polish spaces and decomposability of Borel functions

Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism

Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions

Incomputability of Simply Connected Planar Continua

See the researcher in context

Building this map preview

Takayuki Kihara

Research overview

Is this your work?

12 publications

Degree spectra of homeomorphism types of compact Polish spaces

Ideal presentations and numberings of some classes of effective quasi-Polish spaces

On some topics around the Wadge rank ω2ω_2ω2​

A syntactic approach to Borel functions: Some extensions of Louveau's theorem

Enumeration degrees and non-metrizable topology

Decomposing Borel functions using the Shore-Slaman join theorem

Dividing by zero - how bad is it, really?

The uniform Martin's conjecture for many-one degrees

Turing degrees in Polish spaces and decomposability of Borel functions

Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism

Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions

Incomputability of Simply Connected Planar Continua

See the researcher in context

Building this map preview

On some topics around the Wadge rank $ω_2$