Computability-theoretic and proof-theoretic aspects of partial and linear orderings

DOI10.1007/BF02783429zbMath1044.03043MaRDI QIDQ1425651

Rodney G. Downey, Steffen Lempp, Denis R. Hirschfeldt, D. Reed Solomon

Publication date: 17 March 2004

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

combinatorics; proof theory; reverse mathematics; partial ordering; linear ordering; Szpilrajn's theorem; effective content

Mathematics Subject Classification ID

06A06: Partial orders, general

06A07: Combinatorics of partially ordered sets

03B30: Foundations of classical theories (including reverse mathematics)

06A05: Total orders

03F35: Second- and higher-order arithmetic and fragments

03D45: Theory of numerations, effectively presented structures

Related Items

There are 2^{ℵ₀} many 𝐻-degrees in the random reals, Up to equimorphism, hyperarithmetic is recursive, Countably complementable linear orderings, Equivalence between Fraïssé's conjecture and Jullien's theorem, Some Questions in Computable Mathematics, Linear extensions of partial orders and reverse mathematics, Open Questions in Reverse Mathematics, Maximal compatible extensions of partial orders, On the Equimorphism Types of Linear Orderings

Cites Work

• Countable algebra and set existence axioms
• Extending partial orders to dense linear orders
• Effective procedures in field theory
• Effective content of field theory
• Ordered Groups: A Case Study in Reverse Mathematics
• Computable Algebra, General Theory and Theory of Computable Fields
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item