nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

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

verfasst von : Arno Pauly

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Eliminating Recursion from Monadic Datalog Programs on Trees

Nächstes Kapitel Emergence on Decreasing Sandpile Models

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}\).

This result essentially is folklore.

In fact, it is sometimes claimed that it has to be done like that – the present work ought to disprove this.

This theorem is based on a personal communication by Vassilios Gregoriades.

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

Brattka, V., Gherardi, G.: Effective choice and boundedness principles in computable analysis. Bull. Symbolic Logic 1, 73–117 (2011). arXiv:0905.4685 MathSciNetCrossRef

Brattka, V., Gherardi, G.: Weihrauch degrees, omniscience principles and weak computability. J. Symbolic Logic 76, 143–176 (2011). arXiv:0905.4679 MathSciNetCrossRefMATH

Brattka, V., Gherardi, G., Hölzl, R.: Probabilistic computability and choice. arXiv:1312.7305 (2013)

Brattka, V., Pauly, A.: On the algebraic structure of Weihrauch degrees (forthcoming)

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

Duparc, J., Fournier, K.: Reductions by relatively continuous relations on \(\mathbb{N}^{\le \omega }\) (unpublished notes)

Escardó, M.: Synthetic topology of datatypes and classical spaces. Electron. Notes Theoret. Comput. Sci. 87, 21–156 (2004)

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.

Hertling, P.: Topological complexity with continuous operations. J. Complex. 12(4), 315–338 (1996)MathSciNetCrossRefMATH

12.

Hertling, P.: Unstetigkeitsgrade von funktionen in der effektiven analysis. Ph.D. thesis, Fernuniversität, Gesamthochschule in Hagen, Oktober 1996

13.

Hertling, P.: Topological complexity of zero finding with algebraic operations. J. Complex. 18, 912–942 (2002)MathSciNetCrossRefMATH

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.

Kihara, T., Pauly, A.: Point degree spectra of represented spaces. arXiv:1405.6866 (2014)

18.

Kleene, S.C.: On notation for ordinal numbers. J. Symbolic Logic 3, 150–155 (1938)CrossRef

19.

Le Roux, S., Pauly, A.: Infinite sequential games with real-valued payoffs arXiv:1401.3325 (2014). arXiv:1401.3325

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.

Pauly, A.: On the (semi)lattices induced by continuous reducibilities. Math. Logic Q. 56(5), 488–502 (2010)MathSciNetCrossRefMATH

26.

Pauly, A.: On the topological aspects of the theory of represented spaces. arXiv:1204.3763 (2012)

27.

Pauly, A.: The descriptive theory of represented spaces. arXiv:1408.5329 (2014)

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.

Pequignot, Y.: A Wadge hierarchy for second countable spaces. Arch. Math. Logic, 1–25 (2015). http://dx.doi.org/10.1007/s00153-015-0434-y

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.

Weihrauch, K.: Computable Analysis. Springer, Heidelberg (2000)CrossRefMATH

38.

Ziegler, M.: Real hypercomputation and continuity. Theory Comput. Syst. 41, 177–206 (2007)MathSciNetCrossRefMATH

39.

Ziegler, M.: Revising type-2 computation and degrees of discontinuity. Electron. Notes Theoret. Comput. Sci. 167, 255–274 (2007)CrossRef

Titel: Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
verfasst von: Arno Pauly
Verlag: Springer Berlin Heidelberg
Buch: Mathematical Foundations of Computer Science 2015
Print ISBN: 978-3-662-48056-4

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"