HOME

TheInfoList



OR:

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 (''ni''), one can consider the set of finite sums FS((''ni'')), consisting of the sums of all finite length subsequences of (''ni''). 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((''ni'')) of a sequence (''ni''). 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 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.


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