Infinite Chains and Antichains in Computable Partial Orderings
Herrman, E.
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 923-934 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 2001-06-14
Classification:  
@article{1183746482,
     author = {Herrman, E.},
     title = {Infinite Chains and Antichains in Computable Partial Orderings},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 923-934},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746482}
}

Herrman, E. Infinite Chains and Antichains in Computable Partial Orderings. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  923-934. http://gdmltest.u-ga.fr/item/1183746482/