Please use this identifier to cite or link to this item: https://doi.org/10.3233/com-180235
Title: Compositions of multivalued functions
Authors: Goh, Jun Le 
Keywords: Weihrauch reducibility
compositional product
reduction game
step product
Issue Date: 3-Aug-2020
Publisher: IOS Press
Citation: Goh, Jun Le (2020-08-03). Compositions of multivalued functions. Computability 9 (3-4) : 231-247. ScholarBank@NUS Repository. https://doi.org/10.3233/com-180235
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.
Source Title: Computability
URI: https://scholarbank.nus.edu.sg/handle/10635/226817
ISSN: 2211-3568
2211-3576
DOI: 10.3233/com-180235
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
goh_compositions.pdf427.02 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

48
checked on Feb 2, 2023

Download(s)

3
checked on Feb 2, 2023

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.