In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Dickson's lemma states that every set of
-tuples of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s has finitely many
minimal element
In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defin ...
s. This simple fact from
combinatorics has become attributed to the American algebraist
L. E. Dickson
Leonard Eugene Dickson (January 22, 1874 – January 17, 1954) was an American mathematician. He was one of the first American researchers in abstract algebra, in particular the theory of finite fields and classical groups, and is also reme ...
, who used it to
prove a result in
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
about
perfect number
In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number.
T ...
s.
However, the
lemma was certainly known earlier, for example to
Paul Gordan
__NOTOC__
Paul Albert Gordan (27 April 1837 – 21 December 1912) was a Jewish-German mathematician, a student of Carl Jacobi at the University of Königsberg before obtaining his PhD at the University of Breslau (1862),. and a professor ...
in his research on
invariant theory
Invariant theory is a branch of abstract algebra dealing with actions of groups on algebraic varieties, such as vector spaces, from the point of view of their effect on functions. Classically, the theory dealt with the question of explicit descri ...
.
[.]
Example
Let
be a fixed number, and let
be the set of pairs of numbers whose product is at least
. When defined over the positive
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s,
has infinitely many minimal elements of the form
, one for each positive number
; this set of points forms one of the branches of a
hyperbola
In mathematics, a hyperbola (; pl. hyperbolas or hyperbolae ; adj. hyperbolic ) is a type of smooth curve lying in a plane, defined by its geometric properties or by equations for which it is the solution set. A hyperbola has two pieces, ca ...
. The pairs on this hyperbola are minimal, because it is not possible for a different pair that belongs to
to be less than or equal to
in both of its coordinates. However, Dickson's lemma concerns only tuples of natural numbers, and over the natural numbers there are only finitely many minimal pairs. Every minimal pair
of natural numbers has
and
, for if ''x'' were greater than ''K'' then (''x'' − 1, ''y'') would also belong to ''S'', contradicting the minimality of (''x'', ''y''), and symmetrically if ''y'' were greater than ''K'' then (''x'', ''y'' − 1) would also belong to ''S''. Therefore, over the natural numbers,
has at most
minimal elements, a finite number.
[With more care, it is possible to show that one of and is at most , and that there is at most one minimal pair for each choice of one of the coordinates, from which it follows that there are at most minimal elements.]
Formal statement
Let
be the set of non-negative integers (
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s), let ''n'' be any fixed constant, and let
be the set of
-tuples of natural numbers. These tuples may be given a
pointwise In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined ...
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
, the
product order
In mathematics, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, ''Introduction to Lattices and Order'' (Second Edition), 2002, p. 18 or componentwise order) is a partial ordering o ...
, in which
if and only if
for every
.
The set of tuples that are greater than or equal to some particular tuple
forms a positive
orthant
In geometry, an orthant or hyperoctant is the analogue in ''n''-dimensional Euclidean space of a quadrant in the plane or an octant in three dimensions.
In general an orthant in ''n''-dimensions can be considered the intersection of ''n'' mutua ...
with its apex at the given tuple.
With this notation, Dickson's lemma may be stated in several equivalent forms:
*In every
non-empty
In mathematics, the empty 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, while in other t ...
subset of
there is at least one but no more than a finite number of elements that are
minimal element
In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defin ...
s of
for the pointwise partial order.
*For every infinite sequence
of
-tuples of natural numbers, there exist two indices