A Note on the Hall's Lemma

全文

(1)A Note on the Hall's Lemma By. Masayuki HIURA* The lemma considered first by Hall seems to require its position in the family of various axioms concerning the possibility of choice. The purpose of this note is to make a half step setting the position between the AC and. AC for Finite Sets. -. IPaul R. Halmos and Herbert E. Vaughan published a simple proof of the lemma using Tychonoff's direct ' product theorem. In their proof only the. direct product of compact Hausdorff spaces appears so as to the weaker version of Tychonoff's theorem will lead the result. In this note, Hall.7s･. lemma is proved using the Ultrafilter Theorem equivalent to the weak. Tychonoff's theorem. .-- .! suppose that there is a relation in A to B; wh'ose d'omain is Al I,f f6Yl'. any finite subset of A the number of its elements does p, Qt exe.ed the'. y'. tt"thmPer.-u. of their images, we can find a injection of A into,.B'which is -contained in the given relation.. The case in which A is a finite set, the proof is,achieved by induction on the cardinality of A, (cf. P.Hall: On representation of subsets, Halmos-. Vaughan: The marriage problem). If A is infinite, let M be the set of all fuiite subsets P of A and T the set of all injections t of finite subsets of A into B. For each PeM) there is a finite set Tp of all injections t of Pinto B. Let F be the set of all functions. f on subsets of M ranged into T such that. 1. f(P)ETp foreach PEdom(f) and 2. for any P,QGdom(f), theinjections f(P) and f(Q) arecompatible. ' Let Xp{fGF: PEdom(f)}, then the set {Xp:PGM} has finite intersection. property. '. Let Eg be the filter over F generated by the sets Xp. By the Ultrafilter Theorem, there is an ultrafilter Ù over F which extends Sr.. For every PEM) the set Xp is a finite union. Xp=,,X V ･･･ V ,.X where {tb･･･,t.}=Tp and tjX={fGF:f(P)=tj}, 1'=1,･･･,m. Since Ù is an " Department of Mathematics, Faculty of Education, Yokohama National University..

(2) 28 M. HIuRA. ultrafilter, XpEÙ implies that some tjXECU. And since t,X,t･･,t.X are. disjoint, there is a unique tjGTp such that tjXEÙ. Denote such'tj by tp. For any P, QEM) since t.X, tQXECU, there is an XECU such that '. XE ,.XA ,Q X･ .. This implies that for fEX, f(P)== tp, f(Q)=itQ and f(P), f(Q) are compatible. Thus the union of all tp is an injection of A into B.. References [1] C. J. EvERETT and G. WHApLEs, Represetations of sequences of sets, Amer. Jour. Math, 71 (1949), pp. 287-293. [2] lllti. IIeimLg,26PiStinCt representatives of subsets, Buii. Amer. Math. soc. s4 (ig4s),. [3] P.HALL, On represetation of subsets, Jour. London Math. Soc. 10 (1935), pp.2630.. [4] P, R, HALMos and H. E. VAuGHAN, The marriage problem, Amer. Jour. Math. 72 (1950), pp. 214-215.. [5] T. J. JEcH, The Axiom of Choice, North-Holland, 1973. [6] H. RuBiN and J. E, RuBiN, Equivalents of The Axiom of Choice, North-Holland, 1963. [7] H. WEyL, Almost periodicinvariant vector sets in a metric vector spaces, Amer, Jour. Math. 71 (1949), pp. 178-205.. .. '.

(3)