Computably enumerable partial orders

DOI10.3233/COM-12013MaRDI QIDQ4904461zbMATH OpenOpenAlexFDO

Authors Peter A. Cholak, Damir D. Dzhafarov, Noah Schweber, Richard A. Shore

Publication date 30 January 2013

Published in Computability (Search for Journal in Brave)

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

zbMATH Keywords

antichainschainscomputably enumerable partial orders

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Computable structure theory, computable model theory (03C57) Recursively (computably) enumerable sets and degrees (03D25)

Abstract: We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain principle and ascending/descending sequence principle for such orders, and show that the former is strictly stronger than the latter. We then show that every $emptyse{t}^{\prime }$-computable structure (or even just of c.e. degree) has the same degree spectrum as some computably enumerable (co-c.e.) partial order, and hence that there is a c.e. (co-c.e.) partial order with spectrum equal to the set of nonzero degrees.

Recommendations

• Computable linear orders and the Ershov hierarchy
• Infinite chains and antichains in computable partial orderings
• Chains and antichains in partial orderings
• scientific article; zbMATH DE number 2237373
• Degree spectra of the successor relation of computable linear orderings

Cited in

(15)

• Chains and antichains in partial orderings
• A computably enumerable partial ordering without computably enumerable maximal chains and antichains
• The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent
• On degree spectra of topological spaces
• The uniform content of partial and linear orders
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• Infinite chains and antichains in computable partial orderings
• The computability path ordering
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Algorithmically random series
• Ideal presentations and numberings of some classes of effective quasi-Polish spaces

This page was built for publication: Computably enumerable partial orders

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