Computing maximal chains

DOI10.1007/S00153-012-0289-4MaRDI QIDQ453200zbMATHOpenAlexFDO

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

maximal chaincomputable well partial orderhyperarithmetic hierarchyhyperarithmetically generic

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• Complexity of winning strategies
• Computable linearizations of well-partial-orderings
• 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
• Infinite chains and antichains in computable partial orderings
• The reverse mathematics of wqos and bqos
• Maximal chains in the Turing degrees
• Computable linearizations of well-partial-orderings
• A computably enumerable partial ordering without computably enumerable maximal chains and antichains
• The computational significance of Hausdorff's maximal chain principle
• Computing the all-pairs longest chains in the plane

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)