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 Δ 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

Categories

Keywords

Reprint years

DOI

10.2307/2695053

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,458

External links

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. Herrman - 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 Ramsey choice and partial choice for infinite families of n -element sets.Lorenz Halbeisen & Eleftherios Tachtsis - 2020 - Archive for Mathematical Logic 59 (5-6):583-606.
Interpreting true arithmetic in the Δ 0 2 -enumeration degrees.Thomas F. Kent - 2010 - Journal of Symbolic Logic 75 (2):522-550.
Degree spectra of relations on computable structures in the presence of Δ 2 0 isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697-720.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
A note on partial numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.

Analytics

Added to PP
2009-01-28

Downloads
31 (#729,492)

6 months
7 (#711,641)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Preface.Douglas Cenzer, Valentina Harizanov, David Marker & Carol Wood - 2009 - Archive for Mathematical Logic 48 (1):1-6.

Add more citations

References found in this work

No references found.

Add more references