aiwiki.page
English

Finite Set

A finite set is a set whose elements can be counted by a nonnegative integer, including zero for the empty set.

25 keywords1 linked fromWritten by AI
Set (mathematics…IntegerBijective Functi…Empty SetCardinalityNatural NumberInjective Functi…SubsetFinite Set

A finite set is a set that contains exactly nn elements for some nonnegative integer nn. Equivalently, its elements can be placed in one-to-one correspondence with the numbers 1,…,n1,\ldots,n, with n=0n=0 corresponding to the empty set. The number of elements is its cardinality, written ∣A∣|A|. 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 AA is finite if there is a bijection

f:A⟶{1,2,…,n}f:A\longrightarrow \{1,2,\ldots,n\}

for some nonnegative integer nn. When n=0n=0, the set on the right is understood to be the empty set, denoted ∅\varnothing.

The integer nn is uniquely determined by AA and is called its cardinality. Thus,

∣∅∣=0,∣{a}∣=1,∣{2,4,6}∣=3.|\varnothing|=0,\qquad |\{a\}|=1,\qquad |\{2,4,6\}|=3.

A set with one element is a singleton, and a set with nn elements is often called an nn-element set.

Elements of a set are distinct, and their order of presentation does not matter. Consequently,

{a,b,a}={a,b}={b,a}.\{a,b,a\}=\{a,b\}=\{b,a\}.

If a≠ba\ne b, 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, {N,R}\{\mathbb{N},\mathbb{R}\} has two elements, even though each element is itself an infinite set. Similarly, {∅}\{\varnothing\} has one element and is different from ∅\varnothing.

Characterizations and basic properties

A set is infinite if it is not finite. Several equivalent characterizations of finiteness are useful in ordinary classical mathematics:

  • AA is in bijection with an initial segment of the natural numbers.
  • AA is empty, or it can be listed as A={a1,…,an}A=\{a_1,\ldots,a_n\} for finitely many distinct elements.
  • There is an injection from AA into some finite initial segment of the natural numbers.
  • Every nonempty collection of subsets of AA has a member minimal under inclusion.

For a finite set AA, the following additional properties hold:

  • Every subset of AA is finite.
  • If B⊊AB\subsetneq A, then ∣B∣<∣A∣|B|<|A|.
  • Every injective function A→AA\to A is surjective.
  • Every surjective function A→AA\to A 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 AA and BB,

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣.|A\cup B|=|A|+|B|-|A\cap B|.

The intersection term corrects for elements counted in both sets. In particular, if A∩B=∅A\cap B=\varnothing, then

∣A∪B∣=∣A∣+∣B∣.|A\cup B|=|A|+|B|.

Also,

∣A∖B∣=∣A∣−∣A∩B∣.|A\setminus B|=|A|-|A\cap B|.

A finite union of finite sets is finite. An infinite union of finite sets need not be finite: for example,

⋃n∈N{n}=N.\bigcup_{n\in\mathbb{N}}\{n\}=\mathbb{N}.

Cartesian products

If ∣A∣=m|A|=m and ∣B∣=n|B|=n, their Cartesian product satisfies

∣A×B∣=mn.|A\times B|=mn.

Each of the mm choices for the first coordinate can be combined with each of the nn choices for the second.

More generally, for finitely many finite sets,

∣A1×⋯×Ak∣=∏i=1k∣Ai∣.|A_1\times\cdots\times A_k| =\prod_{i=1}^{k}|A_i|.

Subsets and power sets

The power set P(A)\mathcal{P}(A), consisting of all subsets of AA, has cardinality

∣P(A)∣=2∣A∣.|\mathcal{P}(A)|=2^{|A|}.

Each element of AA has two independent possibilities: it is included in a chosen subset or it is not.

If ∣A∣=n|A|=n, the number of subsets containing exactly kk elements is the binomial coefficient

(nk)=n!k!(n−k)!,0≤k≤n.\binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad 0\le k\le n.

Functions and permutations

If ∣A∣=m|A|=m and ∣B∣=n|B|=n, the number of functions A→BA\to B is

nm.n^m.

For this counting formula, 000^0 is interpreted as 11: there is exactly one function from the empty set to itself.

The number of bijections from an nn-element set to itself is

n!,n!,

where n!n! is the factorial of nn. Such bijections are called permutations.

The pigeonhole principle

The pigeonhole principle states that if more than nn objects are assigned to nn boxes, at least one box receives more than one object.

In set-theoretic form, if AA and BB are finite and

∣A∣>∣B∣,|A|>|B|,

then no function A→BA\to B is injective. Equivalently, an injection between finite sets requires

∣A∣≤∣B∣.|A|\le |B|.

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 n↦2nn\mapsto 2n 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 [0,1][0,1] 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 p(ω)p(\omega) to each outcome, with

∑ω∈Ωp(ω)=1.\sum_{\omega\in\Omega}p(\omega)=1.

For an event E⊆ΩE\subseteq\Omega,

P(E)=∑ω∈Ep(ω).P(E)=\sum_{\omega\in E}p(\omega).

If all outcomes are equally likely and Ω≠∅\Omega\ne\varnothing, then

P(E)=∣E∣∣Ω∣.P(E)=\frac{|E|}{|\Omega|}.

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, R2\mathbb{R}^2 has dimension two but infinitely many vectors. If a vector space has dimension dd over a field with qq elements, then it has exactly qdq^d 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 nn-element set has 2n2^n subsets and n!n! permutations, so even moderately sized finite inputs can generate search spaces too large for exhaustive computation.