Fact-checked by Grok 2 weeks ago

Finite set

A finite set is a collection of distinct objects, known as elements, where the total number of elements is a non-negative integer, including the possibility of zero elements in the empty set.^[1] Formally, in set theory, a set S is finite if it is empty or if there exists a positive integer n and a bijection—a one-to-one correspondence—between S and the set \{1, 2, \dots, n\}.^[2] The size of a finite set, denoted as its cardinality |S|, is uniquely determined as the number n for which such a bijection exists, providing a precise measure of its elements.^[3] Essential properties of finite sets include the fact that every subset of a finite set is itself finite, with cardinality at most that of the original set; the union of two finite sets is finite, with cardinality given by |A \cup B| = |A| + |B| - |A \cap B|; and the Cartesian product of two finite sets is finite, with cardinality |A \times B| = |A| \times |B|.^[2]^[1] Additionally, a finite set cannot be placed in bijection with any of its proper subsets, distinguishing it from infinite sets, which can exhibit such equivalences.^[2] Finite sets underpin much of discrete mathematics and combinatorics, enabling the study of counting, enumeration, and structural relations among discrete objects.^[1] A notable application is the pigeonhole principle, which asserts that if |A| > |B| for finite sets A and B, then any function f: A \to B cannot be injective, implying at least two elements of A map to the same element in B. This principle, along with operations on finite sets, facilitates proofs in areas like graph theory, probability, and computer science algorithms.^[1]

Definition and Basics

Formal Definition

In set theory, a set S is finite if it is empty or if there exists a positive integer n such that S is in one-to-one correspondence with the set \{1, 2, \dots, n\}, meaning there is a bijection between S and this initial segment of the natural numbers.^[4] This bijection criterion captures the intuitive notion that the elements of S can be enumerated without end, assigning each a unique position from 1 to n. Equivalently, a set S is finite if it is the empty set or can be constructed from the empty set by adjoining a single distinct element a finite number of times, forming a closure under the operation of adding singletons.^[5] Richard Dedekind, in his 1888 work Was sind und was sollen die Zahlen?, introduced a definition of finite sets as those that cannot be placed in bijection with any proper subset of themselves, distinguishing them from infinite sets which can exhibit such equivalences and thereby resolving associated paradoxes.^[6] This approach laid the groundwork for modern set-theoretic definitions of finiteness via bijections. Within Zermelo-Fraenkel set theory (ZF), finiteness is characterized by the absence of the infinite structure posited by the axiom of infinity for the set in question; specifically, a set is finite if it bijects with a finite ordinal, relying on the constructive hierarchy starting from the empty set but without invoking infinite inductive sets. For example, the set \{a, b, c\} is finite, as the bijection f(a) = 1, f(b) = 2, f(c) = 3 establishes its equivalence to \{1, 2, 3\}, yielding a cardinality of 3.

Terminology and Notation

A finite set is a collection of distinct elements with a finite number of members.^[7] The term "finite cardinality" refers to the property of such a set having a specific, non-infinite number of elements, often denoted as n for an n-element set, where n is a non-negative integer.^[8] An n-element set, also called an n-set, is a finite set precisely with n distinct members.^[8] The cardinality of a finite set S, denoted |S|, represents the number of elements it contains.^[9] Finite sets are commonly expressed by explicitly listing their elements within curly braces, such as S = \{x_1, x_2, \dots, x_n\}, where the x_i are distinct and n = |S|.^[7] The empty set, with no elements, is denoted \emptyset or \{\}, and its cardinality is |\emptyset| = 0.^[10] While the term "countable" encompasses both finite sets and certain infinite sets (specifically, those bijectable with the natural numbers), "finite" strictly excludes infinite collections.^[11] In standard mathematical convention, finite sets include the empty set as having cardinality 0, though some specialized contexts may imply non-emptiness.^[10]

Core Properties

Basic Properties

Finite sets exhibit several key closure properties under basic set operations. The union of two finite sets is finite; if A and B are finite with |A| = m and |B| = n, then |A \cup B| \leq m + n.^[12] Similarly, the intersection of any finite number of finite sets is finite, as intersection preserves finiteness by restricting elements to common members.^[12] The Cartesian product of two finite sets is also finite, with |A \times B| = m \times n, reflecting the pairing of each element from A with each from B.^[12] Every subset of a finite set is finite, ensuring that finiteness is hereditary under the subset relation.^[12] Consequently, the power set of a finite set S with |S| = n elements, denoted \mathcal{P}(S), is finite and has exactly $2^n elements, as each subset corresponds to a unique choice of inclusion or exclusion for the n elements.^[12] For example, if S = \{1, 2\}, then \mathcal{P}(S) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}, which has $2^2 = 4 elements.^[12] These properties imply that finite sets admit no infinite descending chains of subsets under inclusion; any chain S_1 \supsetneq S_2 \supsetneq \cdots must terminate after finitely many steps due to the finite number of possible subsets.^[12] Finite sets are thus Dedekind-finite, meaning no bijection exists between a finite set and one of its proper subsets.^[12]

Induction and Recursion on Finite Sets

One distinctive feature of finite sets is that they admit a form of structural induction, allowing properties to be proven by considering the empty set as the base case and assuming the property holds for all proper subsets. Specifically, let P be a property of sets. If P(\emptyset) holds and, for every finite set S, P(T) holds for all proper subsets T \subsetneq S implies P(S), then P holds for all finite sets.^[13] This principle leverages the well-foundedness of the subset relation on finite sets, where there are no infinite descending chains of subsets, ensuring the induction covers all cases without circularity.^[14] An equivalent formulation, often more convenient for recursive definitions, proceeds by specifying the property on the empty set and extending it via single-element adjunction. That is, if P(\emptyset) holds and, for any finite set S and element x \notin S, P(S) implies P(S \cup \{x\}), then P holds for all finite sets.^[15] This additive induction mirrors the construction of finite sets from the empty set by successive unions with singletons, exploiting the fact that every nonempty finite set can be decomposed in this manner uniquely up to the choice of the added element.^[16] Recursive definitions on finite sets exploit this structure to define functions by base cases on the empty set and singletons, then extending via operations like disjoint union. For instance, the sum of elements in a finite set S of numbers can be defined recursively as \sum \emptyset = [0](/page/0) and, for x \notin S, \sum (S \cup \{x\}) = \sum S + x.^[15] This recursion terminates because the process reduces to smaller sets by removing elements, eventually reaching the empty set due to finiteness.^[16] In general, any function on the class of finite sets satisfying appropriate closure conditions under union can be defined this way, providing a foundation for computations on finite structures without invoking natural numbers explicitly.^[15] Finite sets also connect naturally to the initial segment of the ordinal hierarchy below \omega, the first infinite ordinal. Each finite set admits a bijection with a unique finite ordinal n < \omega, where the ordinals are von Neumann ordinals: $0 = \emptyset, $1 = \{0\}, $2 = \{0,1\}, and so on.^[17] This correspondence enables transfinite induction restricted to finite stages, where properties proven by induction up to \omega apply precisely to finite sets, bridging structural induction on sets with the well-ordering of ordinals.^[18] Unlike recursion on infinite sets, which may not terminate or require additional axioms like choice, recursion on finite sets always halts, as the depth of recursive calls is bounded by the set's size.^[13]

Characterizing Finiteness

Necessary and Sufficient Conditions

A set S is finite if and only if there exists a natural number n (including n = 0) and a bijection between S and the set \{0, 1, \dots, n-1\}.^[19] This bijection criterion provides a precise characterization of finiteness by equinumerosity with an initial segment of the natural numbers. Another fundamental condition, due to Dedekind, states that a set S is finite if and only if there is no injection from S to a proper subset of itself.^[20] Equivalently, every injection from S to S is a bijection, meaning S is not equinumerous to any of its proper subsets. This condition highlights the absence of "infinite regress" in self-mappings that preserve distinctness. To see why this holds, first suppose S is finite via the bijection criterion with some n. Any injection f: S \to S must then map a set of cardinality n injectively into itself, which implies surjectivity by the pigeonhole principle for finite sets, hence a bijection. Conversely, if S admits an injection to a proper subset, it is Dedekind-infinite and contains a countably infinite subset, obtained by iterating the injection to generate an ω-chain.^[20] Additional equivalent conditions include: a set S is finite if and only if every non-empty family of subsets of S has a minimal element under inclusion (Tarski's criterion); or equivalently, if S has no countably infinite subset.^[20] These capture finiteness through well-foundedness in the subset lattice or the absence of infinite countable chains. For example, the set \mathbb{N} of natural numbers is infinite because the shift map n \mapsto n+1 provides a bijection from \mathbb{N} to its proper subset \{1, 2, 3, \dots\}.^[20] In Zermelo-Fraenkel set theory (ZF) without the axiom of choice, the bijection criterion, Dedekind's condition, Tarski's criterion, and the absence of a countably infinite subset are all equivalent. In ZF with choice (ZFC), these simplify further, as every Dedekind-finite set is finite in the standard sense, and the bijection criterion suffices uniquely.^[20]

Alternative Notions of Finiteness

In set theory without the axiom of choice (ZF), a set is Dedekind-finite if it is not equinumerous to any of its proper subsets, providing an alternative characterization of finiteness that diverges from the classical bijection-based definition when choice is absent.^[21] Unlike classical finite sets, Dedekind-finite sets in ZF can be infinite; for instance, amorphous sets are infinite Dedekind-finite sets that cannot be partitioned into two infinite subsets, highlighting pathological structures possible without choice.^[22] These sets arise in models of ZF where the axiom of choice fails, such as those constructed via Fraenkel-Mostowski methods, and they underscore foundational tensions between cardinality and injectivity.^[22] Another alternative arises in topological and domain-theoretic contexts, where a set is considered finite if every ultrafilter on its power set is principal, meaning it is generated by a singleton.^[23] This notion, employed in pointless topology and Scott domains, equates finiteness with compactness in the associated locale or lattice structure, ensuring that no non-trivial infinite "limits" exist. It aligns with classical finiteness under choice but allows for broader applications in constructive settings where ultrafilters model convergence without assuming discrete points.^[23] In computability theory, finiteness connects to primitive recursive functions, which are total computable functions built from basic operations via composition, projection, and primitive recursion, always terminating after finitely many steps.^[24] This ties finiteness to bounded computation: on finite sets, primitive recursive functions suffice for enumeration and manipulation, whereas infinite sets permit definitions of partial recursive functions that may non-terminate on some inputs, distinguishing effectively finite data from potentially unending processes. Historically, Hermann Weyl's predicative mathematics offers a variant where finite sets are those constructed intuitionistically through finite iterations of basic operations, avoiding impredicative definitions that quantify over the totality of sets.^[25] In Weyl's 1918 framework, as detailed in Das Kontinuum, such sets form the foundation for analysis, excluding impredicative comprehensions to prevent circularity, thus restricting "finiteness" to explicitly generative processes.^[26] In intuitionistic logics, finiteness often means decidable finiteness: a set is finite if there exists a decidable enumeration or if membership is decidable and the set is provably non-infinite via constructive proofs.^[27] This excludes sets that are classically finite but lack a uniform constructive witness for their boundedness, such as those requiring the law of excluded middle for cardinality proofs.^[28] Classical finiteness, assuming the axiom of choice, implies all these alternative notions, but the converses fail in ZF alone, as infinite Dedekind-finite or amorphous sets demonstrate non-equivalence without choice.^[21]

Cardinality of Finite Sets

Definition and Uniqueness

In set theory, the cardinality of a finite set S, denoted |S|, is defined as the unique natural number n such that there exists a bijection between S and the set \{1, 2, \dots, n\}.^[12]^[29] This definition aligns with the intuitive notion of counting the elements in S, where the bijection establishes a one-to-one correspondence with a standard finite ordinal. The empty set \emptyset has cardinality |\emptyset| = 0, as it is in bijection with the empty natural number $0 = \emptyset, providing the base case for finite cardinalities.^[12] A key uniqueness theorem states that for any two finite sets S and T, if there exists a bijection between them, then |S| = |T|.^[29] This result extends the Schröder-Bernstein theorem to the finite case, ensuring that equinumerous finite sets share the same cardinality without relying on injections alone.^[12] The proof of uniqueness proceeds by induction on the natural number n. For the base case n = 0, the empty set is unique up to bijection. Assume the result holds for all sets of cardinality less than n; for a set S of cardinality n, any bijection to another finite set T implies T has exactly n elements, as removing corresponding elements yields sets of cardinality n-1, and by the inductive hypothesis, their cardinalities match. Distinct natural numbers cannot be bijective, since one is a proper subset of the other, preventing a bijection.^[29]^[12] For example, all singleton sets have cardinality 1, as each is bijective with \{1\}, and no finite set of cardinality 2 is equinumerous with a singleton, illustrating that sets of different finite sizes are never bijective.^[12] This uniqueness of finite cardinalities holds in ZF set theory without the axiom of choice, as the inductive construction and bijection properties rely solely on the well-ordering of natural numbers and extensionality.^[29]

Finite Cardinals and Ordering

Finite cardinals support well-defined arithmetic operations that extend the familiar arithmetic of natural numbers. The sum of two finite cardinals m and n is defined as m + n = |A \cup B|, where A and B are disjoint sets with |A| = m and |B| = n.^[12] Similarly, the product is m \times n = |A \times B|.^[12] These operations are independent of the choice of representative sets and align precisely with addition and multiplication on the corresponding natural numbers.^[30] Addition and multiplication of finite cardinals are both commutative and associative, and multiplication distributes over addition, mirroring the properties of natural number arithmetic.^[12] For example, the sum $3 + 2 = 5 can be verified by taking disjoint sets A = \{a, b, c\} and B = \{d, e\}, whose union has five elements.^[30] The finite cardinals form a total order under the relation m \leq n if and only if there exists an injection from a set of cardinality m to a set of cardinality n.^[12] This ordering is isomorphic to the order of the natural numbers $0 < 1 < 2 < \cdots, with no gaps between consecutive elements.^[30] For instance, |\{a\}| < |\{a, b, c\}| because an injection exists from the singleton to the three-element set, but no bijection (or equivalently, no surjection from the singleton).^[12] Cantor's theorem holds for finite sets: if S is a nonempty finite set, then |S| < | \mathcal{P}(S) |, since the cardinality of the power set is $2^{|S|}, and $2^n > n for any finite n \geq 1.^[31] Finite ordinals coincide with finite cardinals up to the first infinite ordinal \omega, as each finite ordinal serves as the cardinal of sets with that many elements.^[12]

References

[1]
Sets:Finite - Department of Mathematics at UTSA
Nov 7, 2021 · A finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting.
[2]
Finite Sets and Infinite Sets - Foundations of Mathematics
Nov 21, 2018 · Definition. We call the set A finite if either A is empty, or there is some k\in\mathbb{N} and a bijection ; Theorem. If A is finite and there is ...
[3]
[PDF] Section 1.3 Finite and Infinite Sets
From the definitions, it is not entirely clear that a finite set might not have n elements for more than one value of n.
[4]
Basic set theory - Stanford Encyclopedia of Philosophy
A set $A$ is finite if there is a one-to-one correspondence between some natural number $n$ and the elements of $A$, i.e., a bijection $F:n\to A$, in ...
[5]
[PDF] MFCS Finite Sets - Carnegie Mellon University
The key part of the definition is the set of natural numbers N. For our definition of finiteness to make any sense, we have to have a definition of. N first.
[6]
Dedekind's Contributions to the Foundations of Mathematics
Apr 22, 2008 · (A set can then be defined to be finite if it is not infinite in this sense.) Moving a step closer to arithmetic, this leads to the notion of a ...
[7]
1.1: Set Notation and Relations - Mathematics LibreTexts
Aug 16, 2021 · A set is a finite set if it has a finite number of elements. Any set that is not finite is an infinite set.
[8]
Finite Set -- from Wolfram MathWorld
A set X whose elements can be numbered through from 1 to n, for some positive integer n. The number n is called the cardinal number of the set.
[9]
Cardinality | Finite Sets | Infinite Sets | Inclusion Exclusion Principle
Let A be a countable set and B⊂A. If A is a finite set, then |B|≤|A|<∞, thus B is countable. If A is countably infinite, then we can list the elements in A, ...
[10]
None
### Summary: Empty Set as Finite with Cardinality 0
[11]
Cardinality | Brilliant Math & Science Wiki
The cardinality of a set is a measure of a set's size, meaning the number of elements in the set. For instance, the set A={1,2,4} has a cardinality of 3 3 3.<|separator|>
[12]
[PDF] Naive set theory. - Whitman People
Halmos —Naive Set Theory. John L. Kelley—Introduction to Modern Algebra. R ... infinite sets of the counting process appropriate to finite sets, the theory.
[13]
[PDF] arXiv:math/9405204v1 [math.LO] 20 May 1994
We establish a course-of-values induction principle for K-finite sets in ... proper subsets of A. It is related to ordinary induction for finite sets much ...
[14]
[PDF] Finiteness in a Minimalist Foundation - Unipd
proper subsets. An alternative way is to consider the sets of the form N(k) as prototypes of the finite sets ... Proposition 7 (induction principle for ...
[15]
[PDF] Some Notes on Finite Sets - arXiv
These notes aim to give a gentle account of one approach to the theory of finite sets without making use of the natural numbers or any other infinite set. They.
[16]
[PDF] Finite Sets and Counting - arXiv
Jun 19, 2010 · the help of the induction principle for finite sets (Theorem 2.1). ... proper subsets B1, B2 of A with x1 = #(B1) and x2 = #(B2) and by ...
[17]
Ordinal Number -- from Wolfram MathWorld
The ordinals for finite sets are denoted 0, 1, 2, 3, ..., i.e., the integers one less than the corresponding nonnegative integers. ... . omega^2 is larger than ...
[18]
Set Theory, Part 2: Constructing the Ordinals - Power Overwhelming
Nov 18, 2014 · We can thus rule out ω as a finite ordinal because, although it has ∅ as its only non-successor element, it has no maximum element. We can also ...
[19]
[PDF] The Cardinality of a Finite Set
The cardinality of a nonempty finite set is the unique natural number n for which there exists a bijection from the set to Nn, denoted by card(A).
[20]
[PDF] Set Theory
Moreover, the theory of inner models has emerged as a major part of the large cardinal theory. The book has three parts. The first part contains material that ...
[21]
[2510.13508] Amorphous sets and dual Dedekind finiteness - arXiv
Oct 15, 2025 · A set A is dually Dedekind finite if every surjection from A onto A is injective; otherwise, A is dually Dedekind infinite. An amorphous set is ...
[22]
General cardinal, without the axiom of choice | cantors-attic
The Dedekind finite sets are those not equinumerous with any proper subset. ... ZF that there are infinite Dedekind finite sets. An amorphous set is an ...
[23]
[PDF] The Logic of Cardinality Comparison Without the Axiom of Choice
Jun 8, 2023 · One particular type of Dedekind-finite set is an amorphous set. An infinite set A is said to be amorphous if there do not exist infinite ...
[24]
[PDF] ultrafilter in set theory - UChicago Math
Aug 28, 2018 · First, if F is a filter containing a finite set, then F is principal; this follows from the fact that filters are closed under finite ...
[25]
(PDF) Choiceless, Pointless, but not Useless: Dualities for Preframes
Aug 10, 2025 · Choiceless, Pointless, but not Useless: Dualities for Preframes. December 2007; Applied Categorical Structures 15(5-6):541-572. DOI:10.1007/ ...
[26]
Recursive Functions - Stanford Encyclopedia of Philosophy
Apr 23, 2020 · A primary problem in the theory of recursively enumerable sets is the problem of determining the degrees of unsolvability of the unsolvable ...
[27]
[PDF] Computability and Recursion
Gödel realized, however, that the primitive recursive functions did not include all effectively calculable functions,5 and in 1934 he proposed a wider class of ...
[28]
9 Hermann Weyl: Predicativity and an Intuitionistic Excursion
Abstract. This chapter provides a survey of Weyl's shifting foundational views in mathematics from his early set-theoretical viewpoint around 1910 to his ...
[29]
[PDF] Weyl's Predicative Classical Mathematics as a Logic-Enriched Type ...
Feb 12, 2007 · We present a logic-enriched type theory that corresponds to Weyl's foundational system. A large part of the mathematics in Weyl's book. — ...
[30]
Constructive stone: cardinality of sets - Mathematics and Computation
Sep 8, 2009 · This establishes `p or not p`. QED. (Side remark: decidable finite sets do have a well-defined number of elements, which is a natural number, ...
[31]
Intuitionistic sets and numbers: small set theory and Heyting arithmetic
Jun 18, 2024 · We present an intuitionistic theory of the hereditarily finite sets, and show that it is definitionally equivalent to Heyting Arithmetic HA, in a sense to be ...<|separator|>
[32]
None
### Summary of Sections on Cardinality of Finite Sets, Uniqueness, and Axiom of Choice
[33]
[PDF] 3. Cardinal Numbers - MIMUW
Every natural number is a cardinal (a finite cardinal); and if S is a finite set, then |S| = n for some n. The ordinal ω is the least infinite cardinal. Note ...
[34]
4.10 Cantor's Theorem
1 Verify Cantor's Theorem for finite sets by showing that if A has n elements, then P(A) has 2n elements. The representation of a real number as a decimal ...