Hyperfinite transversal theory

Author:
Boško Živaljević

Journal:
Trans. Amer. Math. Soc. **330** (1992), 371-399

MSC:
Primary 03H05; Secondary 04A20, 05D15

DOI:
https://doi.org/10.1090/S0002-9947-1992-1033237-1

MathSciNet review:
1033237

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A measure theoretic version of a well-known P. Hall's theorem, about the existence of a system of distinct representatives of a finite family of finite sets, has been proved for the case of the Loeb space of an internal, uniformly distributed, hyperfinite counting space. We first prove Hall's theorem for graphs after which we develop the version of discrete Transversal Theory. We then prove a new version of Hall's theorem in the case of monotone graphs and give an example of a graph which satisfies Hall's condition and which does not possess an internal a.e. matching.

**[Bo]**Béla Bollobás,*Extremal graph theory*, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR**506522****[BoVa]**B. Bollobás and N. Th. Varopoulos,*Representation of systems of measurable sets*, Math. Proc. Cambridge Philos. Soc.**78**(1975), no. 2, 323–325. MR**0379781**, https://doi.org/10.1017/S0305004100051756**[Ha]**P. Hall,*On representatives of subsets*, J. London Math. Soc.**10**(1935), 26-30.**[He]**C. Ward Henson,*Analytic sets, Baire sets and the standard part map*, Canad. J. Math.**31**(1979), no. 3, 663–672. MR**536371**, https://doi.org/10.4153/CJM-1979-066-0**[HeRo]**C. Ward Henson and David Ross,*Analytic mappings on hyperfinite sets*, Proc. Amer. Math. Soc.**118**(1993), no. 2, 587–596. MR**1126195**, https://doi.org/10.1090/S0002-9939-1993-1126195-9**[HPS]**Michael Holz, Klaus-Peter Podewski, and Karsten Steffens,*Injective choice functions*, Lecture Notes in Mathematics, vol. 1238, Springer-Verlag, Berlin, 1987. MR**880206****[HuLo]**Albert E. Hurd and Peter A. Loeb,*An introduction to nonstandard real analysis*, Pure and Applied Mathematics, vol. 118, Academic Press, Inc., Orlando, FL, 1985. MR**806135****[KKLM]**H. Jerome Keisler, Kenneth Kunen, Arnold Miller, and Steven Leth,*Descriptive set theory over hyperfinite sets*, J. Symbolic Logic**54**(1989), no. 4, 1167–1180. MR**1026596**, https://doi.org/10.2307/2274812**[Ki]**Henry A. Kierstead,*An effective version of Hall’s theorem*, Proc. Amer. Math. Soc.**88**(1983), no. 1, 124–128. MR**691291**, https://doi.org/10.1090/S0002-9939-1983-0691291-0**[LaRo]**D. Landers and L. Rogge,*Universal Loeb-measurability of sets and of the standard part map with applications*, Trans. Amer. Math. Soc.**304**(1987), no. 1, 229–243. MR**906814**, https://doi.org/10.1090/S0002-9947-1987-0906814-1**[Lo]**Peter A. Loeb,*Conversion from nonstandard to standard measure spaces and applications in probability theory*, Trans. Amer. Math. Soc.**211**(1975), 113–122. MR**0390154**, https://doi.org/10.1090/S0002-9947-1975-0390154-8**[MaRo]**Alfred B. Manaster and Joseph G. Rosenstein,*Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall)*, Proc. London Math. Soc. (3)**25**(1972), 615–654. MR**0314610**, https://doi.org/10.1112/plms/s3-25.4.615**[Mi]**L. Mirsky,*Transversal theory. An account of some aspects of combinatorial mathematics*, Mathematics in Science and Engineering, Vol. 75, Academic Press, New York-London, 1971. MR**0282853****[NW]**C. St. J. A. Nash-Williams,*Unexplored and semi-explored territories in graph theory*, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York, 1973, pp. 149–186. MR**0387097****[Ra]**R. Rado,*A theorem on general measure function*, Proc. London Math. Soc.**44**(1938), 61-91.**[Ro]**D. Ross, (private communication).**[StBa]**K. D. Stroyan and José Manuel Bayod,*Foundations of infinitesimal stochastic analysis*, Studies in Logic and the Foundations of Mathematics, vol. 119, North-Holland Publishing Co., Amsterdam, 1986. MR**849100****[StLu]**K. D. Stroyan and W. A. J. Luxemburg,*Introduction to the theory of infinitesimals*, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. Pure and Applied Mathematics, No. 72. MR**0491163****[Ži]**Boško Živaljević,*Rado’s theorem for the Loeb space of an internal *-finitely additive measure space*, Proc. Amer. Math. Soc.**112**(1991), no. 1, 203–207. MR**1056688**, https://doi.org/10.1090/S0002-9939-1991-1056688-2**[Ži]**Boško Živaljević,*The structure of graphs all of whose 𝑌-sections are internal sets*, J. Symbolic Logic**56**(1991), no. 1, 50–66. MR**1131729**, https://doi.org/10.2307/2274903**[Ži]**-,*Hyperfinite transversal theory*. II (in preparation).

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
03H05,
04A20,
05D15

Retrieve articles in all journals with MSC: 03H05, 04A20, 05D15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1992-1033237-1

Article copyright:
© Copyright 1992
American Mathematical Society