Disjoint sets

related topics
{math, number, function}

In mathematics and computer science, two sets are said to be disjoint if they have no element in common. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets.

Explanation

Formally, two sets A and B are disjoint if their intersection is the empty set, i.e. if

This definition extends to any collection of sets. A collection of sets is pairwise disjoint or mutually disjoint if any two sets in the collection are disjoint.

Formally, let I be an index set, and for each i in I, let Ai be a set. Then the family of sets {Ai : iI} is pairwise disjoint if for any i and j in I with ij,

For example, the collection of sets { {1}, {2}, {3}, ... } is pairwise disjoint. If {Ai} is a pairwise disjoint collection (containing at least two sets), then clearly its intersection is empty:

However, the converse is not true: the intersection of the collection {{1, 2}, {2, 3}, {3, 1}} is empty, but the collection is not pairwise disjoint. In fact, there are no two disjoint sets in this collection.

A partition of a set X is any collection of non-empty subsets {Ai : iI} of X such that {Ai} are pairwise disjoint and

References

See also

Full article ▸

related documents
Context-sensitive language
Sedenion
Galois group
Endomorphism ring
Markov process
Lazy initialization
Ring homomorphism
Co-NP
Sieve of Eratosthenes
Chart parser
Equivalence class
Center (group theory)
Euclidean distance
Recursive language
Greibach normal form
Measurable function
Harmonic analysis
Essential singularity
Direct sum of groups
Water, gas, and electricity
Derivative of a constant
Church–Rosser theorem
Co-NP-complete
Sigmoid function
Digital Signature Algorithm
JUnit
Uniform Resource Locator
Gabriel Lamé
Lint (software)
Power associativity