PaperlayerView exact revision on arXiv

Source-linked AI summary

Closed Choice and a Uniform Low Basis Theorem

Vasco Brattka, Matthew de Brecht, Arno Pauly

arXiv:1002.2800v2math.LOcs.LO

TL;DR

Because closed choice is generally noncomputable, the paper asks how its Weihrauch degree varies with the solution space. It studies closed choice uniformly through Weihrauch reducibility, relating it to classes of computation and a low-point result for Cantor space.

  • Problem

    Because closed choice is generally noncomputable, the paper asks how its Weihrauch degree varies with the underlying space, with some resulting degrees associated with hypercomputation models.

    Source: §1 · p. 3

  • Method

    The paper studies closed choice for different spaces in a uniform framework using Weihrauch reducibility.

    Source: §1 · p. 3

  • Results

    Closed choice on the singleton, N, Cantor space, and Baire space corresponds respectively to computable, finite-mind-change, weakly computable, and effectively Borel measurable functions.

    Source: §10 · p. 46

  • Takeaways & Limitations

    For Cantor space, a representation that makes low points computable renders closed choice computable.

    Source: §1 · p. 4

    The inversion results are not optimal in general: for arbitrary represented spaces, an injective computable map need not have the behavior of the real-line case, which uses additional properties such as connectedness.

    Source: §6 · p. 20

Abstract

from arXiv · show

We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution. We show that with closed choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, of the natural numbers, of Cantor space and of Baire space correspond to the class of computable functions, of functions computable with finitely many mind changes, of weakly computable functions and of effectively Borel measurable functions, respectively. We also prove that all these classes correspond to classes of non-deterministically computable functions with the respective spaces as advice spaces. Moreover, we prove that closed choice on Euclidean space can be considered as "locally compact choice" and it is obtained as product of closed choice on the natural numbers and on Cantor space. We also prove a Quotient Theorem for compact choice which shows that single-valued functions can be "divided" by compact choice in a certain sense. Another result is the Independent Choice Theorem, which provides a uniform proof that many choice principles are closed under composition. Finally, we also study the related class of low computable functions, which contains the class of weakly computable functions as well as the class of functions computable with finitely many mind changes. As one main result we prove a uniform version of the Low Basis Theorem that states that closed choice on Cantor space (and the Euclidean space) is low computable. We close with some related observations on the Turing jump operation and its initial topology.

1 Introduction

Closed choice asks for a solution from negative information about which candidates are not solutions; its difficulty depends on the solution space. The paper uses Weihrauch degrees to connect these problems with hypercomputation and develops a low-point version of the Low Basis Theorem.

1 Introduction

  • Closed choice takes information about what does not constitute a solution and returns a solution.The relevant solution set is closed because membership in its complement can be continuously confirmed.Source: §1 · pp. 2–3
  • The introduction describes negative-information representations using enumerated excluded points, words, or rational intervals, depending on the space.For Cantor space the words' corresponding balls exhaust the complement; for the real line the representation lists rational intervals exhausting it.Source: §1 · p. 3
  • Closed choice is generally noncomputable, so the paper classifies its Weihrauch degree according to the underlying space.Some resulting degrees are associated with models of type-2 hypercomputation.Source: §1 · p. 3
  • For Cantor space, closed choice becomes computable under a representation of points that makes the low points computable.A co-c.e. closed set may lack computable points but always contains a low point.Source: §1 · pp. 3–4
  • The paper also presents observations about the initial topology of the Turing jump operator, called the Π-topology by Joseph Miller.Source: §1 · p. 4

2 Weihrauch Reducibility

This section establishes the represented-space and reducibility framework used to compare computational tasks. It also defines operations, including products and parallelization, that organize Weihrauch degrees.

2 Weihrauch Reducibility

  • A represented space equips a set with a surjective, potentially partial map from Baire space, and a realizer computes a function through these representations.Computability and continuity transfer to represented-space functions through their realizers.Source: §2 · p. 4
  • Weihrauch reducibility compares multi-valued functions by computable preprocessing and postprocessing around a realizer of the problem being used.The induced equivalence classes form Weihrauch degrees, ordered by reducibility.Source: §2 · p. 5
  • Products solve two instances independently, while coproducts form a disjoint sum; for pointed and idempotent functions, coproduct and product are equivalent.Pointedness is required for the first reduction and coproduct idempotency for the last.Source: §2 · pp. 5–6
  • Parallelization solves countably many instances of a function, and finite parallelization allows a finite number of instances.Both operations are closure operators for the Weihrauch lattice.Source: §2 · p. 6

3 Closed Choice

Closed choice selects an arbitrary member of a nonempty closed set given its negative description. The section relates choice across spaces and shows that products can behave differently for finite and infinite spaces.

3 Closed Choice

  • Closed choice maps a negative description of a nonempty closed set to an arbitrary point in that set.The input enumerates the complement; the possible outputs are the set's points.Source: §3 · p. 7
  • Choice on a product space bounds the product of the separate choice operations: C_X ⊔ C_Y ≤W C_X × C_Y ≤W C_(X×Y).The reductions need not reverse in general.Source: §3 · p. 8
  • For finite discrete sets A and B with at least two elements each, C_A × C_B is strictly weaker than C_(A×B).The paper's alternative argument compares operation levels, with bounds n+k and (n+1)(k+1)-1 for the specified finite-choice operations.Source: §3 · pp. 8–9
  • A computable surjection with co-c.e. closed domain yields a reduction from choice on its codomain to choice on its domain.A computable surjection from A to A² also suffices for C_A to be idempotent.Source: §3 · pp. 9–10
  • Choice on N, Cantor space, Baire space, and N × Cantor space is idempotent, whereas closed choice need not be idempotent in general.The non-idempotence follows from the equivalence of binary choice with LLPO and LLPO's non-idempotence [7].Source: §3 · pp. 7, 10

4 Choice on Computable Metric Spaces

The section compares closed choice on computable metric spaces by compactness, local compactness, and embeddings. It identifies Euclidean choice with a product of natural-number and Cantor-space choice and gives a dichotomy for Polish spaces.

4 Choice on Computable Metric Spaces

  • For computable Polish spaces, choice reduces to Baire-space choice, and for computably compact spaces it reduces to Cantor-space choice.Computably compact computable metric spaces also admit a surjective computable representation from Cantor space.Source: §4 · pp. 11–12
  • A computable embedding with co-c.e. closed range yields a choice reduction; rich Polish spaces therefore have at least Cantor-space choice, with equivalence for nonempty compact spaces without isolated points.Every nonempty perfect computable Polish space is rich in the stated sense.Source: §4 · pp. 12–13
  • Choice on a computable Kσ-space reduces to the product of choice on N and Cantor space.Choice on N finds a compact piece intersecting the closed set, and Cantor-space choice selects a point there; the result also applies to R^k using the cubes [−n,n]^k.Source: §4 · p. 14
  • For every k ≥ 1, choice on R^k is Weihrauch-equivalent to choice on R and to C_N × C_{ {0,1}^N}.Source: §4 · p. 14
  • Topologically, every Polish-space choice principle lies at or below real-line choice or is equivalent to Baire-space choice.Thus no Polish-space choice degree lies strictly between those two degrees topologically.Source: §4 · p. 14
  • For the cited non-Kσ computable metric spaces, including R^N, C[0,1], and ℓ_p, choice is equivalent to Baire-space choice.The stated ℓ_p result holds for computable real p ≥ 1.Source: §4 · pp. 14–15
  • Choice on a computable sequence's range reduces to choice on N; for Q it is equivalent to natural-number choice under either stated representation.Source: §4 · p. 15
  • Choice on the irrational numbers is equivalent to Baire-space choice.The section identifies the irrationals with Baire space via their continued-fraction representation.Source: §4 · p. 15

5 Compact Choice, Quotients and Join-Irreducibility

Compact choice can be removed from computations of single-valued functions into computable metric spaces when another function is available. The section also shows that several closed-choice principles are join-irreducible, with coproduct and product having distinct strength.

Quotients

  • If single-valued f into a computable metric space satisfies f ≤W C_{0,1}^N × g, then f ≤W g.The proof represents f(x) as the singleton {f(x)} and uses the computable inverse of the singleton embedding into compact sets.Source: §5 · pp. 15–16
  • Single-valued f ≤W C_{0,1}^N into a computable metric space is computable, while f ≤W C_R implies f ≤W C_N.The first is identified as Corollary 8.8 from [7]; the second follows with Corollary 4.9.Source: §5 · p. 16

Join-Irreducibility

  • Join-irreducibility here means that if f is equivalent to a countable coproduct of functions, it is equivalent to one of them.For countably many functions, the authors note that the coproduct is not necessarily their supremum in computable Weihrauch reducibility.Source: §5 · pp. 16–17
  • C_N, C_{0,1}^N, C_NN, and C_R are join-irreducible.The criterion used is that restricting choice to any nonempty clopen subset of its domain preserves its Weihrauch degree; removing finitely many small open rational balls leaves enough space to simulate full choice.Source: §5 · p. 17
  • The coproduct of C_N and C_{0,1}^N is strictly below their product.The corollary also shows that the coproduct of two idempotent functions need not be idempotent.Source: §5 · p. 17

6 Unique Choice and Inversion

The section introduces unique closed choice and relates it to ordinary choice and inversion. It establishes inversion bounds for computable metric spaces, while noting that these bounds need not be optimal and depend on the represented space.

Unique Choice

  • Unique closed choice UC_X selects the unique point represented by a closed singleton in a represented Hausdorff space.It is the partial inverse of the map sending each point x to {x}.Source: §6 · p. 18
  • On the natural numbers, unique choice and ordinary closed choice have the same Weihrauch degree: UC_N ≡W C_N.The proof encodes a candidate for the chosen natural number through a negative description of a singleton.Source: §6 · p. 18
  • The paper conjectures that unique choice on Baire space has the same degree as ordinary Baire-space choice, UC_NN ≡W C_NN.It also states that lim ≤W UC_NN and that the cone below UC_NN is closed under composition, so UC_NN is not on any finite Borel-hierarchy level.Source: §6 · p. 19

Inversion

  • For computable metric spaces, the inverse of a computable map reduces to closed choice on its domain; if the map is injective, it reduces to unique choice.When the domain is computably compact, the inverse is weakly computable, and for an injective map it is computable; on a computable Kσ space, the corresponding bounds are C_R and C_N.Source: §6 · p. 20
  • The inversion bounds are not necessarily optimal, and the results do not hold for arbitrary represented spaces.For the identity from Cauchy-represented R to left-cut-represented R, the inverse is equivalent to lim and is not reducible to C_R; injective computable maps R→R can have computable inverses using additional properties such as connectedness.Source: §6 · pp. 20–21

7 Choice on Baire Space and Non-Deterministic Computability

The section characterizes computation with advice and finite mind changes through closed choice, then applies these characterizations to composition and effectively Borel functions. It also relates Cantor-space choice to weak computability and discusses the limits of representing limit computability by choice.

Advice and Independent Choice

  • The characterization of non-deterministic computability generalizes the advice-space formulation to subsets of Baire space.The paper notes that the formulation in implicitly uses full Baire space NN as its advice space.Source: §7 · pp. 21–22
  • For any advice space A⊆NN, f ≤W C_A exactly when f is non-deterministically computable with advice space A.The advice must include a successful option for each input, and every successful advice must produce a correct output.Source: §7 · pp. 21–22
  • If f ≤W C_A and g ≤W C_B, then f∘g ≤W C_{A×B}; this yields closure under composition and idempotency for several choice principles.The listed cases include C_N, C_{0,1}^N, C_NN, C_{N×{0,1}^N}, and hence C_R; the proof uses independently chosen advice for each function.Source: §7 · pp. 23–24

Baire-Space Choice

  • For computable Polish spaces X and Y, a single-valued f:X→Y satisfies f ≤W C_NN exactly when it is effectively Borel measurable.Effective Borel measurability is defined by an effective Σ1_1 graph; C_NN itself is not Borel measurable, since its domain corresponds to ill-founded trees and is Σ1_1-complete.Source: §7 · pp. 25–26

Finite Mind Changes

  • Computability with finitely many mind changes is equivalent to f ≤W C_N, and also to f ≤W lim_Δ.The discrete limit lim_Δ takes an eventually constant sequence to its eventual value; finite revision means the output may be erased and rewritten only finitely often.Source: §7 · pp. 26–27

Cantor-Space Choice

  • A function is weakly computable exactly when it is reducible to C_{0,1}^N, or non-deterministically computable with advice space {0,1}^N.The section identifies weak computability with the Cantor-space choice characterization.Source: §7 · p. 28

Limit Computability

  • The paper conjectures that no represented space has closed choice equivalent to lim, while parallelized natural-number choice characterizes limit-computable functions.It notes that limit-computable functions are not closed under composition, whereas the parallelized choice satisfies cC_N ≡W lim.Source: §7 · p. 28

8 A Uniform Low Basis Theorem

This section presents a uniform Low Basis Theorem for Cantor space, characterizes low computability via L = J⁻¹ ◦ lim, and extends low-solution results to computable Kσ spaces. It also examines composition properties of low computability, limit computability, and L.

8 A Uniform Low Basis Theorem

  • Uniformly, closed choice on Cantor space is low computable: from an enumeration of a nonempty compact set’s complement, one computes a sequence converging to the jump of a point in it.The resulting uniform theorem implies that every nonempty co-c.e. closed subset of Cantor space contains a low point.Source: §8 · pp. 30, 32
  • L is strictly above locally compact choice, strictly below lim, and L <_W L × L, so L is not idempotent.The strict upper bound follows because lim can map a computable input to a non-low output.Source: §8 · pp. 33–34
  • A multi-valued function is low computable exactly when it is strongly Weihrauch reducible to L = J^-1 ◦ lim.The equivalence identifies L as a characterization of low computability.Source: §8 · p. 34
  • Cantor-space choice and locally compact choice on N × Cantor space are cylinders.Source: §8 · p. 35
  • For computable Kσ spaces X, closed choice C_X is low computable and every nonempty co-c.e. closed subset contains a low point; this includes N, Cantor space, and R.Source: §8 · p. 35
  • Low computability includes functions computable with finitely many mind changes and weakly computable functions, and the Brouwer Fixed Point Theorem is low computable.The BFT result is a uniform version of the fact that each computable function on [0, 1]^n has a low fixed point.Source: §8 · pp. 35–36
  • If f is low computable and g is limit computable, then g ◦ f is limit computable; if both are low computable, then g ◦ f is low computable.Source: §8 · p. 36
  • The composition of two low computable functions is low computable.The section identifies low computable functions as the largest known class with the stability property stated in Proposition 8.16.Source: §8 · p. 36
  • A limit computable function composed with one computable with finitely many mind changes need not be limit computable.Source: §8 · p. 36
  • L is not closed under composition, so Theorem 8.10 cannot replace strict Weihrauch reducibility with ordinary Weihrauch reducibility.Source: §8 · p. 36

9 The Jump Topology

The section identifies the initial topology of the Turing jump with the Π-topology and studies its limit operation. It establishes how that operation compares computationally with other limit and choice principles, and derives properties of points and continuous maps in this topology.

The Π-topology

  • The initial topology of J is generated by the co-c.e. closed sets and is identical to the Π-topology.Convergence in the Π-topology means that the jumps of a sequence converge to the jump of its limit in Baire space.Source: §9 · p. 37

Limit operation

  • Theorem 9.7 states that limJ is strictly below L in strong Weihrauch reducibility, while Theorem 9.6 states that C{0,1}N is not Weihrauch reducible to limJ.Theorem 9.10 states that limJ and L are strongly Weihrauch equivalent with respect to some oracle.Source: §9 · pp. 40–41

Points limit computable in the jump

  • Every point limit computable in the jump is low, and every limit-computable 1-generic is limit computable in the jump.Non-computable points limit computable in the jump need not be 1-generic.Source: §9 · pp. 38, 41, 42

Limit operation

  • The limit operations satisfy lim_Δ <_W lim_J <_W lim.The second inequality is strict because Cantor-space choice is reducible to lim but not to lim_J.Source: §9 · pp. 40–41
  • With respect to some oracle, lim_J is strongly Weihrauch-equivalent to L = J^-1 ◦ lim.The section distinguishes this oracle-relative equivalence from the strict computational comparison.Source: §9 · pp. 40–41

Points limit computable in the jump

  • Points limit computable in the jump remain so under total computable functions, and they cannot compute diagonally non-computable functions.A non-computable point limit computable in the jump need not be 1-generic.Source: §9 · pp. 39, 42

The Π-topology

  • A singleton is clopen in the Π-topology exactly when it is co-c.e. closed in Baire space.Consequently, the set of computable points is open in the Π-topology, though not effectively so.Source: §9 · p. 43

The inverse of the jump

  • There is a total continuous F for which no continuous G satisfies FJ^-1 = J^-1G.Thus the inverse of J is not a topological jump operator.Source: §9 · pp. 43–44

10 Conclusions

The conclusion summarizes how closed choice for several spaces characterizes function classes. The table pairs singleton, natural-number, Cantor, and Baire space choice with computable, finitely mind-changing, weakly computable, and effectively Borel measurable functions, respectively.

Conclusions

  • The figure extends the results on closed choice in the Weihrauch lattice presented in [6, Figure 6].The accompanying text summarizes results in tables and figures.Source: §10 · p. 44, Figure 1 · p. 45
  • Closed choice on singleton, natural-number, Cantor, and Baire spaces corresponds respectively to computable, finitely mind-changing, weakly computable, and effectively Borel measurable functions.The table also gives the topological counterparts: continuous, piecewise continuous, upper semi-continuous compact-valued selectors, and Borel measurable, respectively.Source: §10 · pp. 44, 46
Loading 1002.2800v2…