DocumentCode
728990
Title
Descriptive Set Theory in the Category of Represented Spaces
Author
Pauly, Arno ; De Brecht, Matthew
Author_Institution
Clare Coll., Univ. of Cambridge, Cambridge, UK
fYear
2015
fDate
6-10 July 2015
Firstpage
438
Lastpage
449
Abstract
We propose to extend descriptive set theory (DST) beyond its traditional setting of Polish spaces to the represented spaces. There, we can reformulate DST in terms of endofunctors on the categories of represented spaces and computable or continuous functions. In particular, this approach satisfies the demand for a uniform approach to both classic and effective DST -- computability follows naturally from the setting, rather than having to be explicitly demanded. The previous endeavour to extend DST to the Quasi-Polish spaces is subsumed by this work. In several cases the category-theoretic setting enables new, very succinct proofs, and sheds a new light on why certain results are true. The framework lets us make formal some natural questions not easily approachable by traditional methods.
Keywords
category theory; computability; set theory; DST; Polish spaces; category-theoretic setting; computability; computable function; continuous function; endofunctors; extend descriptive set theory; quasipolish spaces; represented spaces; Complexity theory; Computer science; Density estimation robust algorithm; Extraterrestrial measurements; Set theory; Topology; computable analysis; descriptive set theory; realizability; topos theory;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
Conference_Location
Kyoto
ISSN
1043-6871
Type
conf
DOI
10.1109/LICS.2015.48
Filename
7174902
Link To Document