Ordinal analysis of partial combinatory algebras

DOI10.1017/JSL.2021.50MaRDI QIDQ5015728zbMATH OpenOpenAlexFDO

Authors Paul Shafer, Sebastiaan A. Terwijn

Publication date 9 December 2021

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2010.12452

zbMATH Keywords

lambda calculusextensionalitypartial combinatory algebrahyperarithmetical sets

Mathematics Subject Classification ID

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

Recommendations

• On the existence of extensional partial combinatory algebras
• Computability in partial combinatory algebras
• Extensions of Scott's graph model and Kleene's second algebra
• A notion of a computational step for partial combinatory algebras
• Third-order functionals on partial combinatory algebras

Cites work

• scientific article; zbMATH DE number 3889501 (Why is no real title available?)
• scientific article; zbMATH DE number 3900744 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3556031 (Why is no real title available?)
• scientific article; zbMATH DE number 3216177 (Why is no real title available?)
• A general form of relative recursion
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computable structures and the hyperarithmetical hierarchy
• Constructivism in mathematics. An introduction. Volume II
• Fixed point theorems for precomplete numberings
• Higher-order computability
• Hyperarithmetical Sets
• Index sets for ^0_1 classes
• Monotone inductive definitions over the continuum
• On notation for ordinal numbers
• On the existence of extensional partial combinatory algebras
• Realizability and recursive set theory
• Realizability for constructive Zermelo-Fraenkel set theory
• Realizability. An introduction to its categorical side
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Recursive well-orderings
• Up to equimorphism, hyperarithmetic is recursive

Cited in

(8)

• Embeddings between partial combinatory algebras
• Fixed point theorems in computability theory
• Computable structure theory of partial combinatory algebras
• The complexity of completions in partial combinatory algebra
• Ordinal analysis of partial combinatory algebras
• Analyzing Nash-Williams' partition theorem by means of ordinal types
• Extensions of Scott's graph model and Kleene's second algebra
• Completions of Kleene's second model

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 Q5015728)