Halpern–Läuchli 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 or HLLP (named after James D. Halpern, Hans Läuchli, Richard Laver, and David Pincus), following (Milliken 1979).
Let d,r < ω, [math]\displaystyle{ \langle T_i: i \in d \rangle }[/math] be a sequence of finitely splitting trees of height ω. Let
- [math]\displaystyle{ \bigcup_{n \in \omega} \left(\prod_{i\lt d}T_i(n)\right) = C_1 \cup \cdots \cup C_r, }[/math]
then there exists a sequence of subtrees [math]\displaystyle{ \langle S_i: i \in d \rangle }[/math] strongly embedded in [math]\displaystyle{ \langle T_i: i \in d \rangle }[/math] such that
- [math]\displaystyle{ \bigcup_{n \in \omega} \left(\prod_{i\lt d}S_i(n)\right) \subset C_k\text{ for some }k \le r. }[/math]
Alternatively, let
- [math]\displaystyle{ S^d_{\langle T_i: i \in d \rangle} = \bigcup_{n \in \omega} \left(\prod_{i\lt d}T_i(n)\right) }[/math]
and
- [math]\displaystyle{ \mathbb{S}^d=\bigcup_{\langle T_i: i \in d \rangle} S^d_{\langle T_i: i \in d \rangle}. }[/math].
The HLLP theorem says that not only is the collection [math]\displaystyle{ \mathbb{S}^d }[/math] partition regular for each d < ω, but that the homogeneous subtree guaranteed by the theorem is strongly embedded in
- [math]\displaystyle{ T= \langle T_i: i \in d \rangle. }[/math]
References
- Halpern, James D.; Läuchli, Hans (1966), "A partition theorem", Transactions of the American Mathematical Society 124: 360–367, doi:10.1090/s0002-9947-1966-0200172-2
- Milliken, Keith R. (1979), "A Ramsey theorem for trees", Journal of Combinatorial Theory, Series A 26 (3): 215–237, doi:10.1016/0097-3165(79)90101-8
- Milliken, Keith R. (1981), "A partition theorem for the infinite subtrees of a tree", Transactions of the American Mathematical Society 263 (1): 137–148, doi:10.1090/s0002-9947-1981-0590416-8
- Pincus, David; Halpern, James D. (1981), "Partitions of products", Transactions of the American Mathematical Society 267 (2): 549–568, doi:10.1090/s0002-9947-1981-0626489-3
 |  |
