Ordinal analysis of partial combinatory algebras

DOI10.1017/JSL.2021.50MaRDI QIDQ6352093arXivFDO

Authors Paul Shafer, Sebastiaan A. Terwijn

Publication date 23 October 2020

Published in arXiv

Full work available at URL https://doi.org/10.1017/JSL.2021.50

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45)

arXiv classification

cs.LOmath.LO

Abstract: For every partial combinatory algebra (pca), 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 $omeg{a}_1^{e}xtitCK$ and that the closure ordinal of Kleene's second model is $omeg{a}_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.

This page was built for publication: Ordinal analysis of partial combinatory algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6352093)