Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Hyperfinite transversal theory

Author: Boško Živaljević
Journal: Trans. Amer. Math. Soc. 330 (1992), 371-399
MSC: Primary 03H05; Secondary 04A20, 05D15
MathSciNet review: 1033237
Full-text PDF Free Access

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 $ \Pi _1^0(\kappa)$ 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 $ \Sigma _1^0(\kappa)$ monotone graphs and give an example of a $ \Sigma _1^0$ graph which satisfies Hall's condition and which does not possess an internal a.e. matching.

References [Enhancements On Off] (What's this?)

  • [Bo] B. Bollobas, Extremal graph theory, Academic Press, New York, 1978. MR 506522 (80a:05120)
  • [BoVa] B. Bollobas and N. Th. Varopoulos, Representation of systems of measurable sets, Math. Proc. Cambridge Philos. Soc. 78 (1974), 323-325. MR 0379781 (52:686)
  • [Ha] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26-30.
  • [He] C. W. Henson, Analytic sets, Baire sets, and the standard part map, Canad. J. Math. 31 (1979), 663-672. MR 536371 (80i:28019)
  • [HeRo] C. W. Henson and D. Ross, Analytic mappings on hyperfinite sets (to appear). MR 1126195 (93g:03055)
  • [HPS] M. Holz, K. P. Podewski, and K. Steffens, Injective choice function, Lecture Notes in Math., vol. 1238, Springer-Verlag, 1987. MR 880206 (88d:04002)
  • [HuLo] A. E. Hurd and P. A. Loeb, An introduction to nonstandard real analysis, Academic Press, 1985. MR 806135 (87d:03184)
  • [KKLM] H. J. Keisler, K. Kunen, S. Leth, and A. Miller, Descriptive set theory over hyperfinite sets, J. Symbolic Logic 54 (1989), 1167-1180. MR 1026596 (91c:03040)
  • [Ki] H. A. Kirstead, An effective version of Hall's theorem, Proc. Amer. Math. Soc. 88 (1983), 124-128. MR 691291 (84g:03065)
  • [LaRo] D. Landers and L. Rogge, Universal Loeb-measurability of sets and of the standard part map with applications, Trans. Amer. Math. Soc. 304 (1983), 229-243. MR 906814 (89d:28015)
  • [Lo] P. A. Loeb, Conversion from nonstandard to standard measure space and applications in probability theory, Trans. Amer. Math. Soc. 211 (1975), 113-122. MR 0390154 (52:10980)
  • [MaRo] A. B. Manaster and J. G. Rosenstein, Effective matchmaking (recursive theoretic aspects of a theorem of Philip Hall), Proc. London Math. Soc. (3) 25 (1972), 615-654. MR 0314610 (47:3161)
  • [Mi] L. Mirski, Transversal theory, Academic Press, 1971. MR 0282853 (44:87)
  • [NW] C. Nash-Williams, Unexplored and semi-explored territories in graph theory, New Directions in Graph Theory, (Frank Harary, ed.), Academic Press, 1973. MR 0387097 (52:7944)
  • [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 J. M. Bayod, Foundations of infinitesimal stochastic analysis, North-Holland, 1986. MR 849100 (87m:60001)
  • [StLu] K. D. Stroyan and W. A. J. Luxemburg, Introduction to the theory of infinitesimals, Academic Press, 1976. MR 0491163 (58:10429)
  • [Ži$ _{1}$] B. Živaljević, Rado's theorem for the Loeb space of an internal $ \ast$-finitely additive measure space, Proc. Amer. Math. Soc. 112 (1991), 203-207. MR 1056688 (91h:03092)
  • [Ži$ _{2}$] -, The structure of graphs all of whose $ Y$-sections are internal sets, J. Symbolic Logic 56 (1991), 50-66. MR 1131729 (92j:03059)
  • [Ži$ _{3}$] -, Hyperfinite transversal theory. II (in preparation).

Similar Articles

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

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society