Compositions of multivalued functions

Issue title: Dagstuhl Seminar on Measuring the Complexity of Computational Content 2018

Guest editors: Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone and Arno Pauly

Article type: Research Article

Authors: Goh, Jun Le^{; *}

Affiliations: Department of Mathematics, University of Wisconsin-Madison, Madison, WI, USA. junle.goh@wisc.edu

Correspondence: [*] Corresponding author. junle.goh@wisc.edu.

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.

Keywords: Weihrauch reducibility, compositional product, reduction game, step product

DOI: 10.3233/COM-180235

Journal: Computability, vol. 9, no. 3-4, pp. 231-247, 2020