Halpern–Läuchli theorem

From Wikipedia, the free encyclopedia

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 or HLLP (named after James D. Halpern, Hans Läuchli, Richard Laver, and David Pincus), following (Milliken 1979).

Let d,r < ω, $\langle T_{i}:i\in d\rangle$ be a sequence of finitely splitting trees of height ω. Let

$\bigcup _{{n\in \omega }}\left(\prod _{{i<d}}T_{i}(n)\right)=C_{1}\cup \cdots \cup C_{r},$

then there exists a sequence of subtrees $\langle S_{i}:i\in d\rangle$ strongly embedded in $\langle T_{i}:i\in d\rangle$ such that

$\bigcup _{{n\in \omega }}\left(\prod _{{i<d}}S_{i}(n)\right)\subset C_{k}{\text{ for some }}k\leq r.$

Alternatively, let

$S_{{\langle T_{i}:i\in d\rangle }}^{d}=\bigcup _{{n\in \omega }}\left(\prod _{{i<d}}T_{i}(n)\right)$

and

${\mathbb {S}}^{d}=\bigcup _{{\langle T_{i}:i\in d\rangle }}S_{{\langle T_{i}:i\in d\rangle }}^{d}.$ .

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\rangle .\$

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.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.