IP set

IP set

In mathematics, an IP set is a set of natural numbers which contains all finite sums of some infinite 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 subset of "D". The set of all finite sums over "D" is often denoted as FS("D").

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".

Some authors give a slightly different definition of IP sets. They require that FS("D") equal "A" instead of just being a subset.

The name IP-set was coined by Furstenberg and Weiss to abbreviate "Infinite-dimensional Parallelepiped".

Hindman's Theorem

If S, is an IP set and S = C_1 cup C_2 cup ... 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.

Since the set of natural numbers itself is an IP-set and partitions can also be seen as colorings, we 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 of the "n" colors. 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 states that the class of IP sets is partition regular.


The definition of being IP has been extended from subsets of the special semigroup of natural numbers with addition to subsets of semigroups and partial semigroups in general.

See also

* Syndetic set
* Piecewise syndetic set
* Thick set
* Ergodic Ramsey theory


* V. Bergelson, I. J. H. Knutson, R. McCutcheon " [http://home.hia.no/~ingerjh/forskning/bhm2jun03.pdf Simultaneous diophantine approximation and VIP Systems] " "Acta Arith." 116, Academia Scientiarum Polona, (2005), 13-23
* V. Bergelson, " [http://www.math.ohio-state.edu/~vitaly/vbkatsiveli20march03.pdf Minimal Idempotents and Ergodic Ramsey Theory] " "Topics in Dynamics and Ergodic Theory 8-39, London Math. Soc. Lecture Note Series 310", Cambridge Univ. Press, Cambridge, (2003)
* V. Bergelson, N. Hindman, " [http://members.aol.com/nhfiles2/pdf/large.pdf Partition regular structures contained in large sets are abundant] " "J. Comb. Theory (Series A)" 93 (2001), pp. 18-36
* H. Furstenberg, B. Weiss, "Topological Dynamics and Combinatorial Number Theory", "J. d'Analyse Math." 34 (1978), pp. 61-85
* J. McLeod, " [http://www.mtholyoke.edu/%7Ejmcleod/somenotionsofsize.pdf Some Notions of Size in Partial Semigroups] ", "Topology Proceedings", Vol. 25 (2000), pp. 317-332

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Set — (s[e^]t), v. t. [imp. & p. p. {Set}; p. pr. & vb. n. {Setting}.] [OE. setten, AS. setton; akin to OS. settian, OFries. setta, D. zetten, OHG. sezzen, G. setzen, Icel. setja, Sw. s[ a]tta, Dan. s?tte, Goth. satjan; causative from the root of E.… …   The Collaborative International Dictionary of English

  • Set — (s[e^]t), v. t. [imp. & p. p. {Set}; p. pr. & vb. n. {Setting}.] [OE. setten, AS. setton; akin to OS. settian, OFries. setta, D. zetten, OHG. sezzen, G. setzen, Icel. setja, Sw. s[ a]tta, Dan. s?tte, Goth. satjan; causative from the root of E.… …   The Collaborative International Dictionary of English

  • set — /set/, v., set, setting, n., adj., interj. v.t. 1. to put (something or someone) in a particular place: to set a vase on a table. 2. to place in a particular position or posture: Set the baby on his feet. 3. to place in some relation to something …   Universalium

  • Set (game) — Set! redirects here. Set! is also a special form in the Scheme programming language. Set is a real time card game designed by Marsha Falco and published by Set Enterprises in 1991. The deck consists of 81 cards varying in four features: number… …   Wikipedia

  • set — [ sɛt ] n. m. • 1893; mot anglais I ♦ Anglic. Manche d un match de tennis, de ping pong, de volley ball. Gagner le premier set. Partie de tennis en cinq sets. Balle de set, qui décide du gain du set. II ♦ Set ou set de table : ensemble des… …   Encyclopédie Universelle

  • set — Ⅰ. set [1] ► VERB (setting; past and past part. set) 1) put, lay, or stand in a specified place or position. 2) put, bring, or place into a specified state. 3) cause or instruct (someone) to do something. 4) give someone (a task) …   English terms dictionary

  • set — [set] vt. set, setting [ME setten < OE settan (akin to Ger setzen & Goth satjan < Gmc * satjan), caus. formation “to cause to sit” < base of SIT] 1. to place in a sitting position; cause to sit; seat 2. a) to cause (a fowl) to sit on… …   English World dictionary

  • set*/*/*/ — [set] (past tense and past participle set) verb I 1) [T] to put someone or something in a position, or to be in a particular place or position Tea s ready, he told them and set down the tray.[/ex] She set the baby on the floor to play.[/ex] 2)… …   Dictionary for writing and speaking English

  • Set — (s[e^]t), v. i. 1. To pass below the horizon; to go down; to decline; to sink out of sight; to come to an end. [1913 Webster] Ere the weary sun set in the west. Shak. [1913 Webster] Thus this century sets with little mirth, and the next is likely …   The Collaborative International Dictionary of English

  • Set — has 464 separate definitions in the Oxford English Dictionary, the most of any English word; its full definition comprises 10,000 words making it the longest definition in the OED. Set may refer to:In mathematics and science:*Set (mathematics), a …   Wikipedia

  • Set packing — is a classical NP complete problem in computational complexity theory and combinatorics, and was one of Karp s 21 NP complete problems. Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”