Article,
A theory of recursive dimension for ordered sets
Order, 1 (1): 67--82 (1984)
Abstract
The classical theorem of R. P. Dilworth asserts that a partially
ordered set of width n can be partitioned into n chains. Dilworth's
theorem plays a central role in the dimension theory of partially
ordered sets since chain partitions can be used to provide embeddmgs
of partially ordered sets in the Cartesian product of chains. In
particular, the dimension of a partiallyordered set never exceeds its
width. In this paper, we consider analogous problems in the setting of
recursive combinatorics where it is required that the partially
ordered set and any associated partition or embedding be described by
recursive functions. We establish several theorems providing upper
bounds on the recursive dimension of a partially ordered set in terms
of its width. The proofs are highly combinatorial in nature and
involve a detailed analysis of a 2-person game in which one person
builds a partially ordered set one point at a time and the other
builds the partition or embedding. AMS (MOS) Key words. subject
classifications (1980). Primary: 06AlO; secondary: 05C35,03D21).
Partially ordered sets, recursive function, recursive combinatorics,
dimension.
