Born rule: Difference between revisions
en>Bibcode Bot m Adding 1 arxiv eprint(s), 0 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot |
en>"alyosha" m Copyedit (minor) |
||
Line 1: | Line 1: | ||
In [[mathematics]], '''Milliken's tree theorem''' in [[combinatorics]] is a partition theorem generalizing [[Ramsey's theorem]] to infinite [[Tree (set theory)|trees]], objects with more structure than [[Set (mathematics)|sets]]. | |||
Let T be a finitely splitting rooted tree of height ω, n a positive integer, and <math>\mathbb{S}^n_T</math> the collection of all strongly embedded subtrees of T of height n. In one of its simple forms, Milliken's tree theorem states that if <math>\mathbb{S}^n_T=C_1 \cup ... \cup C_r</math> then for some strongly embedded infinite subtree R of T, <math>\mathbb{S}^n_R \subset C_i</math> for some i ≤ r. | |||
This immediately implies [[Ramsey's theorem]]; take the tree T to be a linear ordering on ω vertices. | |||
Define <math>\mathbb{S}^n= \bigcup_T \mathbb{S}^n_T</math> where T ranges over finitely splitting rooted trees of height ω. Milliken's tree theorem says that not only is <math>\mathbb{S}^n</math> [[partition regular]] for each n < ω, but that the homogeneous subtree R guaranteed by the theorem is '''strongly embedded''' in T. | |||
== Strong embedding == | |||
Call T an α-tree if each branch of T has cardinality α. Define Succ(p, P)= <math> \{ q \in P : q \geq p \}</math>, and <math>IS(p,P)</math> to be the set of immediate successors of p in P. Suppose S is an α-tree and T is a β-tree, with 0 ≤ α ≤ β ≤ ω. S is ''strongly embedded'' in T if: | |||
* <math>S \subset T</math>, and the partial order on S is induced from T, | |||
* if <math>s \in S</math> is nonmaximal in S and <math>t \in IS(s,T)</math>, then <math>|Succ(t,T) \cap IS(s,S)|=1</math>, | |||
* there exists a strictly increasing function from <math>\alpha</math> to <math>\beta</math>, such that <math>S(n) \subset T(f(n)).</math> | |||
Intuitively, for S to be strongly embedded in T, | |||
* S must be a subset of T with the induced partial order | |||
* S must preserve the branching structure of T; ''i.e.'', if a nonmaximal node in S has n immediate successors in T, then it has n immediate successors in S | |||
* S preserves the level structure of T; all nodes on a common level of S must be on a common level in T. | |||
==References== | |||
#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. | |||
[[Category:Ramsey theory]] | |||
[[Category:Theorems in discrete mathematics]] | |||
[[Category:Trees (set theory)]] |
Revision as of 19:36, 28 September 2013
In mathematics, Milliken's tree theorem in combinatorics is a partition theorem generalizing Ramsey's theorem to infinite trees, objects with more structure than sets.
Let T be a finitely splitting rooted tree of height ω, n a positive integer, and the collection of all strongly embedded subtrees of T of height n. In one of its simple forms, Milliken's tree theorem states that if then for some strongly embedded infinite subtree R of T, for some i ≤ r.
This immediately implies Ramsey's theorem; take the tree T to be a linear ordering on ω vertices.
Define where T ranges over finitely splitting rooted trees of height ω. Milliken's tree theorem says that not only is partition regular for each n < ω, but that the homogeneous subtree R guaranteed by the theorem is strongly embedded in T.
Strong embedding
Call T an α-tree if each branch of T has cardinality α. Define Succ(p, P)= , and to be the set of immediate successors of p in P. Suppose S is an α-tree and T is a β-tree, with 0 ≤ α ≤ β ≤ ω. S is strongly embedded in T if:
- , and the partial order on S is induced from T,
- if is nonmaximal in S and , then ,
- there exists a strictly increasing function from to , such that
Intuitively, for S to be strongly embedded in T,
- S must be a subset of T with the induced partial order
- S must preserve the branching structure of T; i.e., if a nonmaximal node in S has n immediate successors in T, then it has n immediate successors in S
- S preserves the level structure of T; all nodes on a common level of S must be on a common level in T.
References
- 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.