ORDINAL ANALYSIS OF PARTIAL COMBINATORY ALGEBRAS

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 ${\omega _1^{\texti...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 2021-09, Vol.86 (3), p.1154-1188
Main Authors: SHAFER, PAUL, TERWIJN, SEBASTIAAN A.
Format: Article
Language:English
Subjects:
Algebra
Calculus
Logic
Mathematics
Philosophy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ${\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.
ISSN:0022-4812
1943-5886
DOI:10.1017/jsl.2021.50