A finite set, in the grand, often tedious, landscape of mathematics and specifically within the labyrinthine corridors of set theory , is a set that contains a finite quantity of elements . To put it plainly, if you could, in theory, muster the patience to count its members and actually reach an end to the process, you’re dealing with a finite set. Consider, for instance, the collection {2, 4, 6, 8, 10}. It’s finite, and it has precisely five elements. This count, this final number you arrive at after your Herculean effort, is known as the cardinality or the cardinal number of the set. If a set refuses to be counted down to a final number, if the counting never ceases, then it’s an infinite set . The set of all positive integers, {1, 2, 3, …}, is a prime example of such an endless endeavor.

Finite sets are the bedrock of combinatorics , that branch of mathematics dedicated to the art of counting . Within this field, the pigeonhole principle often makes its appearance. It’s a rather elegant, if sometimes blunt, instrument that states you can’t cram more pigeons than there are pigeonholes without at least one hole getting more than one pigeon. More formally, it asserts that there cannot be an injective function mapping elements from a larger finite set to a smaller one. It’s a matter of basic arithmetic, really, but framed in the language of sets and functions.

Definition and Terminology

The natural numbers themselves, those foundational building blocks, are abstract entities defined by the Peano axioms or constructed through set-theoretic means, such as the Von Neumann ordinals . Within this framework, a set S is formally declared finite if there exists a bijection —a perfect one-to-one correspondence—between S and the set {1, 2, …, n} for some natural number n. This is essentially the formalization of counting its elements, much like tallying them off on your fingers. If the set S is the empty set , this condition is met with n=0, the empty function serving as the bijection, a concept that is vacuously true. The number n, the size of this correspondence, is the cardinality of the set, usually denoted as |S|.

When a nonempty set S is finite, its elements can be arranged in a specific order, a sequence : x₁, x₂, …, x<0xE2><0x82><0x99>, where each xᵢ is an element of S and the index i ranges from 1 to n. If n is 2 or greater, it’s worth noting that multiple such sequences can exist, depending on how you choose to list them.

In the realm of combinatorics , a finite set with n elements is frequently referred to as an n-set. A subset of this set containing k elements is then, predictably, a k-subset. For example, the set {5, 6, 7} is a 3-set, and {6, 7} is a 2-subset of it.

The notation {1, …, n} for a set of the first n natural numbers can be defined recursively. It’s the empty set if n=0. If n is 1 or greater, it’s the union of the set {1, …, n-1} and the singleton set {n}. This recursive definition is crucial for many proofs and constructions involving finite sets.

Basic Properties

A proper subset of a finite set S is, by definition, also finite. Furthermore, it must contain fewer elements than S itself. This leads to a fundamental consequence: it is impossible to establish a bijection between a finite set S and one of its own proper subsets. Sets possessing this property—the inability to be put into a one-to-one correspondence with a proper subset of themselves—are termed Dedekind-finite . In the standard axiomatic framework of ZFC set theory , every Dedekind-finite set is indeed finite. However, this implication is not provable within ZF (Zermelo–Fraenkel axioms without the axiom of choice ) alone. The axiom of countable choice , a weaker version of the axiom of choice, is sufficient to establish this equivalence.

Consider two finite sets with the same cardinality. If you have an injective function mapping elements from one to the other, it is automatically also a surjective function (a surjection), and vice versa. They are, in essence, the same size.

The union of two finite sets is, unsurprisingly, finite. Its cardinality is bounded: |S ∪ T| ≤ |S| + |T|. More precisely, the inclusion–exclusion principle gives us the exact size: |S ∪ T| = |S| + |T| - |S ∩ T|. This principle extends to any finite collection of finite sets; their union will always be finite. The Cartesian product of finite sets also yields a finite set, with the cardinality |S × T| = |S| × |T|. This extends to multiple finite sets as well. For a finite set S with n elements, its power set , denoted ℘(S), which is the set of all its subsets, is also finite, possessing exactly 2ⁿ elements, or 2^|S|.

Crucially, any subset of a finite set is itself finite. Likewise, if you apply a function to every element of a finite set, the resulting set of values will also be finite.

All finite sets are considered countable , meaning their elements can be put into a one-to-one correspondence with the natural numbers. However, the converse isn’t always true; not all countable sets are finite. It’s worth noting that some mathematicians use “countable” specifically to mean “countably infinite,” excluding finite sets from this classification.

The concept of a free semilattice over a finite set is directly related to its non-empty subsets, where the join operation is defined as set union.

Necessary and Sufficient Conditions for Finiteness

Within the axiomatic framework of Zermelo–Fraenkel set theory without the axiom of choice (ZF), several conditions are demonstrably equivalent to a set S being finite:

• Standard Definition: S can be put into a one-to-one correspondence with the set of natural numbers {1, 2, …, n} for some natural number n. This is the intuitive definition we started with.
• Kuratowski’s Criterion: S possesses all properties that can be proven by mathematical induction , starting with the empty set and adding one element at a time. This links finiteness to inductive reasoning.
• Stäckel’s Criterion: S can be endowed with a total ordering that is well-ordered in both the forward and backward directions. This means every non-empty subset of S has both a smallest and a largest element within that subset.
• Powerset of Powerset Property: The powerset of the powerset of S, denoted ℘(℘(S)), is Dedekind-finite . This means no one-to-one function from ℘(℘(S)) to itself can be onto, except for the identity function, implying it cannot be put into a one-to-one correspondence with a proper subset of itself. This was a significant result by Whitehead & Russell in Principia Mathematica .
• Powerset of Powerset Surjection Property: Conversely, every surjective function from ℘(℘(S)) onto itself must also be one-to-one.
• Tarski’s Criterion: Every non-empty family of subsets of S has a minimal element with respect to the inclusion relation (⊆). Equivalently, every non-empty family of subsets of S has a maximal element under inclusion. This connects finiteness to the structure of subsets.
• Unique Well-Ordering: S can be well-ordered, and any two such well-orderings on S are order isomorphic . This implies there is only one unique order type for the well-orderings of S.

When the axiom of choice (or even the weaker axiom of countable choice ) is assumed, the following conditions become equivalent to finiteness:

• Dedekind’s Criterion: Every injective function from S into itself is also surjective. This means S is Dedekind-finite .
• Dedekind’s Criterion (Dual): Every surjective function from S onto itself is also injective.
• Maximal Element Property: S is either empty, or every partial ordering on S contains a maximal element . This relates finiteness to the existence of maximal elements in ordered structures.

Other Concepts of Finiteness

In ZF set theory, without the axiom of choice , distinctions arise between various notions of finiteness. These concepts form a hierarchy of decreasing strength; a set meeting a stronger condition will automatically meet all weaker ones. The reverse implications, however, are unprovable in ZF alone and require the axiom of choice for equivalence. These definitions are purely set-theoretic, not relying on pre-defined ordinals:

1. I-finite: Every non-empty set of subsets of S has a maximal element under the subset relation (⊆). This is equivalent to the standard numerical definition of finiteness.
2. Ia-finite: For any partition of S into two sets, at least one of the resulting sets must be I-finite. A set that is not I-finite but satisfies this condition is termed an amorphous set .
3. II-finite: Every non-empty ⊆-monotone set of subsets of S has a ⊆-maximal element.
4. III-finite: The power set ℘(S) is Dedekind finite.
5. IV-finite: S itself is Dedekind finite.
6. V-finite: |S| = 0 or 2⋅|S| > |S|. This is a rather weak condition.
7. VI-finite: |S| = 0 or |S| = 1 or |S|² > |S|. This is related to Tarski’s theorem about choice .
8. VII-finite: S is I-finite or not well-orderable.

The forward implications (from stronger to weaker definitions) are provable within ZF. Counter-examples to the reverse implications, demonstrating the distinctness of these concepts in the absence of choice, often arise from model theory . These definitions and their classifications are largely attributed to Alfred Tarski , with early work appearing in his 1924 paper.

It’s important to note that properties I through IV share a characteristic of “smallness”: any subset of a set with these properties will also inherit the property. This is not true for V through VII, as they might possess countably infinite subsets.

Uniqueness of Cardinality

An intuitive characteristic of finite sets is that a set cannot simultaneously possess two different cardinalities. For example, a set cannot have exactly 4 elements and also exactly 5 elements. While this seems obvious, its formal proof requires careful construction. The following lemma and theorem, adapted from Terence Tao’s Analysis I, illustrate this point.

Lemma: If a set X has cardinality n ≥ 1, and x₀ ∈ X, then the set X - {x₀} (X with x₀ removed) has cardinality n-1.

Proof: Given X with cardinality n, there exists a bijection f from X to {1, 2, …, n}. Since x₀ ∈ X, f(x₀) is some element in {1, 2, …, n}. We need to show there’s a bijection g from X - {x₀} to {1, …, n-1}. Define g(x) = f(x) for all x ≠ x₀, and let g(x₀) be the element in {1, …, n} that f(x) would have mapped to if X - {x₀} mapped to {1, …, n-1}. More precisely, we can construct g by mapping X - {x₀} to {1, …, n-1}. This involves carefully defining the mapping to ensure it’s a bijection.

Theorem: If a set X has cardinality n, then it cannot have any other cardinality m ≠ n.

Proof: The base case of an empty set (cardinality 0) is straightforward. Assume by induction that cardinality is unique for sets up to cardinality n. Now consider a set X with cardinality n+1. If we assume it also has cardinality m, then by the lemma, X - {x₀} has cardinality n and also m-1. By the inductive hypothesis, since X - {x₀} has a unique cardinality n, it must be that m-1 = n. Therefore, m = n+1, proving uniqueness.

This rigorous approach ensures that the concept of cardinality for finite sets is not just intuitive but mathematically sound.

See Also

• FinSet
• Discrete point set
• Ordinal number
• Peano arithmetic

Notes

1. The equivalence of standard numerical finiteness to the Dedekind-finiteness of iterated powersets was a significant result established early on.
2. Tarski’s work provided a formal set-theoretic definition of finiteness that proved equivalent to other characterizations.
3. The axiom of choice plays a crucial role in collapsing these distinct finiteness concepts into a single notion.
4. The lemma and theorem presented here illustrate the fundamental proof of the uniqueness of cardinality for finite sets.