Infinite Chains and Antichains in Computable Partial Orderings

Journal of Symbolic Logic 66 (2):923-934 (2001)
  Copy   BIBTEX

Abstract

We show that every infinite computable partial ordering has either an infinite $\Delta^0_2$ chain or an infinite $\Pi^0_2$ antichain. Our main result is that this cannot be improved: We construct an infinite computable partial ordering that has neither an infinite $\Delta^0_2$ chain nor an infinite $\Delta^0_2$ antichain.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,628

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Infinite chains and antichains in computable partial orderings.E. Herrmann - 2001 - Journal of Symbolic Logic 66 (2):923-934.
Chains and antichains in partial orderings.Valentina S. Harizanov, Carl G. Jockusch & Julia F. Knight - 2009 - Archive for Mathematical Logic 48 (1):39-53.
Stability and Posets.Carl G. Jockusch, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693-711.
Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
Computing maximal chains.Alberto Marcone, Antonio Montalbán & Richard A. Shore - 2012 - Archive for Mathematical Logic 51 (5-6):651-660.
Reverse mathematics and initial intervals.Emanuele Frittaion & Alberto Marcone - 2014 - Annals of Pure and Applied Logic 165 (3):858-879.
A note on partial numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Infinite Time Turing Machines With Only One Tape.D. E. Seabold & J. D. Hamkins - 2001 - Mathematical Logic Quarterly 47 (2):271-287.
Equivalence between Fraïssé’s conjecture and Jullien’s theorem.Antonio Montalbán - 2006 - Annals of Pure and Applied Logic 139 (1):1-42.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
On ramsey’s theorem and the existence of infinite chains or infinite anti-chains in infinite posets.Eleftherios Tachtsis - 2016 - Journal of Symbolic Logic 81 (1):384-394.
Computability of measurable sets via effective topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Computable choice functions for computable linear orderings.Manuel Lerman & Richard Watnick - 2003 - Mathematical Logic Quarterly 49 (5):485-510.

Analytics

Added to PP
2017-02-21

Downloads
7 (#1,381,358)

6 months
1 (#1,461,875)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references