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

S

is an IP set and

S = C_1 \cup C_2 \cup \cdots \cup C_n

, then at least one

C_i

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.

Hindman's theorem

Semigroups

See also

References

Further reading