Completion of choice

Annals of Pure and Applied Logic 172 (3):102914 (2021)
  Copy   BIBTEX


We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete.



    Upload a copy of this work     Papers currently archived: 91,102

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On countable choice and sequential spaces.Gonçalo Gutierres - 2008 - Mathematical Logic Quarterly 54 (2):145-152.
How to Understand the Completion of Art.Patrick Grafton-Cardwell - 2020 - Journal of Aesthetics and Art Criticism 78 (2):197-208.
Real numbers and other completions.Fred Richman - 2008 - Mathematical Logic Quarterly 54 (1):98-108.
D -completions and the d -topology.Klaus Keimel & Jimmie D. Lawson - 2009 - Annals of Pure and Applied Logic 159 (3):292-306.
Completion time and performance on multiple-choice and essay tests.Paul W. Foos - 1989 - Bulletin of the Psychonomic Society 27 (2):179-180.
Closed choice and a uniform low basis theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.
Amodal completion and knowledge.Grace Helton & Bence Nanay - 2019 - Analysis 79 (3):415-423.
Filling-in: One or many?Luiz Pessoa, Evan Thompson & Alva Noë - 2001 - Behavioral and Brain Sciences 24 (6):1137-1139.
Pollock on Rational Choice and Trying.Peter K. Mcinerney - 2006 - Philosophical Studies 129 (2):253-261.


Added to PP

19 (#717,158)

6 months
5 (#366,001)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Weihrauch Goes Brouwerian.Vasco Brattka & Guido Gherardi - 2020 - Journal of Symbolic Logic 85 (4):1614-1653.
The fixed-point property for represented spaces.Mathieu Hoyrup - 2022 - Annals of Pure and Applied Logic 173 (5):103090.
The Discontinuity Problem.Vasco Brattka - 2023 - Journal of Symbolic Logic 88 (3):1191-1212.

View all 7 citations / Add more citations