Abstract
We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is \({\Sigma _{1}^{1}}\) or \({\Pi _{1}^{1}}\) , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two \({\Pi _{1}^{1}}\) sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering \({\mathcal{A}}\) has the feature that for every \({\mathcal{B} \cong \mathcal{A}}\) , there is an infinite chain or antichain that is \({\Delta _{2}^{0}}\) relative to \({\mathcal{B}}\) , then we have uniform dichotomy: either for all copies \({\mathcal{B}}\) of \({\mathcal{A}}\) , there is an infinite chain that is \({\Delta _{2}^{0}}\) relative to \({\mathcal{B}}\) , or for all copies \({\mathcal{B}}\) of \({\mathcal{A}}\) , there is an infinite antichain that is \({\Delta _{2}^{0}}\) relative to \({\mathcal{B}}\) .
Similar content being viewed by others
References
Jockusch C.G. Jr.: Ramsey’s theorem and recursion theory. J. Symb. Logic 37, 268–280 (1972)
Herrmann E.: Infinite chains and antichains in computable partial orderings. J. Symb. Logic 66, 923–934 (2001)
Binns S., Kjos-Hanssen B., Lerman M., Schmerl J.H., Solomon R.: Self-embeddings of computable trees. Notre Dame J. Formal Logic 49, 1–37 (2008)
Rogers H. Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)
Ash C.J., Knight J.F.: Computable Structures and the Hyperarithmetical Hierarchy. Elsevier, Amsterdam (2000)
Ash C.J., Knight J.F.: Relatively recursive expansions. Fundamenta Mathematicae 140, 137–155 (1992)
Jockusch, C. Jr., Kastermans, B., Lempp, S., Lerman, M. Solomon, R.: Stability and posets. J. Symb. Logic (to appear)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Harizanov, V.S., Jockusch, C.G. & Knight, J.F. Chains and antichains in partial orderings. Arch. Math. Logic 48, 39–53 (2009). https://doi.org/10.1007/s00153-008-0114-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-008-0114-2