Fact-checked by Grok 2 weeks ago

Disjoint sets

In mathematics, particularly set theory, two sets are said to be disjoint if their intersection is the empty set, meaning they share no common elements.^[1] More generally, a family of sets is pairwise disjoint (or mutually disjoint) if the intersection of every pair of distinct sets in the family is empty.^[2] This concept is fundamental to understanding unions, partitions, and measures, where disjoint sets allow for additive properties, such as in the disjoint union operation and probability theory. Applications include set partitions, where a set is divided into non-overlapping subsets, and measure theory, where disjoint events simplify integration and probability calculations.^[3]

Basic Concepts

Definition

In set theory, two sets A and B are disjoint if they share no common elements, meaning their intersection is the empty set: A \cap B = \emptyset.^[4] This condition ensures that no element belongs to both sets simultaneously, distinguishing disjoint sets from those that overlap.^[5] The notion of disjointness extends naturally to collections of sets. A family of sets \{A_i \mid i \in I\}, where I is an index set, is pairwise disjoint if the intersection of any two distinct members is empty: A_i \cap A_j = \emptyset for all i \neq j in I.^[6] This pairwise condition applies to finite or infinite families and forms the basis for more advanced structures like partitions of a universal set. To distinguish the union of disjoint sets from the general case, mathematicians often use the disjoint union notation A \sqcup B, which is equivalent to the standard union A \cup B when A and B are disjoint but highlights the absence of overlap.^[3] This symbol extends to families as \bigsqcup_{i \in I} A_i.^[3]

Examples

A classic example of two disjoint sets involves the even and odd integers. Let E be the set of all even integers, E = \{ \dots, -4, -2, 0, 2, 4, \dots \}, and O be the set of all odd integers, O = \{ \dots, -3, -1, 1, 3, \dots \}. Their intersection is empty because no integer can be both even and odd, so E \cap O = \emptyset.^[6]^[7] In geometry, consider a closed disk in the plane, defined as all points at distance less than or equal to 1 from the origin. The interior of this disk, consisting of points strictly inside with distance less than 1, and its boundary, the circle of points exactly at distance 1, form disjoint sets. No point can simultaneously be strictly inside and on the boundary, ensuring their intersection is empty. The empty set \emptyset provides another fundamental example, as it is disjoint from every set, including itself. For any set A, \emptyset \cap A = \emptyset, since there are no elements to share. This holds even when A = \emptyset, as \emptyset \cap \emptyset = \emptyset.^[9] To contrast, consider the closed intervals [0, 2] and [1, 3] on the real line. These are not disjoint because their intersection [1, 2] contains all points from 1 to 2, which belong to both sets.^[10] Visual representations, such as Venn diagrams, illustrate disjoint sets by depicting two or more circles with no overlapping areas, emphasizing the absence of common elements.

Properties

Intersection Properties

One fundamental consequence of two sets A and B being disjoint is the additivity of their cardinalities when the sets are finite. Specifically, if A \cap B = \emptyset, then the cardinality of the union satisfies |A \cup B| = |A| + |B|.^[4] This holds because each element in the union belongs uniquely to either A or B, with no overlap, allowing the total count to be the direct sum of the individual counts. A proof proceeds by induction on the finite sizes: for base cases with one empty set, it reduces to the cardinality of the nonempty set; adding one element at a time preserves the sum due to disjointness.^[4] This additivity extends naturally to the realm of measures on measurable sets. For a measure \mu defined on a \sigma-algebra, if A and B are disjoint measurable sets, then \mu(A \cup B) = \mu(A) + \mu(B).^[11] A prominent example is the Lebesgue measure \lambda on \mathbb{R}^d, where disjoint measurable sets satisfy \lambda(A \cup B) = \lambda(A) + \lambda(B), reflecting the non-overlapping volumes.^[11] The proof follows from the definition of measurability and the subadditivity of outer measure, combined with the disjointness ensuring no double-counting in coverings.^[11] For infinite collections, the property generalizes to countable additivity in measure theory. A measure \mu is countably additive if, for a countable family of pairwise disjoint measurable sets \{E_n\}_{n=1}^\infty, \mu\left(\bigcup_{n=1}^\infty E_n\right) = \sum_{n=1}^\infty \mu(E_n).^[11] This holds for the Lebesgue measure, enabling the assignment of measures to countable disjoint unions like intervals covering the real line.^[11] The proof builds on finite additivity by taking limits of partial unions, using continuity of measure from below for increasing sequences.^[11]

Union Properties

When two sets A and B are disjoint, meaning A \cap B = \emptyset, their union A \cup B consists precisely of all elements from A together with all elements from B, with no duplication or overlap between the contributions of each set.^[3] This distinguishes the union of disjoint sets from the union of overlapping sets, where shared elements are counted only once but the overlap reduces the total distinct elements below the sum of individual sizes. In formal terms, the union coincides with the disjoint union operation, denoted A \sqcup B, which emphasizes the preservation of distinct origins for each element even when the sets are embedded in a larger structure.^[3] An adaptation of De Morgan's laws highlights a specific property for the complements of disjoint sets. By De Morgan's second law, the complement of an intersection equals the union of the complements: (A \cap B)^c = A^c \cup B^c. Since A and B are disjoint, A \cap B = \emptyset, and the complement of the empty set is the universal set U, so A^c \cup B^c = U.^[12] This means the union of the complements of two disjoint sets exhausts the entire universal set, a consequence that holds only when the original sets have no intersection. A collection of disjoint sets relates to the concept of a partition when their union covers the universal set. Specifically, if a family of pairwise disjoint nonempty sets has a union equal to U, it forms a partition of U, dividing the universal set into mutually exclusive components that together comprise the whole.^[13] More generally, if the union is a proper subset of U, the family constitutes a partial partition of that subset, maintaining the disjointness without full coverage.^[13]

Classifications

Pairwise Disjoint

In set theory, a family of sets \{A_i \mid i \in I\} is said to be pairwise disjoint if the intersection of any two distinct sets in the family is empty, that is, A_i \cap A_j = \emptyset for all i \neq j.^[2] This condition ensures that no element belongs to more than one set in the collection.^[2] For finite families, pairwise disjointness is particularly straightforward and implies that the intersection of all sets in the family is also empty.^[14] To illustrate, consider the finite family \{A_1, A_2, A_3\} where A_1 = \{1, 2\}, A_2 = \{3, 4, 5\}, and A_3 = \{6\}. Here, A_1 \cap A_2 = \emptyset, A_1 \cap A_3 = \emptyset, and A_2 \cap A_3 = \emptyset, confirming the family is pairwise disjoint.^[15] A key property of finite pairwise disjoint families is the additivity of cardinalities under union. Specifically, if \{A_i\}_{i=1}^n is a finite pairwise disjoint family, then the cardinality of the union equals the sum of the individual cardinalities: \left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i|. This follows directly from the disjointness, as there is no overlap to account for in counting elements. For the example above, |A_1 \cup A_2 \cup A_3| = 2 + 3 + 1 = 6.

Mutually Disjoint Families

A mutually disjoint family of sets, also known as a pairwise disjoint family, indexed by an arbitrary index set I, is a collection \{A_i \mid i \in I\} such that A_i \cap A_j = \emptyset for all distinct i, j \in I. This condition ensures that elements belong to at most one set in the collection.^[16]^[17] Examples of such families abound in analysis and algebra. A basic case involves the sets of rational numbers \mathbb{Q} and irrational numbers \mathbb{R} \setminus \mathbb{Q}, which form a two-element mutually disjoint family whose union is the real line \mathbb{R}. For infinite families, consider the standard basis vectors in an infinite-dimensional vector space, such as \ell^2(I) over an infinite index set I; the supports \operatorname{supp}(e_i) = \{i\} for each basis vector e_i yield a mutually disjoint family of singleton sets.^[18] When the index set I is uncountable, working with mutually disjoint families often encounters limitations in standard set theory without additional axioms. For instance, constructing a Hamel basis for a vector space over an uncountable index set, whose supports form such a family, relies on the axiom of choice to guarantee existence. A key theorem states that for a mutually disjoint family \{A_i \mid i \in I\}, the ordinary union \bigcup_{i \in I} A_i coincides with the disjoint union \bigsqcup_{i \in I} A_i, via a canonical bijection that identifies elements without overlap. This equivalence simplifies computations in set-theoretic constructions.

Operations

Disjoint Union

The disjoint union of two sets A and B, denoted A \sqcup B, is a set-theoretic construction that forms a canonical union by embedding the sets into disjoint copies, ensuring no overlap even if A and B intersect. Formally, it is defined as

A \sqcup B = \{(a, 1) \mid a \in A\} \cup \{(b, 2) \mid b \in B\},

where the tags $1 and $2 distinguish elements from each set; this is also known as a tagged union.^[19]^[20] This operation serves to artificially disjointify sets when necessary, allowing the union to proceed without loss of information about element origins, though its primary utility arises when the sets are already disjoint, in which case A \sqcup B is in bijection with the standard union A \cup B. The cardinality of the disjoint union satisfies |A \sqcup B| = |A| + |B| unconditionally, reflecting the additive structure imposed by the tagging; this equals |A \cup B| if and only if A and B are disjoint.^[19]^[20] For an indexed family of sets \{A_i \mid i \in I\}, the disjoint union extends naturally as the coproduct \bigsqcup_{i \in I} A_i = \bigcup_{i \in I} (A_i \times \{i\}), with alternative notations including \coprod_{i \in I} A_i or \sum_{i \in I} A_i emphasizing the categorical or additive aspects. The cardinality then generalizes to |\bigsqcup_{i \in I} A_i| = \sum_{i \in I} |A_i|, preserving the disjointness by construction.^[21]^[20]

Disjoint Sums in Algebra

In algebraic structures, the concept of disjoint sums extends the set-theoretic disjoint union by incorporating the respective operations of the structures, ensuring compatibility through componentwise definitions. In vector spaces over a field, the direct sum V \oplus W of two subspaces V and W is the subspace consisting of all sums v + w where v \in V, w \in W, and V \cap W = \{0\}, with addition and scalar multiplication defined componentwise on pairs (v, w).^[22] For groups, the disjoint sum depends on the structure: for abelian groups, it is the direct sum over disjoint index sets, where elements are formal sums with support in distinct indices and operations are componentwise, coinciding with the direct product.^[22] In the more general category of groups, the analogous construction is the free product, which amalgamates the groups without relations beyond their individual structures, serving as the coproduct for families indexed by disjoint sets.^[23]^[24] In the category of modules over a ring R, the coproduct is precisely the direct sum, often called the disjoint sum, where for modules M_i over a disjoint index set I, elements are finite sums \sum m_i with m_i \in M_i and at most one nonzero term per index, equipped with the module operations extended componentwise.^[22] This construction applies similarly to rings, where the direct sum of R-modules preserves the ring actions. A representative example is \mathbb{Z} \oplus \mathbb{Z}, which forms the integer lattice \mathbb{Z}^2 in the plane, generated by the basis vectors e_1 = (1,0) and e_2 = (0,1), with addition componentwise and the basis providing a disjoint decomposition.^[22]

Applications

The disjoint-set data structure is widely used in algorithm design for problems involving dynamic partitioning and connectivity queries. Its efficiency makes it ideal for scenarios where sets need to be merged repeatedly while checking membership or equivalence efficiently.^[25]

Graph Algorithms

A primary application is in Kruskal's algorithm for finding the minimum spanning tree (MST) of an undirected graph. Here, edges are sorted by weight, and the structure tracks connected components: before adding an edge, Find checks if its endpoints are in the same set (indicating a cycle); if not, Union merges the components. This ensures the algorithm builds a tree without cycles in O(E α(V)) time, where E is edges and V is vertices.^[25] Similarly, it supports cycle detection during graph construction by verifying if an edge connects elements already in the same set.^[26] The structure also computes connected components in undirected graphs, either statically by unioning adjacent vertices or dynamically as edges are added. For example, in network analysis, it groups vertices into components representing reachable subgraphs.^[25] In image processing, connected-component labeling uses it to identify and label contiguous regions in binary images by treating pixels as elements and adjacency as unions.

Other Applications

In compiler design, disjoint sets aid register allocation by modeling variable lifetimes and reuse, merging intervals of live ranges to assign registers without conflicts. For offline lowest common ancestors in trees, Tarjan's algorithm employs union-find to process queries in nearly linear time by unioning paths during a DFS traversal. Social network analysis uses it for friendship circles, where Union merges friends and Find checks indirect connections (e.g., if two users share a component). Procedural maze generation, such as randomized Kruskal's on a grid graph, unions adjacent cells to form paths while avoiding cycles. Dynamic connectivity problems, like link-cut trees, extend it for online edge insertions/deletions with connectivity queries.^[26]^[27]

References

[1]
[PDF] CMSC 420: Disjoint-Set Data Structures - UMD MATH
Disjoint-set data structures, also called union-find data structures, are a class of data structure which stores elements according to disjoint sets they are in ...
[2]
[PDF] 11 Data Structures for Disjoint Sets - Jeff Erickson
Disjoint set data structures have lots of applications. For instance, Kruskal's minimum spanning tree algorithm relies on such a data structure to maintain ...
[3]
Efficiency of a Good But Not Linear Set Union Algorithm
Efficiency of a Good But Not Linear Set Union Algorithm. Author: Robert Endre Tarjan ... Proc, 1969, pp 118-128. Google Scholar. [13]. TARJAN, R Testing flow ...
[4]
[PDF] Naive set theory. - Whitman People
Halmos —Naive Set Theory. John L. Kelley—Introduction to Modern Algebra. R ... disjoint finite sets E and F is equal to #(2?) + §{F). We observe now that.
[5]
Disjoint Sets -- from Wolfram MathWorld
Two sets A_1 and A_2 are disjoint if their intersection A_1 intersection A_2=emptyset, where emptyset is the empty set.
[6]
1.6 Families of Sets
An indexed family {Ai:i∈I} is pair-wise disjoint if Ai∩Aj=∅ whenever i and j are distinct elements of I. The indexed family of example 1.6.1 is pair-wise ...
[7]
Disjoint Union -- from Wolfram MathWorld
The disjoint union of two sets A and B is a binary operator that combines all distinct elements of a pair of given sets, while retaining the original set ...
[8]
Unions and Intersections of Sets - Department of Mathematics at UTSA
Nov 16, 2021 · } and the set of odd numbers {1, 3, 5, 7, 9, 11, ...}, because 9 is ... are disjoint, while the set of even numbers intersects the set of ...<|control11|><|separator|>
[9]
[PDF] Lecture 41: Some point-set topology of metric spaces - Ohio University
(d) X is the union of the pairwise disjoint sets int(E),∂(E), ext(E) ... Exterior, interior, and boundary points: Examples. Example 1: Let (X,d)=(R2,d ...
[10]
1A Set Terminology - University of Hawaii System
Certainly the empty set is disjoint from every other set, while the universal set meets every set except the empty set. example 3. Let the universal set be. U ...
[11]
21-110: Sets - CMU Math
A set is often written by listing its elements between curly braces { }. For example, a set containing the numbers 1, 2, and 3 would be written as {1, 2, 3}.
[12]
245A, Notes 1: Lebesgue measure
Summary of each segment:
[13]
de Morgan's Laws -- from Wolfram MathWorld
de Morgan's Laws: Let union represent "or", intersection represent "and", and ^' represent "not." Then, for two logical units E and F,
[14]
Set Partition -- from Wolfram MathWorld
A set partition of a set S is a collection of disjoint subsets of S whose union is S. The number of partitions of the set {k}_(k=1)^n is called a Bell number.
[15]
pairwise disjoint - PlanetMath
Mar 22, 2013 · These sets are said to be pairwise disjoint if for every pair of distinct elements α,β∈I α , β ∈ I , we have Eα∩Eβ=∅ E α ∩ E β = ∅ . Remark. The ...
[16]
Notes on Set Theory - Northwestern University
More generally, we will say that a (finite) collection of sets A1,...,An is pairwise disjoint if the intersection of any two of them is empty. Note that ...Missing: implies | Show results with:implies
[17]
[PDF] set theory
A and B are disjoint iff their intersection is empty. A collection of sets is pairwise disjoint iff any two members of the collection are disjoint. Page 3. 6.
[18]
2.3Indexed families of sets - SIUE
Definition2.3. An indexed family A={Aα∣α∈I} A = { A α ∣ α ∈ I } of sets is said to be pairwise disjoint if for any α,β∈I α , β ∈ I with α≠β, α ≠ β , Aα∩Aβ=∅, A ...Missing: mutually | Show results with:mutually
[19]
Definition:Pairwise Disjoint/Also known as - ProofWiki
mutually disjoint · non-intersecting. Some ... indexed family the compact term disjoint family is often seen. Sources. 1960: Paul R. Halmos: Naive Set Theory ...
[20]
Disjoint Set Definition - BYJU'S
Disjoint sets are those sets whose intersection with each other results in a null set. In Set theory, sometimes we notice that there are no common elements ...
[21]
[PDF] The Category of Sets - Princeton University
Oct 16, 2016 · Intuitively speaking, the coproduct X q Y is the disjoint union of the sets. X and Y . What we mean by “disjoint” here is that if X and Y share ...
[22]
[PDF] Chapter 2 - The category of sets - MIT OpenCourseWare
The coproduct of X and Y , denoted X \ Y , is defined as the “disjoint union” of X and Y , i.e. the set for which an element is either an element of X or an ...
[23]
[PDF] Category Theory
Let Q be the disjoint union of the Xi. Thus, Q = Si X0 ... ιi : Xi → Q by ιi(x)=(x, i). Claim: The pair (Q,{ιi}) is a coproduct of the family {Xi} in Set.<|control11|><|separator|>
[24]
Direct Sum -- from Wolfram MathWorld
Direct sums are defined for a number of different sorts of mathematical objects, including subspaces, matrices, modules, and groups.
[25]
Coproduct -- from Wolfram MathWorld
The coproduct is unique up to isomorphisms. In the category of sets, the coproduct is the disjoint union C= union ^._(i in I)X_i , and c_i ...
[26]
free product - PlanetMath
Mar 22, 2013 · ... groups has a free product, and the free product is unique up to isomorphism . The free product is the coproduct ...
[27]
1.4 Bell numbers
Definition 1.4.1 A partition of a set S is a collection of non-empty subsets Ai⊆S, 1≤i≤k (the parts of the partition), such that ⋃ki=1Ai=S and for every i≠j ...
[28]
[PDF] Chapter 3: Partitions and counting - Dartmouth Mathematics
described in terms of partitions of a set. A partition of a set U is a sub- division of the set into subsets that are disjoint and exhaustive, i.e.,.
[29]
[PDF] Equivalence Relations and Partitions - UCSB
Jun 18, 2013 · An equivalence relation ∼ on X gives rise to a partition of X into equivalence classes. Conversely, a partition of X gives rise to an ...
[30]
5.1 Equivalence Relations
Let A/∼ denote the collection of equivalence classes; A/∼ is a partition of A. (Recall that a partition is a collection of disjoint subsets of A whose union is ...
[31]
[PDF] The number of partitions of a set
The number of partitions is solely determined by n, the cardinality of X. Denote this number by dn (n-th Bell's number). We have d1 = 1, d2 = 2, d3 = 5, d4 ...
[32]
[PDF] CMSC 250: Set Theory and Proofs - UMD MATH
Mar 13, 2023 · Intersection and Disjoint Sets . . . . . . . . . . . . . . . . 5. 3.3. Complements ... Cardinality and Countability .
[33]
[PDF] An Introduction to Measure Theory - Terry Tao
countably additive theory. Definition 1.4.19 (Finitely additive ... use general facts about measure, such as countable additivity, which are not ...
[34]
[PDF] 1 Measure Theory - Princeton University
This chapter is devoted to the construction of Lebesgue measure in Rd and the study of the resulting class of measurable functions. After some.
[35]
Kolmogorov axioms of probability - The Book of Statistical Proofs
Jul 30, 2021 · We introduce three axioms of probability: P(E)∈R,P(E)≥0,for all E∈E. (1) P(Ω)=1. (2) Third axiom: The probability of any countable sequence of disjoint (ie ...
[36]
Probability | Axioms | Chance | Likelihood
Axioms of Probability: ... From the third axiom of probability, the probability of the union of two disjoint events is the summation of individual probabilities.
[37]
3.11: Properties of the Integral - Statistics LibreTexts
Apr 23, 2022 · Let A = { x ∈ S : f ⁡ ( x ) ≥ 0 } . Then A ∈ S and μ ⁡ ( A c ) = 0 . By the additivity of the integral over disjoint sets we have (3.11.6) ∫ S f ...