Source-linked AI summary
Weihrauch Degrees, Omniscience Principles and Weak Computability
Vasco Brattka, Guido Gherardi
TL;DR
The paper develops Weihrauch reducibility as a framework for studying the computational content of multi-valued mathematical operations. It establishes structural results for the resulting degrees and applies them to omniscience principles, weak computability, and theorem equivalences.
Problem
The paper seeks foundations for classifying mathematical theorems by computational content and for studying how multi-valued operations can be transferred into one another.
Source: §1. Introduction · p. 2, §2. Weihrauch reducibility of… · p. 5Method
It defines Weihrauch reducibility for multi-valued functions on represented spaces via their realizers, then studies degree operations, parallelization, and omniscience principles.
Source: §1. Introduction · p. 3, §2. Weihrauch reducibility of… · p. 5, §9. Conclusions · p. 33Results
The degrees have the stated lattice structure and embeddings, while parallelized LLPO matches Weak König’s Lemma and Hahn-Banach; weakly computable operations are composition-closed and characterized by selectors on computable metric spaces.
Source: §1. Introduction · pp. 4–5, §9. Conclusions · p. 33Takeaways & Limitations
Single-valued weakly computable operations are computable in the ordinary sense, even though the operations used to obtain them may be discontinuous and noncomputable.
Source: §1. Introduction · p. 5The sum operation on parallelized Weihrauch degrees requires parallelized representatives and cannot be defined using arbitrary representatives.
Source: §4. Parallelization of Weihrauch degrees · p. 17
Abstract
from arXiv · showhide
In this paper we study Weihrauch reducibility for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice with the disjoint union of multi-valued functions as greatest lower bound operation. We prove that parallelization is a closure operator for this semi-lattice and the parallelized Weihrauch degrees even form a lattice with the product of multi-valued functions as greatest lower bound operation. We show that the Medvedev lattice and hence Turing degrees can be embedded into the parallelized Weihrauch lattice in a natural way. We study the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations. We prove that parallelized LLPO is equivalent to Weak K"onig's Lemma and hence to the Hahn-Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof that the class of weakly computable operations is closed under composition. This proof is based on a computational version of Kleene's ternary logic. Moreover, we characterize weakly computable operations on computable metric spaces as operations that admit upper semi-computable compact-valued selectors and we prove that any single-valued weakly computable operation is already computable in the ordinary sense.
§1. Introduction.
The paper lays foundations for classifying mathematical theorems by computational content using Weihrauch reducibility for multi-valued operations on represented spaces. It develops the degree structure and connects omniscience principles to weak computability and major theorems.
§1. Introduction.
- The paper aims to establish foundations for classifying mathematical theorems according to their computational content.It frames the study as part of a broader program and points to subsequent work classifying choice principles and theorems from analysis.Source: §1. Introduction · pp. 2, 5
- Weihrauch reducibility compares multi-valued operations on represented spaces through uniform computable translations between their realizers.The paper presents this framework as a tool for studying whether mathematical theorems can be continuously or computably transferred into each other.Source: §1. Introduction · pp. 2–3
- The Weihrauch degrees form a lower semi-lattice, with direct sums as greatest lower bounds.The product and direct-sum operations are monotone; direct sums require multi-valuedness because they need not preserve single-valuedness.Source: §1. Introduction · p. 3
- Parallelization is a closure operator, and the parallelized Weihrauch degrees form a lattice with products as least upper bounds.Parallelization takes countably many copies of a function in parallel.Source: §1. Introduction · pp. 3–4
- The Medvedev lattice embeds into the Weihrauch lattice preserving least and greatest upper bounds, while Turing degrees embed preserving least upper bounds.The embeddings require total continuous multi-valued operations for the Medvedev lattice, and total continuous single-valued functions for Turing degrees.Source: §1. Introduction · p. 4
- LPO is strictly Weihrauch reducible to LLPO, and parallelized LPO is complete for effectively Σ0 2-measurable operations.The paper treats LPO and LLPO as operations and characterizes their Weihrauch degrees.Source: §1. Introduction · p. 4
- The cone below parallelized LLPO is closed under composition, and parallelized LLPO has the same Weihrauch degree as Weak König’s Lemma and the Hahn-Banach Theorem.Operations reducible to parallelized LLPO are called weakly computable; compact choice is also stated to have the same degree.Source: §1. Introduction · p. 4
- On computable metric spaces, weakly computable operations are exactly those with upper semi-computable compact-valued selectors, and single-valued weakly computable operations are computable.The paper notes that this includes uniquely determined results obtained using operations that may be discontinuous and noncomputable.Source: §1. Introduction · p. 5
§2. Weihrauch reducibility of multi-valued operations.
This section defines Weihrauch reducibility for multi-valued functions on represented spaces through their realizers. It establishes basic order properties, invariance under equivalent representations, and the role of computable functions as a least degree under a domain condition.
§2. Weihrauch reducibility of multi-valued operations.
- A multi-valued function f is Weihrauch reducible to g when the set of realizers of f is reducible to the set of realizers of g.The set-based reduction uses fixed computable translations, with the input also available to the outer output translation.Source: §2. Weihrauch reducibility of… · p. 6
- Both ordinary and strong Weihrauch reducibility are preorders, and their induced equivalence relations define Weihrauch degrees.The section restricts attention to operations between a given set of represented spaces so that the collection under consideration is a set.Source: §2. Weihrauch reducibility of… · p. 6
- Ordinary Weihrauch reducibility is weaker than strong reducibility, and both preserve continuity and computability.The section motivates ordinary reducibility as more useful because strong reducibility can distinguish functions such as the identity and a constant function.Source: §2. Weihrauch reducibility of… · pp. 6–7
- Among functions whose domains contain a computable point, computable functions form the least Weihrauch degree.A computable point in the domain of the target function allows a fixed computable input to be supplied to it.Source: §2. Weihrauch reducibility of… · p. 7
- For Weihrauch reducibility with respect to an oracle, continuous functions form the least degree among functions with non-empty domains.This is the continuous counterpart of the computable least-degree result, which requires a computable point in the domain.Source: §2. Weihrauch reducibility of… · pp. 7–8
- Replacing the representations of the spaces with equivalent representations preserves Weihrauch and strong Weihrauch reductions.The section treats invariance under equivalent representations as important in computable analysis.Source: §2. Weihrauch reducibility of… · p. 8
§3. Product and sum of Weihrauch degrees.
The direct sum is the greatest lower bound for Weihrauch degrees, while products are monotone and provide common upper bounds. The operations also give the degrees distinct algebraic structure, with product-based cylindrification relating strong and ordinary reducibility.
- Products are monotone and give a common upper bound when both functions have a computable point in their domains, but need not give the least upper bound.Some functions are not equivalent to their product with themselves.Source: §3. Product and sum of Weihrauch degrees · pp. 9–10
- Cylindrification is a closure operator on strong Weihrauch degrees, and applying it yields ordinary Weihrauch degrees.Source: §3. Product and sum of Weihrauch degrees · p. 11
- The direct sum is the greatest lower bound under both ordinary and strong Weihrauch reducibility.Source: §3. Product and sum of Weihrauch degrees · p. 13
- Weihrauch degrees form a lower semi-lattice with direct sum as greatest lower bound; direct sum and product are monoids with neutral elements 0 and 1, respectively.Source: §3. Product and sum of Weihrauch degrees · p. 13
- Product preserves single-valuedness, whereas direct sum does not and therefore requires multi-valued functions to be meaningful.Source: §3. Product and sum of Weihrauch degrees · pp. 11, 13
§4. Parallelization of Weihrauch degrees.
The section treats parallelization as a closure operation on Weihrauch degrees and develops the resulting algebra of parallel degrees. These degrees form a lattice, with sums and products serving as its meet and join operations, respectively.
§4. Parallelization of Weihrauch degrees.
- Parallelization takes countably many copies of an operation and acts as a closure operator on Weihrauch degrees.It is idempotent: parallelizing an already parallelized operation does not change its degree.Source: §4. Parallelization of Weihrauch degrees · p. 14
- Parallel Weihrauch reducibility compares the parallelizations of two operations, and its equivalence classes are parallel Weihrauch degrees.Specifically, f is parallely Weihrauch reducible to g when the parallelization of f is Weihrauch reducible to the parallelization of g.Source: §4. Parallelization of Weihrauch degrees · p. 15
- Parallelization commutes with products, so the product of two parallel degrees is itself parallelizable.This permits products to be treated as an operation on parallel Weihrauch degrees.Source: §4. Parallelization of Weihrauch degrees · pp. 15–16
- Every parallelizable Weihrauch degree is idempotent, and the product of two operations is their least upper bound under parallel Weihrauch reducibility.The proof of the upper-bound property assumes each operation has at least one computable point in its domain.Source: §4. Parallelization of Weihrauch degrees · p. 16
- The sum of parallelized operations is parallelizable, making sum well-defined on parallel degrees only when parallelized representatives are used.The section does not prove that parallelization commutes with sums.Source: §4. Parallelization of Weihrauch degrees · pp. 16–17
- Parallel Weihrauch degrees form a lattice with direct sum as greatest lower bound and product as least upper bound.The direct-sum and product operations are idempotent monoids with neutral elements 0 and 1, respectively.Source: §4. Parallelization of Weihrauch degrees · p. 17
- Parallelization is not necessarily the supremum of an operation’s finite self-products, and ordinary Weihrauch degrees can distinguish finer differences.The paper points to Corollary 6.8 for the failure of that supremum expectation.Source: §4. Parallelization of Weihrauch degrees · p. 17
§5. Embedding of Turing degrees and Medvedev degrees.
The section represents Medvedev and Turing degrees within parallel Weihrauch degrees using multi-valued operations on Baire space. The Medvedev embedding preserves both bounds, while the Turing-degree embedding preserves least upper bounds.
§5. Embedding of Turing degrees and Medvedev degrees.
- Medvedev reducibility requires a computable map defined on the target set and mapping it into the source set; Turing reducibility is its singleton case.The paper uses this relationship to treat the Turing-degree embedding as a special case of the Medvedev embedding.Source: §5. Embedding of Turing degrees and… · p. 17
- For the Medvedev embedding, each set of Baire-space sequences is associated with a multi-valued function that has a computable realizer exactly when the set contains a computable member.The associated function is parallelizable.Source: §5. Embedding of Turing degrees and… · pp. 17–18
- The Medvedev lattice embeds into the parallel Weihrauch lattice while preserving both least upper and greatest lower bounds.The embedding is restricted to total continuous multi-valued functions on Baire space and the empty operation.Source: §5. Embedding of Turing degrees and… · p. 19
- The upper semi-lattice of Turing degrees embeds into the parallel Weihrauch lattice with least upper bounds preserved.This embedding uses total continuous single-valued functions on Baire space.Source: §5. Embedding of Turing degrees and… · p. 19
- The embeddings allow structural properties of the Medvedev lattice and Turing upper semi-lattice to transfer to the parallel Weihrauch lattice.The paper notes that this observation raises further research questions.Source: §5. Embedding of Turing degrees and… · p. 19
§6. Omniscience principles.
This section studies LPO and LLPO through Weihrauch reducibility and their measurable, computable, and weak-computability properties. It characterizes weak computability via compact choice, Weak König’s Lemma, and selectors, and examines composition, finite-product hierarchies, parallelization, strict separations, and real LLPO.
LPO and discontinuity
- Every discontinuous function F from a subset of Baire space to Baire space computes LPO under strong Weihrauch reducibility relative to some oracle.The proof uses a point of discontinuity and a computable characteristic function to recover LPO.Source: §6. Omniscience principles · pp. 19–20
Completeness
- The text states that f is Σ0_2-measurable iff f ≤W d LPO with respect to some oracle, and Σ0_2-computable iff f ≤W d LPO.Source: §6. Omniscience principles · p. 21
Mind changes
- LPO^(k+1) and LLPO^(k+1) each require exactly k+1 mind changes on a limit machine.The machines can compute them with at most k+1 mind changes, but not with k.Source: §6. Omniscience principles · p. 22
Finite products
- For all k ∈ N, LPO(k) <W LPO(k+1) and LLPO(k) <W LLPO(k+1); in particular, LPO and LLPO are not idempotent.Source: §6. Omniscience principles · p. 22
Parallelization
- Parallelized LPO is not the supremum of its finite products, and the section states that an analogous result holds for LLPO.Source: §6. Omniscience principles · p. 22
Composition and weak computability
- Operations reducible to parallelized LLPO are closed under composition, and such operations are called weakly computable.The closure result also holds for continuous Weihrauch reducibility with respect to an oracle.Source: §6. Omniscience principles · pp. 26–27
Omniscience principles
- LLPO is strongly reducible to LPO, but LPO and parallelized LPO are not Weihrauch reducible to parallelized LLPO.The negative results also hold with respect to an arbitrary oracle.Source: §6. Omniscience principles · pp. 27–28
Weak König’s Lemma
- Weak König’s Lemma is strongly Weihrauch-equivalent to parallelized LLPO, and Hahn–Banach has the same Weihrauch degree as both.Source: §8. Compact choice and Weak K˝onig’s… · pp. 28–29
Compact choice
- For every computable metric space X, compact choice CK(X) is strongly reducible to parallelized LLPO and is Weihrauch-equivalent to it when X is rich.Source: §8. Compact choice and Weak K˝onig’s… · p. 30
Selection
- A multi-valued operation into a computable metric space is weakly computable exactly when it has a computable compact-valued selector.Source: §8. Compact choice and Weak K˝onig’s… · p. 31
Weakly computable single-valued operations
- Every single-valued weakly computable operation into a computable metric space is computable in the ordinary sense.Source: §8. Compact choice and Weak K˝onig’s… · p. 32
Real LLPO
- Real LLPO is strongly Weihrauch-equivalent to LLPO.Source: §8. Compact choice and Weak K˝onig’s… · p. 32
§9. Conclusions.
The paper establishes lattice structure and degree embeddings for Weihrauch reducibility, then uses parallelized omniscience principles to characterize weak computability and its closure properties. It also points to a forthcoming classification of analysis theorems by Weihrauch degree.
§9. Conclusions.
- Weihrauch degrees form a lower semilattice under direct sum, while parallelized degrees form a lattice with product as least upper bound.The Medvedev lattice and the upper semilattice of Turing degrees embed into the parallelized Weihrauch lattice.Source: §9. Conclusions · p. 33
- Parallelized LPO is complete for limit-computable operations, while parallelized LLPO defines a composition-closed class of weakly computable operations.Single-valued weakly computable operations are computable in the ordinary sense.Source: §9. Conclusions · p. 33
- A forthcoming paper classifies Weihrauch degrees of analysis theorems, including the Intermediate Value, Baire Category, and Banach Inverse Mapping Theorems.The authors say this classification appears finer than other known classifications in constructive and reverse mathematics.Source: §9. Conclusions · p. 33