On a theorem of Richardson
John R. Isbell · Proceedings of the American Mathematical Society · 1957
Given a set S with an irreflexive relation >, define the operators dom and max as follows. For any subset T of S, dom T is the set of all x in S such that for some t in T, t>x; max T= T-dom T. A solution of (S, > ) is a subset T of S satisfying T = S dom T. A solution of an n-person game in the sense of [3] is precisely a solution, as just defined, of a certain system (S, >) associated with the game. Von Neumann and Morgenstern investigated various combinatorial criteria for solutions in [3, pp. 587-602]. Richardson has given further criteria; in particular, in [4] he established that if every unoriented cycle in S is even then S has a solution.2 An unoriented cycle is a subset (xi, * * *, xn) of S such that for i=1, * * *, n-1, either xi > xi+, or xi+, > xi, and also x1 > xn or x. > xi. This note establishes a reduction for general (S, >) which yields a simplified proof of Richardson's theorem. The reduction is an elaboration of one which has been studied by Gillies [I]. Obviously any solution T must contain max S, since every point is in T or in dom T. Hence no solution can contain any point of dom max S, since no point of T is in dom T. Inductively let Si = S, Ma max Sa, Da = dom Ma, Sa+i Sa Ma -Da; and for limit ordinals ae, let Sa=n[S4 f ) then TnR is a solution of (R, >), and (2) if TnR is a solution of (R, >) then (TnR)UM is a solution of (S, >). This establishes a one-to-one correspondence between solutions of R and solutions of S. By construction of M, max R is empty. Therefore solving S reduces to solving R, where max R is empty. In Richardson's case this is done by a theorem of Konig [2 ]: if all unoriented cycles in R are even, then R can be colored in two colors, i.e. partitioned into two sets, P, Q, such that x>y never holds if x and y are both in P or both in Q.