Computing maximal chains

DOI10.1007/S00153-012-0289-4MaRDI QIDQ453200zbMATH OpenOpenAlexFDO

Authors Alberto Marcone, Antonio Montalbán, Richard A. Shore

Publication date 18 September 2012

Published in Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

computable well partial orderhyperarithmetic hierarchyhyperarithmetically genericmaximal chain

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Applications of computability and recursion theory (03D80) Combinatorics of partially ordered sets (06A07)

Abstract: In 1967 Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk's original result actually shows that every wpo has a strongly maximal chain, which we define below. We show that a set computes strongly maximal chains in all computable wpo if and only if it computes all hyperarithmetic sets.

Review text

This paper examines computability properties of chains of maximal order type (maximal chains, for short) contained in computable well partial orders (wpo's). The centerpiece is the theorem that, given any computable wpo \(P\) and any hyperarithmetically generic set \(G\), then \(P\) contains some maximal chain that is Turing-reducible to \(G\). On the other hand, the authors show that for any computable ordinal \(\alpha\), there exists a computable wpo containing no maximal chain reducible to \(0^{(\alpha)}\).

Recommendations

• Infinite chains and antichains in computable partial orderings
• Chains and antichains in partial orderings
• Maximal chains in the Turing degrees
• Computable linearizations of well-partial-orderings
• Well-partial orderings and their maximal order types

Cites work

• Complexity of winning strategies
• Computable linearizations of well-partial-orderings
• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• On Chains and Antichains in well Founded Partially Ordered Sets
• On the strength of König's duality theorem for countable bipartite graphs
• On the strength of König's duality theorem for infinite bipartite graphs
• Ordered sets
• Pairs of recursive structures
• Partially well ordered sets and partial ordinals
• Subsystems of second order arithmetic
• The maximal linear extension theorem in second order arithmetic

Cited in

(8)

• Chains and antichains in partial orderings
• A computably enumerable partial ordering without computably enumerable maximal chains and antichains
• The computational significance of Hausdorff's maximal chain principle
• Computable linearizations of well-partial-orderings
• Infinite chains and antichains in computable partial orderings
• The reverse mathematics of wqos and bqos
• Computing the all-pairs longest chains in the plane
• Maximal chains in the Turing degrees

This page was built for publication: Computing maximal chains

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