Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Minimal and Monotone Minimal Perfect Hash Functions Read chapter Read first chapter

2015 | OriginalPaper | Chapter

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

Author : Arno Pauly

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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. In order to remedy this, we explore various potential representations of the set of countable ordinals. An equivalence class of representations is then suggested as a standard, as it offers the desired closure properties. With a decent notion of computability on the space of countable ordinals in place, we can then state and prove a computable uniform version of the Hausdorff-Kuratowski theorem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Eliminating Recursion from Monadic Datalog Programs on Trees
next chapter Emergence on Decreasing Sandpile Models
Footnotes
1
Any algorithm attempting to compute \(\sup \) on \(\mathbf{COrd}_{\text {M}}\) needs to decide whether or not the result is 0 after finitely many steps – and this questions essentially is \(\text {LPO}\).
 
2
This result essentially is folklore.
 
3
In fact, it is sometimes claimed that it has to be done like that – the present work ought to disprove this.
 
4
This theorem is based on a personal communication by Vassilios Gregoriades.
 
Literature
1.
Brattka, V., de Brecht, M., Pauly, A.: Closed choice and a uniform low basis theorem. Ann. Pure Appl. Logic 163(8), 968–1008 (2012)CrossRef
2.
3.
4.
5.
Brattka, V., Pauly, A.: On the algebraic structure of Weihrauch degrees (forthcoming)
6.
de Brecht, M.: Levels of discontinuity, limit-computability, and jump operators. In: Brattka, V., Diener, H., Spreen, D. (eds.) Logic, Computation, Hierarchies, pp. 79–108. de Gruyter, Berlin (2014). arXiv 1312.​0697
7.
Duparc, J., Fournier, K.: Reductions by relatively continuous relations on \(\mathbb{N}^{\le \omega }\) (unpublished notes)
8.
Escardó, M.: Synthetic topology of datatypes and classical spaces. Electron. Notes Theoret. Comput. Sci. 87, 21–156 (2004)
9.
Gherardi, G., Marcone, A.: How incomputable is the separable Hahn-Banach theorem? Notre Dame J. Formal Logic 50(4), 393–425 (2009)MathSciNetCrossRefMATH
10.
Gregoriades, V., Kispéter, T., Pauly, A.: A comparison of concepts from computable analysis and effective descriptive set theory. arXiv:​1401.​3325 (2014)
11.
12.
Hertling, P.: Unstetigkeitsgrade von funktionen in der effektiven analysis. Ph.D. thesis, Fernuniversität, Gesamthochschule in Hagen, Oktober 1996
13.
14.
Hertling, P., Weihrauch, K.: Levels of degeneracy and exact lower complexity bounds. In: 6th Canadian Conference on Computational Geometry, pp. 237–242 (1994)
15.
Higuchi, K., Pauly, A.: The degree-structure of Weihrauch-reducibility. Log. Methods Comput. Sci. 9(2), 1–17 (2013)MathSciNetCrossRef
16.
Jayne, J., Rogers, C.: First level borel functions and isomorphisms. Journal de Mathématiques Pures et Appliquées 61, 177–205 (1982)MathSciNetMATH
17.
18.
Kleene, S.C.: On notation for ordinal numbers. J. Symbolic Logic 3, 150–155 (1938)CrossRef
19.
20.
Li, Z., Hamkins, J.D.: On effectiveness of operations on countable ordinals. unpublished notes
21.
Moschovakis, Y.N.: Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics, vol. 100. North-Holland publishing company, Amsterdam (1980)
22.
Ros, M.L., Semmes, B.: A new proof of a theorem of Jayne and Rogers. Real Anal. Exch. 35(1), 195–204 (2009)
23.
Pauly, A.: Methoden zum Vergleich der Unstetigkeit von Funktionen. Masters thesis, FernUniversität Hagen (2007)
24.
Pauly, A.: How incomputable is finding Nash equilibria? J. Univ. Comput. Sci. 16(18), 2686–2710 (2010)MathSciNetMATH
25.
26.
27.
28.
Pauly, A.: Computability on the countable ordinals and the Hausdorff-Kuratowski theorem. arXiv 1501.00386 (2015)
29.
Pauly, A., de Brecht, M.: Towards synthetic descriptive set theory: An instantiation with represented spaces. arXiv:​1307.​1850 (2013)
30.
Pauly, A., de Brecht, M.: Non-deterministic computation and the Jayne Rogers theorem. Electron, Proc. Theoret. Comput. Sci. 143, 87–96 (2014). dCM 2012CrossRef
31.
32.
Schröder, M.: Admissible Representations for Continuous Computations. Ph.D. thesis, FernUniversität Hagen (2002)
33.
Schröder, M.: A natural weak limit space with admissible representation which is not a limit space. ENTCS 66(1), 165–175 (2002)
34.
Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. Proc. LMS 2(42), 230–265 (1936)MathSciNet
35.
Turing, A.: On computable numbers, with an application to the Entscheidungsproblem: Corrections. Proc. LMS 2(43), 544–546 (1937)MathSciNet
36.
Weihrauch, K.: The TTE-interpretation of three hierarchies of omniscience principles. Informatik Berichte 130, FernUniversität Hagen, Hagen (1992)
37.
38.
39.
Ziegler, M.: Revising type-2 computation and degrees of discontinuity. Electron. Notes Theoret. Comput. Sci. 167, 255–274 (2007)CrossRef
Metadata
Title
Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
Author
Arno Pauly
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48056-4

Electronic ISBN: 978-3-662-48057-1

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48057-1_32

Premium Partner

    Image Credits