A finite set is a set that contains exactly elements for some nonnegative integer . Equivalently, its elements can be placed in one-to-one correspondence with the numbers , with corresponding to the empty set. The number of elements is its cardinality, written . Finite sets provide the foundation for counting and occur throughout mathematics, from elementary arithmetic to algebra, probability, and computation.
Definition and notation
Formally, a set is finite if there is a bijection
for some nonnegative integer . When , the set on the right is understood to be the empty set, denoted .
The integer is uniquely determined by and is called its cardinality. Thus,
A set with one element is a singleton, and a set with elements is often called an -element set.
Elements of a set are distinct, and their order of presentation does not matter. Consequently,
If , each of these expressions denotes a set with two elements, not three.
Finiteness concerns the number of elements, not their nature or size. For example, has two elements, even though each element is itself an infinite set. Similarly, has one element and is different from .
Characterizations and basic properties
A set is infinite if it is not finite. Several equivalent characterizations of finiteness are useful in ordinary classical mathematics:
- is in bijection with an initial segment of the natural numbers.
- is empty, or it can be listed as for finitely many distinct elements.
- There is an injection from into some finite initial segment of the natural numbers.
- Every nonempty collection of subsets of has a member minimal under inclusion.
For a finite set , the following additional properties hold:
- Every subset of is finite.
- If , then .
- Every injective function is surjective.
- Every surjective function is injective.
The last two properties express the fact that, on a finite set, an injective self-map cannot leave any element out, and a surjective self-map cannot identify two distinct elements.
Proofs about finite sets frequently use mathematical induction on their cardinality. The empty set supplies the base case; removing one element from a nonempty finite set reduces its cardinality by one.
Counting and set operations
Finite sets remain finite under the standard operations of taking subsets, finite unions, Cartesian products, and power sets.
Unions and differences
For finite sets and ,
The intersection term corrects for elements counted in both sets. In particular, if , then
Also,
A finite union of finite sets is finite. An infinite union of finite sets need not be finite: for example,
Cartesian products
If and , their Cartesian product satisfies
Each of the choices for the first coordinate can be combined with each of the choices for the second.
More generally, for finitely many finite sets,
Subsets and power sets
The power set , consisting of all subsets of , has cardinality
Each element of has two independent possibilities: it is included in a chosen subset or it is not.
If , the number of subsets containing exactly elements is the binomial coefficient
Functions and permutations
If and , the number of functions is
For this counting formula, is interpreted as : there is exactly one function from the empty set to itself.
The number of bijections from an -element set to itself is
where is the factorial of . Such bijections are called permutations.
The pigeonhole principle
The pigeonhole principle states that if more than objects are assigned to boxes, at least one box receives more than one object.
In set-theoretic form, if and are finite and
then no function is injective. Equivalently, an injection between finite sets requires
This principle underlies many existence arguments in combinatorics. It also explains why no finite set can be in bijection with one of its proper subsets. Infinite sets can behave differently: the map gives a bijection from the natural numbers to the even natural numbers.
Finiteness, countability, and foundations
Under the common convention that countable means “finite or countably infinite,” every finite set is a countable set. Some authors instead use “countable” to mean only countably infinite, so the intended convention matters.
Finiteness is stronger than being bounded. For example, the real interval is bounded but contains infinitely many elements. Conversely, any set with only finitely many real elements is finite regardless of how large those elements are.
Dedekind finiteness and choice
A set is Dedekind-finite if it is not in bijection with any proper subset of itself. Every finite set is Dedekind-finite.
In Zermelo–Fraenkel set theory with the axiom of choice, Dedekind finiteness is equivalent to finiteness. Without a suitable choice principle, the converse is not generally provable: there are models of Zermelo–Fraenkel set theory containing infinite Dedekind-finite sets. Thus, “not equinumerous with a proper subset” must be distinguished from the standard definition of finite when foundational assumptions are important.
No axiom of choice is needed to choose one element from each member of a finite family of nonempty sets. This differs from choosing elements from an arbitrary infinite family, even when every member of that family is finite.
Roles in mathematics and computation
Probability
A finite sample space allows a probability model to be specified by assigning a nonnegative number to each outcome, with
For an event ,
If all outcomes are equally likely and , then
Finiteness alone does not imply that outcomes are equally likely.
Algebra and geometry
A finite field is a field whose underlying set is finite. More generally, many algebraic structures are studied by considering operations on finite sets.
A finite-dimensional vector space, however, need not be a finite set. For example, has dimension two but infinitely many vectors. If a vector space has dimension over a field with elements, then it has exactly elements.
In topology, every finite subset of any topological space is compact. Every finite subset of a Hausdorff space is also closed.
Computation
Finite sets serve as domains for exhaustive search, finite-state models, and many discrete data structures. A search over an explicitly enumerable finite set can terminate after inspecting every candidate, but finiteness does not guarantee practical feasibility. An -element set has subsets and permutations, so even moderately sized finite inputs can generate search spaces too large for exhaustive computation.