User:CRGreathouse/Large and small sets

In many branches of mathematics there are different formalizations of the intuitive concepts of large and small. They are generally set ideals, or their generalization over classes.

Set theory

In set theory, the natural definition of size is cardinality. Cantor's theorem means that there are an infinite number of different cardinalities. The generalized continuum hypothesis restricts the number of different cardinalities, if used. Large sets are usually taken to mean uncountable sets in this context, where countable and finite sets are small.

Alternately, consider cofinite sets: a set is large if its complement (with respect to some universe, usually the natural numbers) is finite. Similarly, in uncountable universes cocountable sets could be considered large.

Porous set are another type of 'small' set.

Measure theory

Main article: Natural density

In measure theory as well as many other fields like number theory a probabilistic definition is useful. Consider the chance of choosing an element of the set out of the first n natural numbers, then take the limit of this value as $n\to \infty$. Large sets have positive density, while small sets have density zero. Thus the even numbers are large (with density 0.5) while the primes are small (density 0 by the prime number theorem). Sets of density 1 are almost sure to be chosen if a random natural number is selected. Because the density may not exist in general, the upper density is often used instead. Instead of the limit, the lim sup is taken.

Szemerédi's theorem means that all large sets have arbitrarily long arithmetic progressions.

Combinatorics

Main article: Small set (combinatorics)

In combinatorics, subsets of the natural numbers are most commonly studied. This shows a limitation of cardinality as a measure of size, since the infinite subsets are always of cardinality $\aleph _{0}$. Even density is problematic since many interesting sequences are of zero density despite having different intuitive sizes. The usual combinatorial definition of a large set is one with a divergent reciprocal sum, with the corresponding definition of a small set as one with a convergent reciprocal sum. Thus the natural numbers are large (since the harmonic series diverges), the prime numbers are large (proof) but the squares are small (see the Basel problem). By Brun's theorem, the set of twin primes is small.

Erdős conjecture on arithmetic progressions, if proved, would mean that all large sets have arbitrarily long arithmetic progressions. The special case where the large set is the primes is the Green–Tao theorem.

Additive number theory

In additive number theory, a set is large if it is an additive basis, that is, if there exists a finite number d such that every natural number is a sum of at most d elements from the set. The least such d is called its degree. Alternately, a set is an additive basis if a finite sumset of the set equals the natural numbers.

Lagrange's four-square theorem is that the squares are large with degree four. Waring's problem is a generalization that looks for the size of the powers in this measure. The cubes are thus smaller than the squares in this sense, since their degree is larger (9). An example of a small set in this sense is the powers of 2. (See also IP set.)

A complete sequence is a sequence for which all sufficiently large numbers can be expressed as the sum of some subsequence. Essentially it is an additive basis of order ω.

Group theory

Main article: Slender group

Category theory

Main article: Small set (category theory)

Topology

Main articles: Meagre set and prevalent and shy sets

Ramsey theory

Main article: Large set (Ramsey theory)

In Ramsey theory, a set is large if any finite partition of the natural numbers has at least one part with arbitrarily-long arithmetic sequences with differences in the set. The natural numbers are large by Van der Waerden's theorem.

Others

A syndetic or piecewise syndetic set may be considered large, as may a thick set.

See also

• Large category

Further expansion

• Beiglböck, Bergelson, Hindman, and Strauss. "Multiplicative structures in additively large sets", Journal of Combinatorial Theory Series A, Vol. 113, No. 7 (Oct 2006), pp. 1219–1242.
• Ergodic Theory and the Properties of Large Sets