A theory of recursive dimension of ordered sets (Q2266723)

The paper deals with countable ordered sets only. Such a set (A,\(\leq)\) is recursive iff both A and \(\leq\) are recursive sets. The recursive dimension of (A,\(\leq)\) is the least cardinal m such that (A,\(\leq)\) can be recursively embedded into \(Q^ m\) where Q is the set of rationals. The recursive chain covering number of (A,\(\leq)\) is the minimal number of disjoint recursive chains the union of which is A. The authors prove many assertions showing relations between these concepts. Typical examples: There is a recursive ordered set of width 3 and recursive chain covering number 4 which has no finite recursive dimension (Theorem 0). Every recursive ordered set of width not more than 2 has recursive dimension not more than 5 (Theorem 2). For the proofs they have used a nontraditional game theoretical approach.