Hyperfinite transversal theory
Author:
Boško Živaljević
Journal:
Trans. Amer. Math. Soc. 330 (1992), 371399
MSC:
Primary 03H05; Secondary 04A20, 05D15
MathSciNet review:
1033237
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A measure theoretic version of a wellknown 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], LondonNew York, 1978. MR 506522
(80a:05120)
 [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
(52 #686)
 [Ha]
P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 2630.
 [He]
C.
Ward Henson, Analytic sets, Baire sets and the standard part
map, Canad. J. Math. 31 (1979), no. 3,
663–672. MR
536371 (80i:28019), http://dx.doi.org/10.4153/CJM19790660
 [HeRo]
C.
Ward Henson and David
Ross, Analytic mappings on hyperfinite
sets, Proc. Amer. Math. Soc.
118 (1993), no. 2,
587–596. MR 1126195
(93g:03055), http://dx.doi.org/10.1090/S00029939199311261959
 [HPS]
Michael
Holz, KlausPeter
Podewski, and Karsten
Steffens, Injective choice functions, Lecture Notes in
Mathematics, vol. 1238, SpringerVerlag, Berlin, 1987. MR 880206
(88d:04002)
 [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 (87d:03184)
 [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
(91c:03040), http://dx.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 (84g:03065), http://dx.doi.org/10.1090/S00029939198306912910
 [LaRo]
D.
Landers and L.
Rogge, Universal Loebmeasurability of sets
and of the standard part map with applications, Trans. Amer. Math. Soc. 304 (1987), no. 1, 229–243. MR 906814
(89d:28015), http://dx.doi.org/10.1090/S00029947198709068141
 [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
(52 #10980), http://dx.doi.org/10.1090/S00029947197503901548
 [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
(47 #3161)
 [Mi]
L.
Mirsky, Transversal theory. An account of some aspects of
combinatorial mathematics, Mathematics in Science and Engineering,
Vol. 75, Academic Press, New YorkLondon, 1971. MR 0282853
(44 #87)
 [NW]
C.
St. J. A. NashWilliams, Unexplored and semiexplored 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
(52 #7944)
 [Ra]
R. Rado, A theorem on general measure function, Proc. London Math. Soc. 44 (1938), 6191.
 [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, NorthHolland Publishing Co., Amsterdam, 1986. MR 849100
(87m:60001)
 [StLu]
K.
D. Stroyan and W.
A. J. Luxemburg, Introduction to the theory of infinitesimals,
Academic Press [Harcourt Brace Jovanovich, Publishers], New YorkLondon,
1976. Pure and Applied Mathematics, No. 72. MR 0491163
(58 #10429)
 [Ž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
(91h:03092), http://dx.doi.org/10.1090/S00029939199110566882
 [Ž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
(92j:03059), http://dx.doi.org/10.2307/2274903
 [Ži]
, Hyperfinite transversal theory. II (in preparation).
 [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), 323325. MR 0379781 (52:686)
 [Ha]
 P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 2630.
 [He]
 C. W. Henson, Analytic sets, Baire sets, and the standard part map, Canad. J. Math. 31 (1979), 663672. 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, SpringerVerlag, 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), 11671180. MR 1026596 (91c:03040)
 [Ki]
 H. A. Kirstead, An effective version of Hall's theorem, Proc. Amer. Math. Soc. 88 (1983), 124128. MR 691291 (84g:03065)
 [LaRo]
 D. Landers and L. Rogge, Universal Loebmeasurability of sets and of the standard part map with applications, Trans. Amer. Math. Soc. 304 (1983), 229243. 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), 113122. 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), 615654. MR 0314610 (47:3161)
 [Mi]
 L. Mirski, Transversal theory, Academic Press, 1971. MR 0282853 (44:87)
 [NW]
 C. NashWilliams, Unexplored and semiexplored 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), 6191.
 [Ro]
 D. Ross, (private communication).
 [StBa]
 K. D. Stroyan and J. M. Bayod, Foundations of infinitesimal stochastic analysis, NorthHolland, 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]
 B. Živaljević, Rado's theorem for the Loeb space of an internal finitely additive measure space, Proc. Amer. Math. Soc. 112 (1991), 203207. MR 1056688 (91h:03092)
 [Ži]
 , The structure of graphs all of whose sections are internal sets, J. Symbolic Logic 56 (1991), 5066. MR 1131729 (92j:03059)
 [Ži]
 , 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
DOI:
http://dx.doi.org/10.1090/S00029947199210332371
PII:
S 00029947(1992)10332371
Article copyright:
© Copyright 1992
American Mathematical Society
