**Introduction to Weihrauch Reducibility in Computability Theory and Set Theory**

**Instructor:** Patrick Lutz

**Email:** pglutz “at” ucla.edu

**Lectures:** MWF 12-12:50 pm, MS 6201

This course is organized around the concept of Weihrauch reducibility. The core idea is that many reducibilities studied in computability theory and set theory can be seen as variations on Weihrauch reducibility. If we interpret “variation” liberally enough, this is trivially true so the (slightly) more precise claim is that many of these reducibilites retain something of the flavor of Weihrauch reducibility. Among these reducibilities are Medvedev and Muchnik reducibility, computable reducibility, Wadge reducibility, continuous reducibility and, of course, Weihrauch reducibility itself.

Throughout the course, we will explore each of these reducibilities. We will begin with an introduction to Weihrauch reducibility and some background on computable analysis. We will then use Weihrauch reducibility to compare various computational problems from computable analysis, combinatorics and reverse math. We will also discuss operations on computational problems and the algebraic structure of the Weihrauch degrees. Next we will discuss Medvedev and Muchnik reducibility as well as the enumeration degrees and the continuous degrees.

In the second half of the course, we will turn to set theory. We will begin with an introduction to Wadge reducibility and then move on to continuous reducibility. We will cover topics such as the Solecki dichotomy, the decomposability conjecture, and Martin’s conjecture. Along the way, we will see several interesting open questions.

**Lecture 1: Introduction to Weihrauch reducibility**- Definition of Weihrauch reducibility, variations on Weihrauch reducibility and some examples

*References:*Course notes by Jun Le Goh, Weihrauch Complexity in Computable Analysis **Lecture 2: Introduction to computable analysis**- Definition of computable real numbers and computable functions on the real numbers

*References:*Computability in Analysis and Physics, Computable Analysis, A Simple Introduction to Computable Analysis **Lecture 3: More computable analysis**- Comparing representations of the real numbers

*References:*Weihrauch Complexity and the Hagen School of Computable Analysis, The Degrees of Discontinuity of Some Translators Between Representations of the Real Numbers **Lecture 4: Weihrauch degrees of translation problems**- Computing the Weihrauch degrees of translating between different representations of real numbers

*References:*Weihrauch Complexity and the Hagen School of Computable Analysis, The Degrees of Discontinuity of Some Translators Between Representations of the Real Numbers **Lecture 5: Weihrauch degrees of choice principles**- Comparing Weihrauch degrees of choice principles on different computable metric spaces

*References:*Closed Choice and a Uniform Low Basis Theorem **Lecture 6: Weihrauch degree of the intermediate value theorem**- Computing the Weihrauch degrees of finding zeros of various functions

*References:*Effective Choice and Boundedness Principles in Computable Analysis, see also section 1.3 in these notes from a class by Jun Le Goh **Lecture 7: Weihrauch degree of Brouwer’s fixed point theorem**- Computing the Weihrauch degree of finding a fixed point of a continuous function \([0,1]^n\to [0,1]^n\)

*References:*Connected Choice and the Brouwer Fixed Point Theorem and Effective Choice and Boundedness Principles in Computable Analysis **Lecture 8: More about Brouwer’s fixed point theorem**- Start of the proof that \(\text{WKL} \leq_W \text{CC}_{[0,1]^2}\)

*References:*Connected Choice and the Brouwer Fixed Point Theorem **Lecture 9: Loose ends**- Finishing the discussion of \(\text{BFT}_n\) and correcting some mistakes.

*References:*Connected Choice and the Brouwer Fixed Point Theorem **Lecture 10: The structure of the Weihrauch degrees**- Algebraic operations on and properties of the Weihrauch degrees

*References:*Weihrauch Complexity in Computable Analysis **Lecture 11: Parallel and sequential repetition**- The squashing theorem and a characterization of the diamond operator

*References:*On Uniform Relationships Between Combinatorial Problems and A Note on the Diamond Operator **Lecture 12: Westrick’s theorem**- Finishing the proof that \(I \leq_W F\) and \(F \star G \leq_W F\) implies \(G^\diamond \leq_W F\)

*References:*A Note on the Diamond Operator **Lecture 13: Reverse math and Ramsey’s theorem**- Introduction to reverse math and proof of Ramsey’s theorem

*References:*Slicing the Truth, chapter 4 and section 6.1 **Lecture 14: Ramsey’s theorem, \(\text{ACA}_0\) and \(\text{WKL}_0\)**- \(\text{RT}^n_k \vdash \text{ACA}_0\) for all \(n \geq 3\) and \(\text{WKL}_0 \nvdash \text{RT}^2_2\)

*References:*Slicing the Truth, section 6.2 **Lecture 15: More on Ramsey’s theorem for pairs**- Finishing the proof that \(\text{WKL}_0 \nvdash \text{RT}^2_2\) and decomposition of \(\text{RT}^2_2\) into \(\text{COH}\) and \(\text{SRT}^2_2\)

*References:*Slicing the Truth, section 6.4 and 6.5 **Lecture 16: Liu’s theorem**- Proof that \(\text{SRT}^2_2\) does not imply \(\text{WKL}_0\) over \(\text{RCA}_0\), following a proof by Monin and Patey

*References:*Pigeons Do Not Jump High, section 5. For Liu’s original proof see either \(\text{RT}^2_2\) does not imply \(\text{WKL}_0\) or the appendix of Slicing the Truth **Lecture 17: Medvedev, Muchnik and enumeration degrees**- Introduction to the Medvedev, Muchnik and enumeration degrees

**Lecture 18: Continuous degrees and Miller’s theorem**- Miller’s answer to the question of whether every continuous function has a representative of least Turing degree

*References:*Degrees of Unsolvability of Continuous Functions **Lecture 19: Introduction to Wadge reducibility**- The least discontinuous function in the Weihrauch degrees and proof that the Wadge degrees are (almost) linearly ordered

*References:*Classical Descriptive Set Theory, section 21.E. See also this blog post by Bill Wadge about the original motivation for defining Wadge reducibility **Lecture 20: More on Wadge reducibility**- Proof that the Wadge degrees are well-founded

*References:*Classical Descriptive Set Theory, section 21.E **Lecture 21: Background on the hyperarithmetic, Baire and Borel hierarchies**- Definition of jump hierarchies, basic facts about them and connections to the Baire and Borel hierarchies

**Lecture 22: The parallelized continuous strong Weihrauch degrees**- Every non-constant Borel function is equivalent to an iterate of the jump under parallelized continuous strong Weihrauch reducibility

*References:*Three Topological Reducibilities for Continuous Functions and Topological Reducibilities for Discontinuous Functions and Their Structures **Lecture 23: Non-uniform continuous Weihrauch reducibility**- Statement of the Solecki dichotomy and generalized Solecki dichotomy and its application to classifying the non-uniform continuous strong Weihrauch degrees of functions

*References:*These notes **Lecture 24: The Solecki dichotomy and the Posner-Robinson theorem**- Proof of a weak version of the Solecki dichotomy from the Posner-Robinson theorem and proof of the Posner-Robinson theorem using Kumabe-Slaman forcing

**Lecture 25: More about the Solecki dichotomy**- More determinacy proofs of statements around the Solecki dichotomy

**Lecture 26: Weihrauch reducibility and Martin’s conjecture**- The connection between structure theorems for continuous Weihrauch reducibility and Martin’s conjecture

**Lecture 27: The structure of continuous strong Weihrauch reducibility**- Simple observations about the structure of functions on Baire space under continuous strong Weihrauch reducibility

**Lecture 28: The structure of continuous functions**- Carroy’s analysis of the structure of continuous functions with countable range under continuous strong Weihrauch reducibility

*References:*A Quasi-Order on Continuous Functions

All undergraduate students enrolled in the course are expected to complete the following coursework.

- First, solve at least one homework problem per week. At least 4 of these should be handed in by the end of the fifth week of classes and the rest should be handed in by Wednesday of finals week.
- Second, read one or more papers on a course-related topic of your choosing and give a presentation about them to me (and, optionally, to the class). This should be completed by the end of the last week of classes. Please let me know what paper you plan to read by the end of the seventh week of classes. If you have trouble picking a paper, I am happy to make suggestions.

Graduate students are encouraged to try to solve the homework problems but do not need to turn anything in.

- Let \(f \colon [0,1] \to \mathbb{R}\) be a computable function. Show that \(\max(f)\) is a computable real number, and also give an example to show that there may be no computable real at which \(f\) attains this maximum value (i.e. there may be no computable real \(x\) such that \(f(x) = \max(f)\)).

- Show that \(\text{EC}_1 \nleq_{W} \text{SEP}\).
- Define \(\text{EC}_2\) to be the following problem: given a function \(f \colon \mathbb{N} \to \mathbb{N}\) such that \(|\mathbb{N} \setminus \text{range}(f)| \leq 2\), find the characteristic function of \(\text{range}(f)\). Is \(\text{EC}_2 \leq_W \text{EC}_1\)?
- In class we showed that if \(F \colon \omega^\omega \to \omega^\omega\) is a single-valued partial function and \(G\) is any problem such that \(F \leq_W \text{WKL}\times G\) then \(F \leq_W G\). Show that this still holds if \(F \colon X \to Y\) is a single-valued function between a represented space \(X\) and a computable metric space \(Y\).

- Recall that \(\text{C}_\mathbb{N} \nleq_W \text{C}_{[0,1]}\) and hence \(\text{C}_\mathbb{N} \nleq_W \text{CC}_{[0,1]}\). Show that \(\text{CC}_{[0,1]} \nleq_W \text{C}_\mathbb{N}\) and hence \(\text{CC}_{[0,1]}\) and \(\text{C}_\mathbb{N}\) are incomparable.
- In class we defined a problem \(\text{IVT}\) using a form of the intermediate value theorem that states that if \(f \colon [0,1] \to \mathbb{R}\) is a continuous function such that \(f(0)\cdot f(1) < 0\) then \(f\) has a zero. However, sometimes this theorem is instead stated with the weaker hypothesis that \(f(0)\cdot f(1) \leq 0\). It is clear that these two theorems are equivalent. Are the corresponding problems Weihrauch equivalent? Formally, define \(\widetilde{\text{IVT}}\) to be the following problem: given a description of a continuous function \(f \colon [0,1] \to \mathbb{R}\) such that \(f(0)\cdot f(1) \leq 0\), find a description of some \(x \in [0,1]\) such that \(f(x) = 0\). Is \(\widetilde{\text{IVT}} \equiv_W \text{IVT}\)?

- In class we showed that if \(I \leq_W F\) and \(F\star G \leq_W F\) then \(G^\diamond \leq_W F\). Suppose that we are instead given that \(I \leq_W F\) and \(G\star F \leq_W F\). Can we still conclude that \(G^\diamond \leq_W F\)?
- In class we proved the following: if \(F\times G \leq_W F\), \(\text{dom}(F) = \omega^\omega\) and \(F\) is finitely tolerant then \(\widehat{G} \leq_W F\). Find an appropriate definition of “finitely tolerant” such that the following holds: if \(F \times G \leq_{sW} F\), \(\text{dom}(F) = 2^\omega\) and \(F\) is finitely tolerant then \(\widehat{G} \leq_{sW} F\). Recall that \(\leq_{sW}\) denotes strong Weihrauch reducibility.

- We showed in class that \(\text{LIM} \leq_W \text{RT}^3_2\) (and hence \(\text{J} \leq_W \text{RT}^3_2\)). Show that for all \(n\), \(\text{LIM}\circ \ldots \circ \text{LIM} \leq_W \text{RT}^{n + 2}_2\) where the term on the left denotes the \(n\)-fold composition of \(\text{LIM}\) with itself.

*Hint:*If \(c = \text{LIM}(p)\) is a 2-coloring of length \(n\)-tuples, show how to use \(p\) to compute a 2-coloring of length \((n + 1)\)-tuples \(\widetilde{c}\) such that infinite homogeneous sets for \(\widetilde{c}\) are also homogeneous for \(c\).

- Show that there is a non-total enumeration degree. Recall that \(A\) has total enumeration degree if there is some \(B\) such that \(A \equiv_e B\oplus B^c\).

*Hint:*Try to prove the following stronger statement. There is some non-c.e. \(A\) such that if \(B\oplus B^c \leq_e A\) then \(B \equiv_T 0\).

- Let \(A\) be the set of all \(x \in \omega^\omega\) such that some number appears infinitely many times in \(x\) and let \(B\) be the set of all \(x \in \omega^\omega\) such that there are infinitely many numbers, each of which appears infinitely many times in \(x\). Show that \(B \nleq_{\text{Wadge}} A\).
- Show that \(\text{AD}\) implies \(\text{CC}_\mathbb{R}\). Recall that \(\text{CC}_\mathbb{R}\) is “countable choice for sets of real numbers,” i.e. the assertion that for all families \(\langle X_n \rangle_{n \in \omega}\) of nonempty sets \(X_n \subseteq \omega^\omega\), there is a choice function \(f \colon \omega \to \omega^\omega\) such that for all \(n\), \(f(n) \in X_n\).

- In class we saw that the Borel functions are linearly ordered by parallelized continuous strong Weihrauch reducibility. This can also be shown for all functions under \(\text{AD}\). Prove that this fails with determinacy. That is, show (in \(\text{ZFC}\)) that there are functions \(f\) and \(g\) such that \(\widehat{f} \nleq^c_{sW} \widehat{g}\) and \(\widehat{g} \nleq^c_{sW} \widehat{f}\).
- Show that even without determinacy, we can still prove some of the same results that we proved with determinacy. In particular prove the following (in \(\text{ZFC}\)): for any function \(f \colon \omega^\omega \to \omega^\omega\) either \(f \leq^c_{sW} \text{Id}\) or \(J \leq^c_{sW} \widehat{f}\).

*Hint:*Use Grilliot’s trick. - Modify the proof from class of the weak version of the Solecki dichotomy to prove the following: for every Borel function \(f\), either \(f \leq^{c, nu}_{sW} \text{Id}\) or \(J \leq^{c}_{W} f\).

- Show that if \(A \subseteq 2^\omega\) is a Borel Turing invariant set then either \(A\) contains a cone or \(A\) is disjoint from a cone. Recall that Turing invariant means that for any \(x \equiv_T y\), \(x \in A \iff y \in A\).
- Suppose \(f, g \colon 2^\omega \to 2^\omega\) are two uniformly Turing-order-preserving functions such that \(f, g \geq_M \text{Id}\). Show that \(f \leq_M g\) if and only if \(\widehat{f} \leq^c_{sW} \widehat{g}\).

- Show that there are functions \(f, g \colon 2^\omega \to 2^\omega\) such that neither \(f\) nor \(g\) are continuous, \(f, g \leq^c_{sW} J\), \(f\) can be written as a countable union of constant functions with closed domains and \(g\) can be written as a countable union of constant functions with \(\mathbf{\Pi}^0_2\) domains but
*not*a countable union of functions with closed domains.

Here I will list interesting open questions connected to the course content.

- Suppose \(X\) is a computable metric space. Define \(\text{PCC}_{X}\) to be the following problem: given a description of an open set \(A \subset X\) such that \(X\setminus A\) is nonempty and path connected, find a description of a point \(x \in X \setminus A\). It is known that \(\text{WKL} \leq_W \text{PCC}_{[0,1]^n}\) for all \(n \geq 3\). Does this also hold for \(n = 2\)?
- What is the first order part of \(\text{RT}^2_2\)? It is known that it is conservative over \(I\Sigma^0_2\) (and hence any first order statement provable from \(\text{RT}^2_2\) is provable from \(I\Sigma^0_2\)), that it proves \(B\Sigma^0_2\) and that it does not prove \(I\Sigma^0_2\). But it is not known whether it is conservative over \(B\Sigma^0_2\), which would imply that its first order consequences are exactly the first order consequences of \(B\Sigma^0_2\).
- Can the full Solecki dichotomy be proved from the Posner-Robinson theorem? Short of that, is there a straightforward determinacy proof of the Solecki dichotomy?
- In class we saw that on the Borel functions, \(\leq^{c, nu}_{sW}\) is a prewellorder. Is this true for all functions under \(\text{AD}\)?
- Is \(\leq^c_{sW}\) a well-quasi-order on continuous functions \(\omega^\omega \to \omega^\omega\)? Note that Carroy has shown it
*is*a well-quasi-order on functions with domain \(2^\omega\).

Here is a list of books, surveys and papers relevant to the topic of the course. This list will be updated throughout the course.

- Weihrauch Complexity in Computable Analysis by Vasco Brattka, Guido Gherardi and Arno Pauly
- Notes from a course on Weihrauch reducibility by Jun Le Goh
- An Update on Weihrauch Complexity, and Some Open Questions by Arno Pauly

- Computability in Analysis and Physics by Marian Pour-El and Ian Richards
- Computable analysis by Klaus Weihrauch
- A Simple Introduction to Computable Analysis by Klaus Weihrauch
- Weihrauch Complexity and the Hagen School of Computable Analysis by Vasco Brattka
- Computability and Analysis, A Historical Approach by Vasco Brattka
- A Tutorial on Computable Analysis by Vasco Brattka, Peter Hertling and Klaus Weihrauch

- Closed Choice and Uniform Low Basis Theorem by Vasco Brattka, Matthew de Brecht and Arno Pauly
- Effective Choice and Boundedness Principles in Computable Analysis by Vasco Brattka and Guido Gherardi
- Connected Choice and the Brouwer Fixed Point Theorem by Vasco Brattka, Stephane Le Roux, Joseph Miller and Arno Pauly
- Completion of Choice by Vasco Brattka and Guido Gherardi
- Finite Choice, Convex Choice and Finding Roots by Stephane Le Roux and Arno Pauly
- Convex Choice, Finite Choice and Sorting by Takayuki Kihara and Arno Pauly
- Overt Choice by Matthew de Brecht, Arno Pauly and Mathias Schroder

- The Bolzano-Weierstrass Theorem is the Jump of Weak Konig’s Lemma by Vasco Brattka, Guido Gherardi and Alberto Marcone
- Effective Aspects of Hausdorff and Fourier Dimension by Alberto Marcone and Manlio Valenti
- Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees by Eike Neumann
- How Constructive is Constructing Measures? by Arno Pauly and Willem Fouche

- How Incomputable is Finding Nash Equilibria by Arno Pauly
- Dividing by Zero—How Bad Is It, Really? by Takayuki Kihara and Arno Pauly
- The Weihrauch Degree of Finding Nash Equilibria in Multiplayer Games by Tonicha Crook and Arno Pauly
- Weihrauch Degrees of Finding Equilibria in Sequential Games by Stephane Le Roux and Arno Pauly

- Weihrauch Degrees, Omniscience Principles and Weak Computability by Vasco Brattka and Guido Gherardi
- Comparing Representations for Function Spaces in Computable Analysis by Arno Pauly and Florian Steinberg
- Weihrauch-Completeness for Layerwise Computability by Arno Pauly, Willem Fouche and George Davie
- The Discontinuity Problem by Vasco Brattka
- Projection Operators in the Weihrauch Lattice by Guido Gherardi, Alberto Marcone and Arno Pauly
- Computable Dyadic Subbases and \(T^\omega\)-representations of Compact Sets by Arno Pauly and Hideki Tsuiki

- Ramsey’s Theorem and Recursion Theory by Carl Jockusch
- On the Strength of Ramsey’s Theorem by David Seetapun and Theodore Slaman
- On the Strength of Ramsey’s Theorem for Pairs by Peter Cholak, Carl Jockusch and Theodore Slaman
- \(\text{RT}^2_2\) Does Not Imply \(\text{WKL}_0\) by Lu Liu
- On the Uniform Computational Content of Ramsey’s Theorem by Vasco Brattka and Tahina Rakotoniaina
- Ramsey’s Theorem and Products in the Weihrauch Degrees by Damir Dzhafarov, Jun Le Goh, Denis Hirschfeldt, Ludovic Patey and Arno Pauly
- On Uniform Relationships Between Combinatorial Problems by Francois Dorais, Damir Dzhafarov, Jeffry Hirst, Joseph Mileti and Paul Shafer
- Strong Reductions Between Combinatorial Principles by Damir Dzhafarov
- Ramsey’s Theorem for Singletons and Strong Computable Reducibility by Damir Dzhafarov, Ludovic Patey, Reed Solomon and Linda Westrick
- An Inside/Outside Ramsey Theorem and Recursion Theory by Marta Fiori-Carones, Paul Shafer and Giovanni Solda
- Coding Power of Product of Partitions by Lu Liu
- The Open and Clopen Ramsey Theorems in the Weihrauch Lattice by Alberto Marcone and Manlio Valenti

- Searching for the Analogue of ATR_0 in the Weihrauch Lattice by Takayuki Kihara, Alberto Marcone and Arno Pauly
- Some Computability Theoretic Reductions Between Principles Around ATR
_{0}by Jun Le Goh - Finding Descending Sequences Through Ill-Founded Linear Orders by Jun Le Goh, Arno Pauly and Manlio Valenti
- A Comparison of Various Analytic Choice Principles by Paul-Eliot Angles D’Auriac and Takayuki Kihara
- On Some Topics Around Wadge Rank \(\omega_2\) by Takayuki Kihara

- Subsystems of Second Order Arithmetic by Steve Simpson
- Slicing the Truth by Denis Hirschfeldt

- Instance Reducibility and Weihrauch Degrees by Andrej Bauer
- Degrees of Incomputability, Realizability and Constructive Reverse Mathematics by Takayuki Kihara
- The Characterization of Weihrauch Reducibility in Systems Containing \(\text{E}\)-\(\text{PA}^\omega + \text{QF}\)-\(\text{AC}^{0, 0}\) by Patrick Uftring
- Weihrauch and Constructive Reducibility Between Existence Statements by Makoto Fujiwara
- Using Ramsey’s Theorem Once by Jeffry Hirst and Carl Mummert

- Compositions of Multivalued Functions by Jun Le Goh
- A Note on the Diamond Operator by Linda Westrick
- Algebraic Properties of the First-Order Part of a Problem by Giovanni Solda and Manlio Valenti
- Reduction Games, Provability and Compactness by Damir Dhzafarov, Denis Hirschfeldt and Sarah Reitzes
- A Galois Connection Between Turing Jumps and Limits by Vasco Brattka
- Stashing and Parallelization Pentagons by Vasco Brattka

- The Degree Structure of Weihrauch Reducibility by Kojiro Higuchi and Arno Pauly
- On the Algebraic Structure of the Weihrauch Degrees by Vasco Brattka and Arno Pauly
- Weihrauch Goes Brouwerian by Vasco Brattka and Guido Gherardi
- Joins in the Strong Weihrauch Degrees by Damir Dhzafarov
- Game Characterizations and Lower Cones in the Weihrauch Degrees by Hugo Nobrega and Arno Pauly

- A Survey of Muchnik and Medvedev Degrees by Peter Hinman
- Cardinal Invariants, Non-Lowness Classes and Weihrauch Reducibility by Noam Greenberg, Rutger Kuyper and Dan Turetsky
- Muchnik Degrees and Cardinal Characteristics by Benoit Monin and Andre Nies
- Degrees of Unsolvability of Continuous Functions by Joe Miller
- Enumeration Degrees and Non-Metrizable Topology by Takayuki Kihara, Keng Meng Ng and Arno Pauly

- A Quasi-Order on Continuous Functions by Raphael Carroy
- Three Topological Reducibilities for Continuous Functions by Adam Day, Rod Downey and Linda Westrick
- Topological Reducibilities for Discontinuous Functions and Their Structures by Takayuki Kihara
- Decomposing Borel Sets and Functions and the Structure of Baire Class 1 Functions by Slawomir Solecki
- A Dichotomy for Borel Functions by Marcin Sabok
- A Dichotomy for \(\sigma\)-Baire Class \(\alpha\) Functions slides from a talk by Andrew Marks