Milliken's tree theorem

Last updated

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:

Intuitively, for S to be strongly embedded in T,

Related Research Articles

In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

In mathematical analysis and in probability theory, a σ-algebra on a set X is a nonempty collection Σ of subsets of X closed under complement and closed under countable unions and countable intersections. The pair is called a measurable space.

Winding number Number of times a curve wraps around a point in the plane

In mathematics, the winding number or winding index of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point, i.e., the curve's number of turns. The winding number depends on the orientation of the curve, and it is negative if the curve travels around the point clockwise.

In differential geometry, a Riemannian manifold or Riemannian space(M, g), so called after the German mathematician Bernhard Riemann, is a real, smooth manifold M equipped with a positive-definite inner product gp on the tangent space TpM at each point p.

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. It was first used by Paul Cohen in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory.

De Rham cohomology Cohomology with real coefficients computed using differential forms

In mathematics, de Rham cohomology is a tool belonging both to algebraic topology and to differential topology, capable of expressing basic topological information about smooth manifolds in a form particularly adapted to computation and the concrete representation of cohomology classes. It is a cohomology theory based on the existence of differential forms with prescribed properties.

In mathematics, the adele ring of a global field is a central object of class field theory, a branch of algebraic number theory. It is the restricted product of all the completions of the global field, and is an example of a self-dual topological ring.

Foliation In mathematics, a type of equivalence relation on an n-manifold

In mathematics, a foliation is an equivalence relation on an n-manifold, the equivalence classes being connected, injectively immersed submanifolds, all of the same dimension p, modeled on the decomposition of the real coordinate space Rn into the cosets x + Rp of the standardly embedded subspace Rp. The equivalence classes are called the leaves of the foliation. If the manifold and/or the submanifolds are required to have a piecewise-linear, differentiable, or analytic structure then one defines piecewise-linear, differentiable, or analytic foliations, respectively. In the most important case of differentiable foliation of class Cr it is usually understood that r ≥ 1. The number p is called the dimension of the foliation and q = np is called its codimension.

In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers, conventionally written , where is the second Hebrew letter (beth). The beth numbers are related to the aleph numbers, but unless the generalized continuum hypothesis is true, there are numbers indexed by that are not indexed by .

In mathematics, a Sobolev space is a vector space of functions equipped with a norm that is a combination of Lp-norms of the function together with its derivatives up to a given order. The derivatives are understood in a suitable weak sense to make the space complete, i.e. a Banach space. Intuitively, a Sobolev space is a space of functions possessing sufficiently many derivatives for some application domain, such as partial differential equations, and equipped with a norm that measures both the size and regularity of a function.

In mathematics, in particular in nonlinear analysis, a Fréchet manifold is a topological space modeled on a Fréchet space in much the same way as a manifold is modeled on a Euclidean space.

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

In mathematics, a real or complex-valued function f on d-dimensional Euclidean space satisfies a Hölder condition, or is Hölder continuous, when there are nonnegative real constants C, α>0, such that

In mathematics, the Milliken–Taylor theorem in combinatorics is a generalization of both Ramsey's theorem and Hindman's theorem. It is named after Keith Milliken and Alan D. Taylor.

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, following Milliken (1979).

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals.

This is a glossary of set theory.

In the mathematical discipline of functional analysis, a differentiable vector-valued function from Euclidean space is a differentiable function valued in a topological vector space (TVS) whose domains is a subset of some finite-dimensional Euclidean space. It is possible to generalize the notion of derivative to functions whose domain and codomain are subsets of arbitrary topological vector spaces (TVSs) in multiple ways. But when the domain of a TVS-valued function is a subset of a finite-dimensional Euclidean space then many of these notions become logically equivalent resulting in a much more limited number of generalizations of the derivative and additionally, differentiability is also more well-behaved compared to the general case. This article presents the theory of -times continuously differentiable functions on an open subset of Euclidean space , which is an important special case of differentiation between arbitrary TVSs. This importance stems partially from the fact that every finite-dimensional vector subspace of a Hausdorff topological vector space is TVS isomorphic to Euclidean space so that, for example, this special case can be applied to any function whose domain is an arbitrary Hausdorff TVS by restricting it to finite-dimensional vector subspaces.

In mathematics, calculus on Euclidean space is a generalization of calculus of functions in one or several variables to calculus of functions on Euclidean space as well as a finite-dimensional real vector space. This calculus is also known as advanced calculus, especially in the United States. It is similar to multivariable calculus but is somehow more sophisticated in that it uses linear algebra more extensively and covers some concepts from differential geometry such as differential forms and Stokes' formula in terms of differential forms. This extensive use of linear algebra also allows a natural generalization of multivariable calculus to calculus on Banach spaces or topological vector spaces.

References

  1. Keith R. Milliken, A Ramsey Theorem for Trees J. Comb. Theory (Series A)26 (1979), 215-237
  2. Keith R. Milliken, A Partition Theorem for the Infinite Subtrees of a Tree, Trans. Amer. Math. Soc.263 No.1 (1981), 137-148.