Infinite chains and antichains in computable partial orderings

Authors
Herrmann, E
Citation
E. Herrmann, Infinite chains and antichains in computable partial orderings, J SYMB LOG, 66(2), 2001, pp. 923-934
Citations number
4
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812 → ACNP
Volume
66
Issue
2
Year of publication
2001
Pages
923 - 934
Database
ISI
SICI code
0022-4812(200106)66:2<923:ICAAIC>2.0.ZU;2-2
Abstract
We show that every infinite computable partial ordering has either an infin ite 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 partia l ordering that has neither an infinite Delta (0)(2) chain nor an infinite Delta (0)(2) antichain.