Infinite chains and antichains in computable partial orderings

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


We show that every infinite computable partial ordering has either an infinite Δ 0 2 chain or an infinite Π 0 2 antichain. Our main result is that this cannot be improved: We construct an infinite computable partial ordering that has neither an infinite Δ 0 2 chain nor an infinite Δ 0 2 antichain



    Upload a copy of this work     Papers currently archived: 92,323

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Concerning Infinite Chains, Infinite Trains, and Borrowing a Typewriter.David A. Conway - 1983 - International Journal for Philosophy of Religion 14 (2):71 - 86.
A note on partial meet package contraction.Jun Li - 1998 - Journal of Logic, Language and Information 7 (2):139-142.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.


Added to PP

23 (#686,422)

6 months
11 (#245,876)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references