Compositions of multivalued functions

Abstract

In reverse mathematics, one sometimes encounters proofs which invoke some theorem multiple times in series, or invoke different theorems in series. One example is the standard proof that Ramsey’s theorem for 2 colors implies Ramsey’s theorem for 3 colors. A natural question is whether such repeated applications are necessary. Questions like this can be studied under the framework of Weihrauch reducibility. For example, one can attempt to capture the notion of one multivalued function being uniformly reducible to multiple instances of another multivalued function in series. There are three known ways to formalize this notion: the compositional product, the reduction game, and the step product. We clarify the relationships between them by giving sufficient conditions for them to be equivalent. We also show that they are not equivalent in general.