Infinite chains and antichains in computable partial Orderings
Eberhard Herrmann · Journal of Symbolic Logic · 2001
Abstract We show that every infinite computable partial ordering has either an infinite chain or an infinite antichain. Our main result is that this cannot be improved: We construct an infinite computable partial ordering that has neither an infinite chain nor an infinite antichain.