Conference Paper/Proceeding/Abstract 920 views 247 downloads
Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
Mathematical Foundations of Computer Science 2015, Volume: 9234, Pages: 407 - 418
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (398.55KB)
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...
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 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
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>SCS</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;SrcAuth=ORCID&amp;SrcApp=OrcidOrg&amp;DestLinkType=FullRecord&amp;DestApp=WOS_CPL&amp;KeyUT=WOS:000371025600037&amp;KeyUID=WOS:000371025600037</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</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 SCS 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&SrcAuth=ORCID&SrcApp=OrcidOrg&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=WOS:000371025600037&KeyUID=WOS:000371025600037 COLLEGE NANME Computer Science COLLEGE CODE SCS 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&SrcAuth=ORCID&SrcApp=OrcidOrg&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=WOS:000371025600037&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-31T03:44:59Z |
_version_ |
1763752122054082560 |
score |
11.021648 |