Math 285D Spring 2022

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

What Is This Course About?

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 Schedule

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

Homework

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

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

Week 1

  1. 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)\)).

Week 2

  1. Show that \(\text{EC}_1 \nleq_{W} \text{SEP}\).
  2. 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\)?
  3. 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\).

Week 3

  1. 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.
  2. 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}\)?

Week 4

  1. 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\)?
  2. 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.

Week 5

  1. 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\).

Week 6

  1. 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\).

Week 7

  1. 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\).
  2. 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\).

Week 8

  1. 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}\).
  2. 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.
  3. 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\).

Week 9

  1. 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\).
  2. 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}\).

Week 10

  1. 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.

Open Questions

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

  1. 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\)?
  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\).
  3. 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?
  4. 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}\)?
  5. 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\).

Relevant Research Papers and Surveys

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

Surveys on Weihrauch Reducibility

Computable Analysis

Weihrauch Degrees of Problems from Computable Analysis

Choice principles

Effectivizing theorems from real analysis

Finding Nash equilibria

Other papers

Ramsey’s Theorem and Weihrauch Reducibility

Weihrauch Reducibility at the Level of ATR0

Reverse Math

Weihrauch Reducibility and Constructive Mathematics

Operations on the Weihrauch Degrees

Algebraic Structure of the Weihrauch Degrees

Medvedev, Muchnik, and Enumeration Reducibility

Wadge Reducibility

Continuous Reducibility

Martin’s Conjecture