In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, an IP set is a set of
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s which contains all finite sums of some
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set ...
.
The finite sums of a set ''D'' of natural numbers are all those numbers that can be obtained by adding up the elements of some finite
nonempty
In mathematics, the empty set or void set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, whi ...
subset
In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of ''D''.
The set of all finite sums over ''D'' is often denoted as FS(''D''). Slightly more generally, for a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
of natural numbers (''n
i''), one can consider the set of finite sums FS((''n
i'')), consisting of the sums of all finite length subsequences of (''n
i'').
A set ''A'' of natural numbers is an IP set if there exists an infinite set ''D'' such that FS(''D'') is a subset of ''A''. Equivalently, one may require that ''A'' contains all finite sums FS((''n
i'')) of a sequence (''n
i'').
Some authors give a slightly different definition of IP sets: They require that FS(''D'') equal ''A'' instead of just being a subset.
The term IP set was coined by
Hillel Furstenberg
Hillel "Harry" Furstenberg (; born September 29, 1935) is a German-born American-Israeli mathematician and professor emeritus at the Hebrew University of Jerusalem. He is a member of the Israel Academy of Sciences and Humanities and U.S. Natio ...
and
Benjamin Weiss
Benjamin Weiss (; born 1941) is an American-Israeli mathematician known for his contributions to ergodic theory, topological dynamics, probability theory, game theory, and descriptive set theory.
Biography
Benjamin ("Benjy") Weiss was born in N ...
to abbreviate "infinite-dimensional
parallelepiped". Serendipitously, the abbreviation IP can also be expanded to "idempotent" (a set is an IP if and only if it is a member of an idempotent
ultrafilter
In the Mathematics, mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a Maximal element, maximal Filter (mathematics), filter on P; that is, a proper filter on P th ...
).
Hindman's theorem
If
is an IP set and
, then at least one
is an IP set.
This is known as ''Hindman's theorem'' or the ''finite sums theorem''.
In different terms, Hindman's theorem states that the class of IP sets is
partition regular
In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a set system, collection of sets.
Given a set X, a collection of subsets \mathbb \subset \mathcal(X) is called ''partition regular'' if every set ''A'' ...
.
Since the set of natural numbers itself is an IP set and partitions can also be seen as colorings, one can reformulate a special case of Hindman's theorem in more familiar terms: Suppose the natural numbers are "colored" with ''n'' different colors; each natural number gets one and only one color. Then there exists a color ''c'' and an infinite set ''D'' of natural numbers, all colored with ''c'', such that every finite sum over ''D'' also has color ''c''.
Hindman's theorem is named for mathematician
Neil Hindman, who
proved it in 1974.
The
Milliken–Taylor theorem
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.
Let \mathcal_f(\mathbb) denote the set of finite subsets of ...
is a common generalisation of Hindman's theorem and
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
.
Semigroups
The definition of being IP has been extended from subsets of the special
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively (just notation, not necessarily th ...
of natural numbers with addition to subsets of semigroups and partial semigroups in general. A variant of Hindman's theorem is true for arbitrary semigroups.
See also
*
Ergodic Ramsey theory
Ergodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.
History
Ergodic Ramsey theory arose shortly after Endre Szemerédi's proof that a set of positive upper density ...
*
Piecewise syndetic set In mathematics, piecewise syndeticity is a notion of largeness of subsets of the natural numbers.
A set S \sub \mathbb is called ''piecewise syndetic'' if there exists a finite subset ''G'' of \mathbb such that for every finite subset ''F'' of \mat ...
*
Syndetic set
In mathematics, a syndetic set is a subset of the natural numbers having the property of "bounded gaps": that the sizes of the gaps in the sequence of natural numbers is bounded.
Definition
A set S \sub \mathbb is called syndetic if for some finit ...
*
Thick set
In mathematics, a thick set is a set of integers that contains arbitrarily long intervals. That is, given a thick set T, for every p \in \mathbb, there is some n \in \mathbb such that \ \subset T.
Examples
Trivially \mathbb is a thick set. Other ...
References
Further reading
*
*
*
*
{{DEFAULTSORT:Ip Set
Semigroup theory
Ergodic theory
Ramsey theory