Finite set

related topics
{math, number, function}
{theory, work, human}

In mathematics, a finite set is a set that has a finite number of elements. For example,

is a finite set with five elements. The number of elements of a finite set is a natural number (non-negative integer), and is called the cardinality of the set. A set that is not finite is called infinite. For example, the set of all positive integers is infinite:

Finite sets are particularly important in combinatorics, the mathematical study of counting. Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set.

Contents

Definition and terminology

Formally, a set S is called finite if there exists a bijection

for some natural number n. The number n is called the cardinality of the set, and is denoted |S|. (Note that the empty set is considered finite, with cardinality zero.) If a set is finite, its elements may be written as a sequence:

In combinatorics, a finite set with n elements is sometimes called an n-set. For example, the set {5,6,7} is a 3-set, a finite set with three elements.

Basic properties

Any proper subset of a finite set S is finite and has fewer elements than S itself. As a consequence, there cannot exist a bijection between a finite set S and a proper subset of S. Any set with this property is called Dedekind-finite. Using the standard ZFC axioms for set theory, every Dedekind-finite set is also finite, but this requires the axiom of choice (or at least the axiom of dependent choice).

Any injective function between two finite sets of the same cardinality is also a surjection, and similarly any surjection between two finite sets of the same cardinality is also an injection.

The union of two finite sets is finite, with

In fact:

More generally, the union of any finite number of finite sets is finite. The Cartesian product of finite sets is also finite, with:

Full article ▸

related documents
Imaginary unit
Multiplication
Exponentiation by squaring
P = NP problem
Quadratic equation
General linear group
Relational database
Busy beaver
AWK
Control flow
Lie algebra
Riemannian manifold
Semidirect product
Category theory
Communication complexity
Polyomino
Monoid
Exponential function
Interpolation
Stochastic process
Operator
Set (mathematics)
Metric space
Dylan (programming language)
Dirac delta function
Vacuous truth
Multiplication algorithm
Taylor's theorem
Support vector machine
Mathematical constant