|国家预印本平台
首页|A topos for extended Weihrauch degrees

A topos for extended Weihrauch degrees

A topos for extended Weihrauch degrees

来源:Arxiv_logoArxiv
英文摘要

Weihrauch reducibility is a notion of reducibility between computational problems that is useful to calibrate the uniform computational strength of a multivalued function. It complements the analysis of mathematical theorems done in reverse mathematics, as multi-valued functions on represented spaces can be considered as realizers of theorems in a natural way. Despite the rich literature and the relevance of the applications of category theory in logic and realizability, actually there are just a few works starting to study the Weihrauch reducibility from a categorical point of view. The main purpose of this work is to provide a full categorical account to the notion of extended Weihrauch reducibility introduced by A. Bauer, which generalizes the original notion of Weihrauch reducibility. In particular, we present a tripos and a topos for extended Weihrauch degrees. We start by defining a new tripos, abstracting the notion of extended Weihrauch degrees, and then we apply the tripos-to-topos construction to obtain the desired topos. Then we show that the Kleene-Vesley topos is a topos of $j$-sheaves for a certain Lawvere-Tierney topology over the topos of extended Weihrauch degrees.

Samuele Maschio、Davide Trotta

计算技术、计算机技术

Samuele Maschio,Davide Trotta.A topos for extended Weihrauch degrees[EB/OL].(2025-05-13)[2025-07-01].https://arxiv.org/abs/2505.08697.点此复制

评论