Please use this identifier to cite or link to this item:
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.
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
ISSN: 2211-3568
DOI: 10.3233/com-180235
Appears in Collections:Staff Publications

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



Page view(s)

checked on Feb 2, 2023


checked on Feb 2, 2023

Google ScholarTM



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