Talk on the existence of connected components of graphs

This week I am attending a seminar at Dagstuhl on Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis. This post has slides from my talk and some blog-only remarks to expand on them.

As the title suggests, the main topics of the seminar are Reverse Mathematics and Weihrauch Reducibility. The collection of other participants is exceptional for the topic, with people from many areas of Classical and Constructive Reverse Mathematics and Weihrauch Reducibility, and it has been a very informative and productive meeting for me so far.

My talk was generally on the paper “On the existence of a connected component of a graph”, with Kirill Gura and Jeff Hirst, which appeared in Computability this year. A preprint is available on the arXiv. The slides are posted here on my blog.

The main question I wanted to emphasize in my talk was the (uncertain) relationship between Reverse Mathematics and Weihrauch Reducibility in the context of the amount of induction needed for a particular problem.

General background

Experts can skip this section.

In Reverse Mathematics, we formalize theorems in second-order arithmetic, and we see which axioms are required to prove the theorems over a weak axiom system. One part of this is to verify that the theorem is provable in the system in which it is supposed to be provable, which is not always obvious. The base system we use, called $\mathsf{RCA}_0$, corresponds roughly to computable mathematics. In the paper we also use a stronger subsystem $\mathsf{ACA}_0$ and an induction scheme $\text{I-}\Sigma^0_1$ that is not provable in $\mathsf{RCA}_0$.

The context of Weihrauch reducibility, we study problems, which are generally statements of the form “for each $X$ there is a $Y$ such that …”. These statements are known to be true; the “problem” is to produce a $Y$ for a given $X$, using a uniform computable procedure for all appropriate $X$. The input $X$ is called an instance of the problem, and the output $Y$ is a corresponding solution. A single instance may have multiple solutions, but the problem is only to produce one. Of course, if some instances of the problem have no computable solutions, then it cannot be solved computably, but we can get around that by reducing the problem to some even-more uncomputable problem.

The rigorous general definition of the appropriate notion of reducibility dates back to work of Klaus Weihrauch in the early 1990s. For problems related to principles from Reverse Mathematics, the definition is simpler. For our present purposes, a problem is just an arithmetical relation $\Theta(X,Y)$ on $\mathbb{N}^\mathbb{N} \times \mathbb{N}^\mathbb{N}$. In many cases, we know that $(\forall X)(\exists Y)\Theta(X,Y)$, but the domain of $\Theta$ does not have to be all of $\mathbb{N}^\mathbb{N}$. We say that a problem $\Theta(X,Y)$ is strong Weihrauch reducible to another problem $\Xi(X,Y)$, written $\Theta \leq_{sW} \Xi$, if there are computable functionals $F$ and $G$ such that, for all $X$, if $X$ is in the domain of $\Phi$ then $F(X)$ is in the domain of $\Xi$, and such that for any $Y$ such that $\Xi(F(X), Y)$, we also have $\Theta(X, G(Y))$. So the pair $(F,G)$ sort-of conjugates the problem $\Xi$ into the problem $\Theta$, although $F$ and $G$ need not be inverses. Two problems are strong Weihrauch equivalent if each can be reduced to the other; this induces the equivalence classes called strong Weihrauch degrees. There are many other closely related reducibility notions that are being actively studied, but I only need strong Weihrauch reducibility for this post.

A particular Weihrauch problem that does not arise in Reverse Mathematics is “closed choice for $\mathbb{N}$”, denoted $C_\mathbb{N}$. By definition, $C_N(p, n)$ holds if $p$ is a non-surjective function from $\mathbb{N}$ to $\mathbb{N}$ and $n(0)$ is a natural number not in the range of $p$. So the “problem” is to find such a number given $p$. Of course each $p$ in the domain has such an $n$, but we are asking for a uniform ability to find $n$ given $p$, which is a nontrivial request. So $C_\mathbb{N}$ has a nontrivial Weihrauch degree. The name comes from the idea that the range of $p$ is $\Sigma^{0,p}_1$, and is thus “open” in some sense, and we want an element of its complement.

Two examples

Here are two examples of relationships between Reverse Mathematics and Weihrauch degrees from my talk.

The first is from my paper with Gura and Hirst. We showed that the following statement is strongly Weihrauch equivalent to $C_\mathbb{N}$:

GC: Given $k \in \mathbb{N}$ and a countable graph with exactly $k$ connected components, compute the characteristic function of any one component. In other words, $\text{GC}(X,Y)$ holds if $\lambda n . X(n+1)$ is (the incidence function for) a countable graph with $k = X(0)$ connected components and $Y$ is the characteristic function of some component of the same graph.

We also showed in the paper that $\mathsf{RCA}_0$ is not strong enough to verify that, for all $k$, every instance of every GC has a solution, when the claim “has exactly $k$ connected components” is expressed as “among every set of $k+1$ vertices, at least two are connected by a path in the graph”. With this formalization, $\text{I-}\Sigma^0_2$ is necessary and sufficient that every instance of the problem has a solution. This might suggest that $C_\mathbb{N}$ is somehow related to $\text{I-}\Sigma^0_2$.

The second example comes from an older result of Hirst. Consider the Weihrauch problem

WPHP: Given $k \in \mathbb{N}$ and a sequence of sets $(A_0, \ldots, A_k)$, produce an upper bound for $\bigcup_{i \leq k} A_i$.

This is a weak form of the infinite pigeonhole principle. It is not difficult to show that WPHP is also strong Weihrauch equivalent to $C_\mathbb{N}$.

In the context of Reverse Mathematics, however, a well known theorem of Hirst shows that the induction principle $\text{B-}\Sigma^0_2$ is necessary and sufficient to verify that every instance of WPHP has a solution. Crucially for my purposes here, $\text{B-}\Sigma^0_2$ is strictly weaker than $\text{I-}\Sigma^0_1$.

Discussion of the examples

The examples show a phenomenon that was already known to occur: principles which are equivalent in Weihrauch degree may have different Reverse Mathematics strength. The converse can also occur. What is interesting to me is that the principles GC and WPHP differ only in the induction required to verify them. In general, Weihrauch reducibility has difficulty detecting issues like this, because from the Weihrauch perspective we only need to construct a solution when one already exists for a given instance of a problem. We don’t have to verify that a solution actually does exist.

This leads to the question:

Is there some variation of Weihrauch reducibility which is able to detect differences of induction?

Ideally, this might lead to a hierarchy of degrees, of some sort, which corresponds to the classical hierarchy of induction principles including $\text{I-}\Sigma^0_n$ and $\text{B-}\Sigma^0_n$ for all $n \in \mathbb{N}$. At the moment, it is completely unclear what the reducibility would look like. I had initially thought about looking at primitive recursive reductions instead of computable ones, but this turns out to make no difference, because the sort of reductions we are looking at in the examples can be taken to be primitive recursive already.

The issue of this possible link between Reverse Mathematics and Weihrauch Reducibility leads to a deeper and more philosophical question in foundations of mathematics. Suppose for the sake of argument that there is some order, some deeper organization, that underlies mathematical theorems. We know that this organization is reflected only partially in each of the various foundational programs (Set Theory, Reverse Mathematics, Weihrauch Reducibility, Constructive Reverse Mathematics, etc.) Is it possible, in principle, that these programs can converge in some way, so that their results can be seen as special cases of more general results, which better illuminate the underlying organization? That might appear to be the ideal outcome. Or are the various programs doomed to always show only separate aspects, never fully capturing the underlying organization?

This entry was posted in Research, Talks. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *