Halpern-Lauchli theorem

In mathematics, the Halpern-Läuchli theorem is a partition result about finite products of infinite trees. Its original purpose was to give a model for set theory in which the Boolean prime ideal theorem is true but the axiom of choice is false. It is often called the Halpern-Läuchli theorem, but the proper attribution for the theorem as it is formulated below is to Halpern-Läuchli-Laver-Pincus (HLLP), following (Milliken 1979).

Let d,r < ω, langle T_i: i in d angle be a sequence of finitely splitting trees of height ω. Let :igcup_{n in omega} (prod_{ithen there exists a sequence of subtrees langle S_i: i in d angle strongly embedded in langle T_i: i in d angle such that:igcup_{n in omega} (prod_{i for some k ≤ r.

Alternatively, let S^d_{langle T_i: i in d angle} = igcup_{n in omega} (prod_{i and mathbb{S}^d=igcup_{langle T_i: i in d angle} S^d_{langle T_i: i in d angle}. The HLLP theorem says that not only is the collection mathbb{S}^d partition regular for each d<ω, but that the homogeneous subtree guaranteed by the theorem is strongly embedded in T= langle T_i: i in d angle.

References

#J.D. Halpern and H. Läuchli, A partition theorem, "Trans. Amer. Math. Soc." 124 (1966), 360-367
#Keith R. Milliken, A Ramsey Theorem for Trees, "J. Comb. Theory (Series A)" 26 (1979), 215-237
#Keith R. Milliken, A Partition Theorem for the Infinite Subtrees of a Tree, "Trans. Amer. Math. Soc." 263 No.1 (1981), 137-148
#J.D. Halpern and David Pincus, Partitions of Products, "Trans. Amer. Math. Soc." 267, No.2 (1981), 549-568.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Partition regular — In mathematics, the notion of partition regularity in combinatorics is one approach to explaining when a set system is quite large.Given a set X, a collection of subsets mathbb{S} subset mathcal{P}(X) is called partition regular if for any A in… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.