Journal of Symbolic Logic · 2001 · 16 citations · 2 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationComputability TheoryPartial OrdersPartially Ordered SetsRecursion TheoryChainsInfinite ChainsPartial Ordering
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.
2
Recursively enumerable sets and degrees
Robert I. Soare · Bulletin of the American Mathematical Society · 1978 · 1.6K citations · Full text
Ramsey's theorem and recursion theory
Carl G. Jockusch · Journal of Symbolic Logic · 1972 · 211 citations