• 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