Finite condensations of recursive linear orders

DOI10.1007/BF00671562MaRDI QIDQ1120568zbMATH OpenOpenAlexFDO

Authors Dev K. Roy, Richard Watnick

Publication date 1988

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00671562

zbMATH Keywords

arithmetical hierarchyfinite condensation of a recursive linear order type

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55) Total orders (06A05)

Review text

This paper answers a question raised by J. Rosenstein: that of locating, in the arithmetical hierarchy, the finite condensation of a recursive linear order type. It was proved that (1) there is a recursive linear order whose finite condensation has \(\Pi_ 2-\Pi_ 1\) order type, (2) a linear order type is \(\Pi_{2n}\) iff it is the n-fold finite condensation of a recursive type, and (3) for all \(n\geq 2\) an order type is \(\Pi_ n\) iff it is \(\Sigma_ n\) presented.

Recommendations

• Linear Order Types of Nonrecursive Presentability
• Linear Order Types of Nonrecursive Presentability
• scientific article; zbMATH DE number 749934
• A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
• Linearisations and the Ershov hierarchy

Cites work

• A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
• Linear Order Types of Nonrecursive Presentability
• R. e. presented linear orders

Cited in

(10)

• Recursive automorphisms of recursive linear orderings
• scientific article; zbMATH DE number 5302144 (Why is no real title available?)
• Linear Order Types of Nonrecursive Presentability
• A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
• scientific article; zbMATH DE number 3944793 (Why is no real title available?)
• Recursive Linear Orders with Incomplete Successivities
• A construction for recursive linear orderings
• scientific article; zbMATH DE number 568841 (Why is no real title available?)
• Linear Order Types of Nonrecursive Presentability
• Up to equimorphism, hyperarithmetic is recursive

This page was built for publication: Finite condensations of recursive linear orders

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