Ordinal analysis of partial combinatory algebras

Journal of Symbolic Logic 86 (3):1154-1188 (2021)
  Copy   BIBTEX

Abstract

For every partial combinatory algebra, we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca’s, i.e., the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene’s first model is ${\omega _1^{\textit {CK}}}$ and that the closure ordinal of Kleene’s second model is $\omega _1$. We calculate the exact complexities of the extensionality relations in Kleene’s first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of pca’s.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,923

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Partial Combinatory Algebras of Functions.Jaap van Oosten - 2011 - Notre Dame Journal of Formal Logic 52 (4):431-448.
Computability in partial combinatory algebras.Sebastiaan A. Terwijn - 2020 - Bulletin of Symbolic Logic 26 (3-4):224-240.
A General Form of Relative Recursion.Jaap van Oosten - 2006 - Notre Dame Journal of Formal Logic 47 (3):311-318.
Analytic combinatory calculi and the elimination of transitivity.Pierluigi Minari - 2004 - Archive for Mathematical Logic 43 (2):159-191.
D-algebras.Stanley Gudder - 1996 - Foundations of Physics 26 (6):813-822.
Linear realizability and full completeness for typed lambda-calculi.Samson Abramsky & Marina Lenisa - 2005 - Annals of Pure and Applied Logic 134 (2-3):122-168.
Partial algebras for Łukasiewicz logics and its extensions.Thomas Vetterlein - 2005 - Archive for Mathematical Logic 44 (7):913-933.
Characteristic Formulas of Partial Heyting Algebras.Alex Citkin - 2013 - Logica Universalis 7 (2):167-193.
On the structure of linearly ordered pseudo-BCK-algebras.Anatolij Dvurečenskij & Jan Kühr - 2009 - Archive for Mathematical Logic 48 (8):771-791.

Analytics

Added to PP
2021-12-06

Downloads
12 (#1,111,684)

6 months
7 (#489,614)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Embeddings between Partial Combinatory Algebras.Anton Golov & Sebastiaan A. Terwijn - 2023 - Notre Dame Journal of Formal Logic 64 (1):129-158.

Add more citations

References found in this work

On notation for ordinal numbers.S. C. Kleene - 1938 - Journal of Symbolic Logic 3 (4):150-155.
Recursive well-orderings.Clifford Spector - 1955 - Journal of Symbolic Logic 20 (2):151-163.
Realizability and recursive set theory.Charles McCarty - 1986 - Annals of Pure and Applied Logic 32:153-183.
Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
Up to Equimorphism, Hyperarithmetic Is Recursive.Antonio Montalbán - 2005 - Journal of Symbolic Logic 70 (2):360 - 378.

View all 9 references / Add more references