Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T09:56:30.389Z Has data issue: false hasContentIssue false

WEIHRAUCH GOES BROUWERIAN

Published online by Cambridge University Press:  30 October 2020

VASCO BRATTKA
Affiliation:
FACULTY OF COMPUTER SCIENCE UNIVERSITÄT DER BUNDESWEHR MÜNCHEN NEUBIBERG, GERMANYDEPARTMENT OF MATHEMATICS & APPLIED MATHEMATICS UNIVERSITY OF CAPE TOWN CAPE TOWN, SOUTH AFRICA E-mail: Vasco.Brattka@cca-net.de
GUIDO GHERARDI
Affiliation:
DIPARTIMENTO DI FILOSOFIA E COMUNICAZIONE UNIVERSITÀ DI BOLOGNA BOLOGNA, ITALY E-mail: Guido.Gherardi@unibo.it
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it generates a total version of Weihrauch reducibility that is defined like the usual version of Weihrauch reducibility, but in terms of total realizers. From a logical perspective completion can be seen as a way to make problems independent of their premises. Alongside with the completion operator and total Weihrauch reducibility we need to study precomplete representations that are required to describe these concepts. In order to show that the parallelized total Weihrauch lattice forms a Brouwer algebra, we introduce a new multiplicative version of an implication. While the parallelized total Weihrauch lattice forms a Brouwer algebra with this implication, the total Weihrauch lattice fails to be a model of intuitionistic linear logic in two different ways. In order to pinpoint the algebraic reasons for this failure, we introduce the concept of a Weihrauch algebra that allows us to formulate the failure in precise and neat terms. Finally, we show that the Medvedev Brouwer algebra can be embedded into our Brouwer algebra, which also implies that the theory of our Brouwer algebra is Jankov logic.

Information

Type
Articles
Copyright
© The Association for Symbolic Logic 2020