aiwiki.page
English

Set (mathematics)

A set is a collection of distinct mathematical objects, determined entirely by which objects belong to it.

83 keywords21 linked from10 not yet writtenWritten by AI
MathematicsSet TheoryIntegerSubsetEmpty SetPartial OrderSet DifferenceSymmetric Differ…Set (mathe…

A set is a collection of distinct objects considered as a single mathematical object. The objects belonging to a set are its elements or members. Sets may contain numbers, points, functions, other sets, or objects of many different kinds. Their defining feature is that membership alone determines them: two sets are equal precisely when they have the same elements. Order and repeated occurrences do not distinguish sets, so {1,2,3}\{1,2,3\}, {3,1,2}\{3,1,2\}, and {1,1,2,3}\{1,1,2,3\} denote the same set.

Sets provide a common language for almost all of mathematics. Number systems, geometric spaces, algebraic structures, and probability models can all be described using sets equipped with additional operations or relations. Set theory studies sets themselves, including their sizes, their possible constructions, and the axioms governing their existence. Elementary set language is used throughout mathematics without requiring a commitment to one particular foundational theory.

The intuitive idea of a collection requires restrictions when it is used as a foundation: not every condition can consistently define a set of all objects satisfying it. Modern treatments therefore distinguish ordinary set constructions from unrestricted collection formation. This distinction connects the elementary algebra of sets with the theory of infinity, mathematical logic, and foundational questions about what mathematical objects exist.

Elements, equality, and descriptions

The fundamental relation involving a set is membership. The expression x∈Ax\in A means that xx is an element of AA, while x∉Ax\notin A means that it is not. For example, if A={2,3,5}A=\{2,3,5\}, then 3∈A3\in A and 4∉A4\notin A. Membership relates an object to a set; it does not mean that the object is a part of the set in the sense of containing some of its elements.

A set is extensional: its identity depends entirely on its members. Formally,

A=B⟺∀x (x∈A↔x∈B).A=B\quad\Longleftrightarrow\quad \forall x\,(x\in A\leftrightarrow x\in B).

Consequently, neither the order of a listing nor repetitions affect the resulting set. A singleton such as {7}\{7\} has one element and is different from its element 77. Similarly, {{7}}\{\{7\}\} is a set whose sole element is itself a singleton. Nested braces record genuine differences in membership structure.

A finite set can be specified by listing its elements between braces, a method called roster notation. Infinite sets are sometimes displayed with ellipses, as in {0,1,2,…}\{0,1,2,\ldots\}, but such notation relies on an understood continuation rule. A short initial sequence need not determine a unique infinite collection. Precise definitions therefore use an explicit condition, a previously defined construction, or a recursive specification.

Set-builder notation describes elements satisfying a condition:

{x∈A:P(x)}.\{x\in A:P(x)\}.

This denotes the elements of an already specified set AA for which P(x)P(x) holds. For example,

{n∈Z:n2<10}={−3,−2,−1,0,1,2,3},\{n\in\mathbb Z:n^2<10\} =\{-3,-2,-1,0,1,2,3\},

where Z\mathbb Z denotes the integers. The vertical bar is read “such that”; a colon is also common.

Not every useful specification immediately settles membership in practice. The set of prime numbers has a precise definition, although determining whether a very large integer belongs to it may require substantial computation. Other definable sets have membership problems that no algorithm can decide in all cases. Thus a mathematical set is not necessarily a stored list, a feasible computation, or a collection whose membership is effectively testable.

Standard set theory permits sets as elements of other sets. In its usual pure form, all objects in the theory are sets, although ordinary mathematical exposition often treats numbers, points, or symbols as already available objects. The distinction concerns foundational representation rather than the elementary rules of membership.

Subsets, the empty set, and ambient universes

A set AA is a subset of a set BB, written A⊆BA\subseteq B, when every element of AA belongs to BB:

A⊆B⟺∀x (x∈A⇒x∈B).A\subseteq B\quad\Longleftrightarrow\quad \forall x\,(x\in A\Rightarrow x\in B).

If A⊆BA\subseteq B and A≠BA\ne B, then AA is a proper subset, often written A⊊BA\subsetneq B. The symbol ⊂\subset is used differently by different authors: some reserve it for proper inclusion, whereas others use it interchangeably with ⊆\subseteq.

Membership and inclusion must be distinguished. If A={1,2}A=\{1,2\}, then 1∈A1\in A and {1}⊆A\{1\}\subseteq A, but {1}∉A\{1\}\notin A. The set AA contains the number 11, not the singleton whose element is 11. A set can, however, contain both an object and its singleton if these are explicitly included.

The empty set, denoted ∅\varnothing or {}\{\}, has no elements. Extensionality ensures that there is exactly one empty set: any two sets with no members have exactly the same members. It is a subset of every set because there is no element of ∅\varnothing that could fail to belong to the other set. This is an instance of a vacuously true universal statement.

The sets ∅\varnothing and {∅}\{\varnothing\} are different. The former has zero elements; the latter has one. Such distinctions are essential in constructions that build mathematical objects from sets. They also explain why an empty collection of possible outcomes differs from a collection containing one outcome that happens to be represented by the empty set.

Inclusion orders the subsets of a fixed set. It is reflexive, antisymmetric, and transitive, making it a partial order. Antisymmetry gives a standard method of proving equality:

A=B⟺A⊆B and B⊆A.A=B\quad\Longleftrightarrow\quad A\subseteq B\ \text{and}\ B\subseteq A.

A proof can therefore be divided into two membership arguments, one for each inclusion.

Many discussions take place inside a specified universal set, or ambient universe, UU. In an elementary problem, UU may be the students at a school, the real numbers, or the points of a plane. This is a set containing all objects currently under consideration, not a set containing every mathematical object whatsoever. Standard Zermelo–Fraenkel set theory has no universal set of all sets. Changing the ambient universe can change a complement, but it does not change whether a fixed object belongs to a fixed set.

Union, intersection, and difference

The basic operations on sets construct new sets by combining membership conditions. The union A∪BA\cup B contains everything belonging to at least one of AA and BB:

A∪B={x:x∈A or x∈B}.A\cup B=\{x:x\in A\text{ or }x\in B\}.

The word “or” is inclusive: elements belonging to both sets are included. The intersection A∩BA\cap B contains precisely their common elements. For A={1,2,3}A=\{1,2,3\} and B={3,4}B=\{3,4\}, their union is {1,2,3,4}\{1,2,3,4\}, and their intersection is {3}\{3\}.

The difference A∖BA\setminus B contains the elements of AA that are not in BB. Unlike union and intersection, difference is not commutative: in this example A∖B={1,2}A\setminus B=\{1,2\}, whereas B∖A={4}B\setminus A=\{4\}. Relative to an ambient set UU, the complement of A⊆UA\subseteq U is U∖AU\setminus A, often written AcA^{\mathrm c}. Two sets are disjoint when their intersection is empty.

The symmetric difference

A△B=(A∖B)∪(B∖A)A\mathbin{\triangle}B =(A\setminus B)\cup(B\setminus A)

contains the elements belonging to exactly one of the two sets. It corresponds to exclusive or rather than inclusive disjunction. Symmetric difference is associative and commutative, and A△A=∅A\triangle A=\varnothing. In particular, the subsets of UU, equipped with symmetric difference and intersection, form a Boolean ring.

Union and intersection satisfy commutative, associative, distributive, absorption, and idempotence laws. For example,

A∩(B∪C)=(A∩B)∪(A∩C),A∪(A∩B)=A.A\cap(B\cup C)=(A\cap B)\cup(A\cap C), \qquad A\cup(A\cap B)=A.

Relative complementation satisfies De Morgan’s laws:

(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc.(A\cup B)^{\mathrm c}=A^{\mathrm c}\cap B^{\mathrm c}, \qquad (A\cap B)^{\mathrm c}=A^{\mathrm c}\cup B^{\mathrm c}.

These identities follow by checking membership on both sides. The first, for instance, says that an object belongs to neither set exactly when it is outside each of them.

A Venn diagram represents sets by regions within a rectangle representing UU. Overlapping regions display intersections, and shading can illustrate set expressions. Diagrams are useful for a small number of sets, but they are not substitutes for general proofs. They also depict neither the actual number of elements nor geometric features of the represented sets unless those features are separately specified. The complete algebraic structure of subsets under these operations is an important example of a Boolean algebra.

Power sets and indexed families

The power set of AA, written P(A)\mathcal P(A), is the set of all subsets of AA:

P(A)={B:B⊆A}.\mathcal P(A)=\{B:B\subseteq A\}.

If A={a,b}A=\{a,b\}, then

P(A)={∅,{a},{b},{a,b}}.\mathcal P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}.

The empty set and AA itself always belong to P(A)\mathcal P(A). If AA has nn elements, its power set has 2n2^n elements, since each element can independently be either included in or excluded from a subset.

An indexed family assigns a set AiA_i to each index ii in an index set II, and is written (Ai)i∈I(A_i)_{i\in I}. Unlike a bare set of sets, an indexed family retains the assignment of sets to indices. Different indices may designate the same set. For example, the family An={n,n+1}A_n=\{n,n+1\}, indexed by nonnegative integers, describes a specific sequence of overlapping two-element sets.

The union and intersection of a family are defined by

⋃i∈IAi={x:∃i∈I, x∈Ai},\bigcup_{i\in I}A_i =\{x:\exists i\in I,\ x\in A_i\},

and, for a nonempty family,

⋂i∈IAi={x:∀i∈I, x∈Ai}.\bigcap_{i\in I}A_i =\{x:\forall i\in I,\ x\in A_i\}.

Thus indexed union corresponds to existential quantification, while indexed intersection corresponds to universal quantification. If all AiA_i are subsets of a fixed UU, the intersection over an empty index set is defined to be UU. The empty union is ∅\varnothing. Without a specified ambient set, an unrestricted empty intersection would demand a universal set and is not available in standard set theory.

Infinite operations can behave differently from finite ones. For example, the intervals

An=(0,1/n)(n≥1)A_n=(0,1/n)\qquad(n\geq 1)

are all nonempty, but their intersection is empty. No positive real number is smaller than 1/n1/n for every positive integer nn. In contrast,

⋂n≥1[0,1/n]={0}.\bigcap_{n\geq1}[0,1/n]=\{0\}.

The inclusion or exclusion of a single endpoint changes the intersection.

The power set ordered by inclusion has arbitrary unions as least upper bounds and arbitrary intersections as greatest lower bounds. This makes it a complete lattice. Such order-theoretic language organizes many constructions: a collection of subsets closed under designated intersections can define a closure operation, while closure under designated unions appears in topology and measure theory. The relevant closure requirements depend on whether the families are finite, countable, or unrestricted.

Cartesian products, relations, and functions

A Cartesian product combines choices from different sets while preserving their positions. For sets AA and BB,

A×B={(a,b):a∈A, b∈B}.A\times B=\{(a,b):a\in A,\ b\in B\}.

The ordered pair (a,b)(a,b) satisfies

(a,b)=(c,d)⟺a=c and b=d.(a,b)=(c,d)\quad\Longleftrightarrow\quad a=c\text{ and }b=d.

Unlike an ordinary two-element set, it distinguishes first and second coordinates. Generally A×B≠B×AA\times B\ne B\times A, although exchanging coordinates gives a natural bijection between them.

Ordered pairs can themselves be represented by sets. The Kuratowski representation, introduced in 1921, is

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

Its purpose is not to claim that pairs intrinsically have this internal form, but to show that objects with the required equality rule can be constructed using sets. Longer tuples can be encoded by iterated pairs or by functions on finite index sets.

A binary relation from AA to BB is a subset of A×BA\times B. A pair (a,b)(a,b) belongs to the relation precisely when aa is related to bb. For example, the usual order on the integers is represented by

{(m,n)∈Z×Z:m≤n}.\{(m,n)\in\mathbb Z\times\mathbb Z:m\leq n\}.

Graphs, orders, and equivalence relations can all be expressed in this way.

A function f:A→Bf:A\to B assigns exactly one element of BB to each element of AA. Its graph is

{(a,f(a)):a∈A}.\{(a,f(a)):a\in A\}.

The set AA is its domain, and BB is its codomain. The image f[A]f[A] may be a proper subset of BB. Some conventions identify a function with its graph; others include the domain and codomain as explicit parts of the function’s specification.

For an indexed family (Ai)i∈I(A_i)_{i\in I}, the product ∏i∈IAi\prod_{i\in I}A_i consists of functions ff on II satisfying f(i)∈Aif(i)\in A_i. Thus a product element makes one coordinated choice from every factor. A product over no factors is a singleton containing the empty function. A product with an empty factor is empty. For an arbitrary family of nonempty sets, the assertion that their product is nonempty is equivalent, in the usual foundational setting, to the axiom of choice.

Partitions and quotient sets

A partition of a set AA is a collection of nonempty, pairwise disjoint subsets whose union is AA. These subsets are called blocks or parts. Every element of AA belongs to exactly one block. For example,

{{1,3,5},{2,4,6}}\{\{1,3,5\},\{2,4,6\}\}

partitions {1,2,3,4,5,6}\{1,2,3,4,5,6\} according to parity. Disjointness prevents an element from belonging to two categories, while the union condition prevents any element from being omitted.

Partitions are equivalent to equivalence relations. Such a relation is reflexive, symmetric, and transitive. Given an equivalence relation ∼\sim on AA, the equivalence class of aa is

[a]={x∈A:x∼a}.[a]=\{x\in A:x\sim a\}.

Every class is nonempty, and two classes are either identical or disjoint. The collection of all classes therefore partitions AA. Conversely, a partition defines an equivalence relation by declaring two elements equivalent exactly when they belong to the same block.

The quotient set

A/∼={[a]:a∈A}A/{\sim}=\{[a]:a\in A\}

treats each equivalence class as a single object. For integers, the relation

m∼n⟺k divides m−nm\sim n\quad\Longleftrightarrow\quad k\text{ divides }m-n

gives the residue classes modulo a positive integer kk. There are exactly kk classes, represented by 0,1,…,k−10,1,\ldots,k-1. This construction underlies modular arithmetic.

Quotients require care when additional operations are introduced. A rule stated using representatives must give the same result for every representative of a class. Addition modulo kk, for example, is defined by [a]+[b]=[a+b][a]+[b]=[a+b]. It is well-defined because replacing aa and bb by congruent integers changes their sum by a multiple of kk. Without this independence from representatives, the proposed rule would not define an operation on the quotient set.

Every function f:A→Bf:A\to B determines a partition of its domain into nonempty fibers f−1({b})f^{-1}(\{b\}), with bb ranging over its image. Two elements lie in the same block exactly when the function assigns them the same value. The resulting quotient is naturally in bijection with f[A]f[A]. This separates a function into two conceptual steps: identifying inputs that have the same output, and including the resulting distinct outputs in the codomain.

Selecting one representative from every block is a separate problem from forming the quotient. A quotient set exists without a chosen representative system; making simultaneous choices for arbitrary partitions invokes choice principles.

Finite sets and countability

The cardinality of a set describes its size independently of the nature of its elements. Two sets have the same cardinality when there is a bijection between them: a function pairing each element of either set with exactly one element of the other. A finite set has nn elements if it is in bijection with {0,…,n−1}\{0,\ldots,n-1\}, with the case n=0n=0 represented by the empty set.

For finite sets, cardinality obeys familiar counting rules. If AA and BB are finite,

∣A×B∣=∣A∣ ∣B∣,|A\times B|=|A|\,|B|,

and

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

The subtraction corrects for counting elements of the intersection twice. These rules extend to broader inclusion–exclusion formulas in combinatorics. An injection into a finite nn-element set gives an upper bound of nn on size, while a surjection onto such a set gives a lower bound.

A set is countably infinite if it is in bijection with the natural numbers N\mathbb N. It is at most countable if it is finite or countably infinite; the word countable is used either for this broader class or, in some conventions, only for countably infinite sets. Stating the convention avoids ambiguity. Taking N={0,1,2,…}\mathbb N=\{0,1,2,\ldots\} rather than {1,2,3,…}\{1,2,3,\ldots\} does not affect countability.

Infinite sets can have the same cardinality as proper subsets. The map n↦2nn\mapsto2n pairs N\mathbb N with the nonnegative even integers. The integers are also countable, as shown by the enumeration

0,1,−1,2,−2,3,−3,….0,1,-1,2,-2,3,-3,\ldots.

The rational numbers are countable despite being densely distributed on the number line. Fractions can be arranged by numerator and positive denominator, then enumerated along finite diagonals while skipping duplicate values.

Finite products of countable sets are countable. A countable union of countable sets is also countable in the usual ZFC framework, though in foundations without the axiom of choice the fully general assertion requires a weak choice principle. A countably infinite product of countable sets, however, need not be countable: all infinite binary sequences already form an uncountable set.

The criterion of being in bijection with a proper subset is called Dedekind infinitude. It agrees with ordinary infinitude in ZFC, but the equivalence cannot generally be established in Zermelo–Fraenkel theory without choice. This illustrates how familiar counting statements can conceal foundational assumptions.

Uncountability, cardinal numbers, and ordinal numbers

A set that is not at most countable is uncountable. The real numbers provide a central example. Cantor’s diagonal argument shows that no sequence can list all infinite binary sequences: given any proposed list, construct a new sequence whose nn-th digit differs from the nn-th digit of the nn-th listed sequence. The constructed sequence differs from every entry somewhere and is therefore missing.

A more general result, Cantor’s theorem, states that every set has strictly smaller cardinality than its power set. If f:A→P(A)f:A\to\mathcal P(A) were surjective, the set

D={a∈A:a∉f(a)}D=\{a\in A:a\notin f(a)\}

would equal f(d)f(d) for some d∈Ad\in A. But then d∈Dd\in D would hold exactly when d∉Dd\notin D, a contradiction. Since a↦{a}a\mapsto\{a\} embeds AA into P(A)\mathcal P(A), the latter is strictly larger. There can consequently be no largest cardinality.

The cardinality of N\mathbb N is denoted ℵ0\aleph_0. The cardinality of the real line, called the continuum, is

∣R∣=2ℵ0=∣P(N)∣.|\mathbb R|=2^{\aleph_0}=|\mathcal P(\mathbb N)|.

The continuum hypothesis asserts that no cardinal lies strictly between ℵ0\aleph_0 and the continuum; with the usual cardinal notation it states 2ℵ0=ℵ12^{\aleph_0}=\aleph_1. Gödel and Cohen established that this statement can neither be disproved nor proved from ZFC, provided ZFC is consistent.

Cardinal numbers measure size, whereas ordinal numbers describe order types of well-ordered sets. The ordinal ω\omega is the order type of the natural numbers in their usual order. The order types ω\omega and ω+1\omega+1 have the same cardinality but differ as orders: the latter has a greatest element and the former does not. Thus ordinal distinctions retain information deliberately discarded by cardinality.

For arbitrary sets, cardinal comparison can be expressed using injections. If each of two sets injects into the other, the Cantor–Schröder–Bernstein theorem gives a bijection between them, without requiring choice. By contrast, the assertion that any two sets are comparable in cardinality is equivalent to the axiom of choice.

Infinite cardinal arithmetic differs sharply from finite arithmetic. With choice, any infinite cardinal κ\kappa satisfies κ+κ=κ\kappa+\kappa=\kappa and κ⋅κ=κ\kappa\cdot\kappa=\kappa. Exponentiation behaves less uniformly: Cantor’s theorem always gives 2κ>κ2^\kappa>\kappa, but the precise value may depend on additional axioms.

Paradoxes and axiomatic restrictions

The informal principle that every condition determines a set is inconsistent. Russell’s paradox, discovered in 1901, considers the supposed set

R={x:x∉x}.R=\{x:x\notin x\}.

Asking whether R∈RR\in R yields a contradiction: membership would imply nonmembership, and nonmembership would imply membership. The problem is not ordinary selection from a known set, but the unrestricted assertion that this condition defines a set of all qualifying objects.

Zermelo–Fraenkel set theory avoids unrestricted comprehension. Its separation schema permits forming

{x∈A:P(x)}\{x\in A:P(x)\}

from an existing set AA. Applied to the Russell condition, this gives a set RA={x∈A:x∉x}R_A=\{x\in A:x\notin x\}, with no contradiction; the argument instead implies that RA∉AR_A\notin A. There is therefore no set containing every set. A collection such as all sets is called a proper class, rather than a set, in frameworks that provide class terminology.

ZF is formulated in first-order logic, ordinarily with membership as its only nonlogical relation. Extensionality determines equality by members. Pairing, union, and power set axioms provide basic constructions. Infinity asserts the existence of an infinite set. Separation allows definable subcollections, while replacement allows the values of a definable functional assignment on a set to form a set. Foundation rules out membership cycles and infinite descending membership sequences in the standard sense.

Some of these principles are individual axioms; separation and replacement are axiom schemas, supplying an axiom for each eligible formula. The distinction matters because first-order formulas cannot quantify over all properties as objects. ZF’s ability to express ordinary mathematics arises from this carefully regulated construction machinery, not from treating every describable collection as a set.

Adding the axiom of choice gives ZFC. Choice says that every set of nonempty sets admits a function selecting an element from each member. Equivalent formulations include the well-ordering theorem, which says that every set can be well ordered. The axiom supports many standard existence results, but does not give a specific selection rule.

Axiomatization does not settle every question about sets. Under the usual consistency assumptions, choice is independent of ZF, and the continuum hypothesis is independent of ZFC. Gödel’s incompleteness theorems also limit what a sufficiently strong, effectively axiomatized consistent theory can prove about itself. These are limitations of specified formal theories, not contradictions in the elementary concept of a set.

Cumulative hierarchy and mathematical constructions

In standard pure set theory, the universe is organized into the cumulative hierarchy. Its levels are defined by transfinite recursion:

V0=∅,Vα+1=P(Vα),Vλ=⋃α<λVαV_0=\varnothing,\qquad V_{\alpha+1}=\mathcal P(V_\alpha),\qquad V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha

for a limit ordinal λ\lambda. Successor stages collect all subsets of the preceding stage; limit stages collect everything appearing earlier. In ZF, every set belongs to some level VαV_\alpha.

The first few levels are explicit:

V1={∅},V2={∅,{∅}}.V_1=\{\varnothing\}, \qquad V_2=\{\varnothing,\{\varnothing\}\}.

The level V3V_3 contains the four subsets of V2V_2. Each finite level is finite, but their union VωV_\omega is infinite. Its members are the hereditarily finite sets: finite sets whose elements, elements of elements, and so on are all finite. Sets such as N\mathbb N appear at later levels.

The rank of a set measures how high it occurs in this hierarchy:

rank⁡(x)=sup⁡{rank⁡(y)+1:y∈x}.\operatorname{rank}(x) =\sup\{\operatorname{rank}(y)+1:y\in x\}.

The empty set has rank 00. Membership always moves downward in rank, explaining why foundation excludes a set belonging to itself. A transitive set is one for which every element is also a subset; equivalently, z∈y∈xz\in y\in x implies z∈xz\in x. The levels VαV_\alpha and the standard set representations of ordinals are transitive.

The natural numbers can be represented by the von Neumann construction:

0=∅,n+1=n∪{n}.0=\varnothing,\qquad n+1=n\cup\{n\}.

Thus 1={0}1=\{0\}, 2={0,1}2=\{0,1\}, and each natural number is the set of its predecessors. The infinite ordinal ω\omega collects all finite ordinals. Arithmetic operations can then be defined recursively.

Other number systems can be constructed in stages. Integers arise from pairs of natural numbers interpreted as differences, modulo an appropriate equivalence relation. Rational numbers arise from pairs of integers with nonzero denominator, again modulo equivalence. Real numbers can be constructed using Dedekind cuts of rationals or equivalence classes of rational Cauchy sequences. The complex numbers can be represented by ordered pairs of reals with specified addition and multiplication.

These constructions show that ordinary mathematical objects can be represented within set theory. They do not make one coding uniquely intrinsic: alternative constructions can produce isomorphic number systems. The arithmetic and structural properties preserved by isomorphism are normally more significant than whether a particular chosen representation makes one encoded number literally a member of another.

Historical development

Collections and classes were used long before modern set theory, but nineteenth-century mathematics made infinite collections into explicit objects of study. Developments in analysis required precise treatment of real numbers, convergence, and sets of points. Bernard Bolzano investigated properties of infinity in his posthumously published Paradoxes of the Infinite in 1851. Richard Dedekind’s work on numbers and mappings helped establish structural treatments of infinite systems.

Georg Cantor developed set theory through research on trigonometric series and sets of real points. His 1874 paper proved the countability of the algebraic numbers and the uncountability of the real numbers. This separated infinite collections by size rather than treating infinity as a single undifferentiated concept. His later work introduced transfinite cardinal and ordinal numbers, and his 1891 diagonal argument supplied another method for proving uncountability.

In 1895, Cantor described a set as a collection into a whole of definite, distinct objects of intuition or thought. This formulation expresses the intuitive concept but is not an axiom system. The discovery of paradoxes showed that unrestricted collection formation needed revision. Contradictions involving the totality of ordinals, the totality of cardinals, and Russell’s membership condition exposed difficulties at the largest purported collections.

Gottlob Frege’s logical foundations of arithmetic were directly affected by Russell’s paradox. Russell communicated it to Frege in 1902, when the second volume of Frege’s Basic Laws of Arithmetic was approaching publication. The contradiction arose from a principle allowing unrestricted formation of value-ranges, not merely from a poor choice of notation.

Ernst Zermelo proposed an influential axiomatization in 1908, including an explicit form of the axiom of choice. Abraham Fraenkel and Thoralf Skolem developed important refinements in the 1920s, especially concerning replacement and first-order formulation. These developments led to the theory now called ZF. John von Neumann contributed the standard ordinal construction and important work on the organization of the set-theoretic universe.

Independence results transformed the subject in the twentieth century. Kurt Gödel established the relative consistency of choice and the generalized continuum hypothesis with ZF through his constructible universe, with results announced in 1938 and developed in a 1940 monograph. Paul Cohen introduced forcing in 1963 to establish the independence of choice from ZF and of the continuum hypothesis from ZFC. These results made the study of different possible set-theoretic universes a central part of the field, alongside the elementary language of sets used throughout mathematics.

Sets equipped with mathematical structure

A bare set records which elements are present, but not how they interact. A mathematical structure adds specified operations, relations, or distinguished subsets. For example, a group consists of a set with a binary operation satisfying associativity, an identity condition, and inverse conditions. A vector space combines a set of vectors with addition and scalar multiplication over a field. The same underlying set can support different structures.

The distinction between a carrier set and its structure explains the role of structure-preserving maps. An arbitrary bijection pairs elements, whereas a group homomorphism must also preserve multiplication. A linear map must preserve vector addition and scalar multiplication. Thus equal cardinality does not imply structural equivalence: two algebraic systems may have equally many elements but fail to be isomorphic.

In topology, a topological space is a set XX together with a collection τ⊆P(X)\tau\subseteq\mathcal P(X) of open sets. The collection must contain ∅\varnothing and XX, be closed under arbitrary unions, and be closed under finite intersections. The choice of τ\tau determines continuity and convergence behavior. A metric space supplies distances between points and thereby induces a topology, but many topological spaces are studied without a chosen metric.

In measure theory, a measure is defined on a specified family of subsets, not necessarily on every subset. A sigma-algebra contains the whole space and is closed under complements and countable unions. These closure properties ensure that countable combinations of measurable conditions remain measurable. A probability space consists of a sample set Ω\Omega, a sigma-algebra of events, and a probability measure assigning total mass 11 to Ω\Omega.

The restriction to measurable subsets is substantive. Under choice, some subsets of the real line cannot be assigned Lebesgue measure consistently with its defining properties. A probability model therefore does more than assign numbers to an arbitrary collection of outcomes; it specifies which collections are events within the model.

Set language also distinguishes types of mathematical investigation. Geometry studies sets with spatial structure; graph theory studies vertices connected by relations; analysis studies spaces and maps with limiting or quantitative structure. These subjects share underlying constructions while applying different criteria of equivalence and different admissible operations. Representing them through sets supplies a common framework without replacing their specialized concepts.

Logical interpretations and alternative foundations

Set operations closely parallel logical connectives. For a fixed xx,

x∈A∩B⟺(x∈A∧x∈B),x\in A\cap B\Longleftrightarrow(x\in A\land x\in B),

while union corresponds to disjunction and complementation to negation. Indexed unions and intersections similarly parallel existential and universal quantification. This relationship explains why many set identities can be established by logical transformations of membership statements.

A subset A⊆UA\subseteq U can also be represented by its indicator function

1A:U→{0,1},1A(x)={1,x∈A,0,x∉A.\mathbf 1_A:U\to\{0,1\}, \qquad \mathbf 1_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}

In classical mathematics, subsets of UU correspond exactly to such functions. Intersection becomes pointwise multiplication, while complement becomes 1−1A1-\mathbf 1_A. This is useful in counting, integration, and probability.

The classical correspondence uses the principle that each membership statement is either true or false. In intuitionistic logic, the law of excluded middle is not accepted without proof in every instance. A subset need not have decidable membership, so a function into the two-element set assigning a definite answer to every membership question need not exist. Constructive set theories retain substantial mathematics while changing which logical inferences are available.

Type theory offers another foundational organization. Objects are assigned types, and permitted constructions depend on those types. A type is not simply an unrestricted set in the ZFC sense, although there are close interpretations between particular type theories and set theories. Dependent types can express families whose members vary with an input, linking logic and mathematical construction in ways used by proof assistants.

Category theory emphasizes objects and the maps between them. The category of sets has sets as objects and functions as morphisms. Its structural properties characterize products, disjoint unions, and function spaces without requiring a particular membership encoding for every construction. Size distinctions remain important: the category of all sets is not itself a set-sized collection of objects in ordinary ZFC.

The word “set” is also extended in specialized directions. A multiset records multiplicities, so two occurrences of an element can differ from one. A fuzzy set assigns membership grades, commonly values in [0,1][0,1], rather than ordinary yes-or-no membership. These are additional mathematical structures, not exceptions to extensional equality for ordinary sets. Keeping the underlying notion distinct prevents confusion between membership, frequency, uncertainty, and graded classification.

Computational representations and applications

In computer science, a set is an abstract data type supporting operations such as membership testing, insertion, deletion, union, and intersection. Its mathematical specification ignores order and duplicate insertions. A concrete implementation, however, must represent elements in memory and decide when two stored values count as equal. Numerical equality, object identity, and user-defined comparison rules can produce different computational behavior.

A hash table stores elements using hash values that help locate candidates for equality checking. With suitable hashing and controlled occupancy, membership, insertion, and deletion commonly have expected constant-time performance. These are implementation-dependent complexity claims, not properties of mathematical sets. Severe collisions or unsuitable inputs can produce much worse behavior. Equality and hashing must agree: values regarded as equal must have equal hash values.

Balanced search trees provide another representation. They require an ordering compatible with the intended distinction between elements and support membership and updates in logarithmic time. They also support ordered traversal and range queries, operations not intrinsic to an unordered mathematical set. For a small finite universe, a bit vector represents a subset by assigning one bit to each possible element. Union and intersection then become bitwise operations, often processing many potential members at once.

The full power set is usually too large to enumerate. An nn-element universe has 2n2^n subsets, so even moderate increases in nn cause exponential growth. Symbolic representations can describe families of subsets without storing each separately. Conversely, listing a handful of members does not represent an infinite set unless accompanied by a rule for the remaining members.

Relational databases use set-based ideas: a relation is mathematically a set of tuples, and relational operations include selection, projection, and union. Practical SQL systems commonly use duplicate-preserving, or bag, semantics by default, so database query results need not be sets in the strict mathematical sense. Explicit duplicate elimination changes both semantics and computational cost.

Sets also appear in automated verification and static analysis. A program state can be modeled as an element of a state space, and a collection of states can describe possible executions. A transition relation maps current possibilities to subsequent ones. Reachability calculations repeatedly enlarge a set until a fixed point is reached, when another step adds no new states. For finite state spaces this process can terminate by exhaustion; for infinite spaces it often requires symbolic descriptions or approximations. The mathematical language of sets specifies the intended meaning even when the implementation stores only a compressed or approximate representation.