No Cover Image

Conference Paper/Proceeding/Abstract 981 views 264 downloads

Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)

Arno Pauly Orcid Logo

Mathematical Foundations of Computer Science 2015, Volume: 9234, Pages: 407 - 418

Swansea University Author: Arno Pauly Orcid Logo

Check full text

DOI (Published version): 10.1007/978-3-662-48057-1_32

Abstract

While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of com...

Full description

Published in: Mathematical Foundations of Computer Science 2015
ISBN: 978-3-662-48056-4 978-3-662-48057-1
ISSN: 0302-9743 1611-3349
Published: Berlin Springer 2015
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa36019
first_indexed 2017-10-11T13:17:32Z
last_indexed 2023-01-11T14:10:50Z
id cronfa36019
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-12-05T12:51:12.2149837</datestamp><bib-version>v2</bib-version><id>36019</id><entry>2017-10-11</entry><title>Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2017-10-11</date><deptcode>MACS</deptcode><abstract>While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific operations, and we prove further relevant operations to be computable. Some alternative approaches are discussed, too. As an application in effective descriptive set theory, we can then state and prove computable uniform versions of the Lusin separation theorem and the Hausdorff-Kuratowski theorem. Furthermore, we introduce an operator on the Weihrauch lattice corresponding to iteration of some principle over a countable ordinal.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Mathematical Foundations of Computer Science 2015</journal><volume>9234</volume><journalNumber/><paginationStart>407</paginationStart><paginationEnd>418</paginationEnd><publisher>Springer</publisher><placeOfPublication>Berlin</placeOfPublication><isbnPrint>978-3-662-48056-4</isbnPrint><isbnElectronic>978-3-662-48057-1</isbnElectronic><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2015</publishedYear><publishedDate>2015-12-31</publishedDate><doi>10.1007/978-3-662-48057-1_32</doi><url>http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&amp;amp;SrcAuth=ORCID&amp;amp;SrcApp=OrcidOrg&amp;amp;DestLinkType=FullRecord&amp;amp;DestApp=WOS_CPL&amp;amp;KeyUT=WOS:000371025600037&amp;amp;KeyUID=WOS:000371025600037</url><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2022-12-05T12:51:12.2149837</lastEdited><Created>2017-10-11T11:56:10.8426153</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>1</order></author></authors><documents><document><filename>0036019-12122017162613.pdf</filename><originalFilename>ordinals-lncs.pdf</originalFilename><uploaded>2017-12-12T16:26:13.2600000</uploaded><type>Output</type><contentLength>376461</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2017-12-12T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2022-12-05T12:51:12.2149837 v2 36019 2017-10-11 Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract) 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2017-10-11 MACS While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific operations, and we prove further relevant operations to be computable. Some alternative approaches are discussed, too. As an application in effective descriptive set theory, we can then state and prove computable uniform versions of the Lusin separation theorem and the Hausdorff-Kuratowski theorem. Furthermore, we introduce an operator on the Weihrauch lattice corresponding to iteration of some principle over a countable ordinal. Conference Paper/Proceeding/Abstract Mathematical Foundations of Computer Science 2015 9234 407 418 Springer Berlin 978-3-662-48056-4 978-3-662-48057-1 0302-9743 1611-3349 31 12 2015 2015-12-31 10.1007/978-3-662-48057-1_32 http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&amp;SrcAuth=ORCID&amp;SrcApp=OrcidOrg&amp;DestLinkType=FullRecord&amp;DestApp=WOS_CPL&amp;KeyUT=WOS:000371025600037&amp;KeyUID=WOS:000371025600037 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2022-12-05T12:51:12.2149837 2017-10-11T11:56:10.8426153 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arno Pauly 0000-0002-0173-3295 1 0036019-12122017162613.pdf ordinals-lncs.pdf 2017-12-12T16:26:13.2600000 Output 376461 application/pdf Accepted Manuscript true 2017-12-12T00:00:00.0000000 true eng
title Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
spellingShingle Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
Arno Pauly
title_short Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
title_full Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
title_fullStr Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
title_full_unstemmed Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
title_sort Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Arno Pauly
format Conference Paper/Proceeding/Abstract
container_title Mathematical Foundations of Computer Science 2015
container_volume 9234
container_start_page 407
publishDate 2015
institution Swansea University
isbn 978-3-662-48056-4
978-3-662-48057-1
issn 0302-9743
1611-3349
doi_str_mv 10.1007/978-3-662-48057-1_32
publisher Springer
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&amp;SrcAuth=ORCID&amp;SrcApp=OrcidOrg&amp;DestLinkType=FullRecord&amp;DestApp=WOS_CPL&amp;KeyUT=WOS:000371025600037&amp;KeyUID=WOS:000371025600037
document_store_str 1
active_str 0
description While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific operations, and we prove further relevant operations to be computable. Some alternative approaches are discussed, too. As an application in effective descriptive set theory, we can then state and prove computable uniform versions of the Lusin separation theorem and the Hausdorff-Kuratowski theorem. Furthermore, we introduce an operator on the Weihrauch lattice corresponding to iteration of some principle over a countable ordinal.
published_date 2015-12-31T13:20:27Z
_version_ 1821411772695838720
score 11.247077

Similar Items