No Cover Image

Conference Paper/Proceeding/Abstract 317 views 47 downloads

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

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

Swansea University Author: Arno, Pauly

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
Tags: Add Tag
No Tags, Be the first to tag this record!
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.
Start Page: 407
End Page: 418