An effective version of Dilworth’s theorem

Abstract

We prove that if (P, <p) is a recursive partial order with finite width w, then P can be covered by (5W -l)/4 recursive chains. For each w we show that there is a recursive partial ordering of width w that cannot be covered by 4(w -1) recursive chains. 0. Introduction. Loosely speaking, a subset A of the natural numbers is recursive iff there exists an algorithm (i.e., a finite computer program) which upon input of a natural number n outputs "1" if n El A and "0" otherwise. Similarly a partial ordering (A, <) is recursive iff there is an algorithm which upon input of an ordered pair of natural numbers (a, b) outputs "1" if a < b and "0" otherwise. For a more careful definition of recursive relations see [R].