In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, 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

Intersection (set theory)

In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....

 is the empty set

Empty set

In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

, i.e. if


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

Formally, let I be an index set

Index set

In mathematics, the elements of a set A may be indexed or labeled by means of a set J that is on that account called an index set...

, and for each i in I, let A_i be a set. Then the family of sets {A_i : i ∈ I} is pairwise disjoint if for any i and j in I with i ≠ j,


For example, the collection of sets { {1}, {2}, {3}, ... } is pairwise disjoint. If {A_i} 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 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

Partition of a set

In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

 X is any collection of non-empty subsets {A_i : i ∈ I} of X such that {A_i} are pairwise disjoint and

See also

• Almost disjoint sets
  Almost disjoint sets
  In mathematics, two sets are almost disjoint if their intersection is small in some sense; different definitions of "small" will result in different definitions of "almost disjoint".-Definition:...
  
  
• Connectedness
  Connectedness
  In mathematics, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected...
  
  
• Disjoint union
  Disjoint union
  In mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...
  
  
• Disjoint-set data structure
  Disjoint-set data structure
  In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
  
  
• Independence (probability theory) (contrast)