The Journal of Symbolic Logic

Research Article

Infinite chains and antichains in computable partial Orderings

E. Herrmann

Institut für Mathematik, Humboldt University, Unter Den Linden 6, 10099 Berlin, Germany, E-mail: herrmann@mathematik.hu-berlin.de

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.

(Received April 23 1998)