Disjoint sets

Two sets are said to be almost disjoint sets if their intersection is small in some sense. For instance, two infinite sets whose intersection is a finite set may be said to be almost disjoint.[3]

In topology, there are various notions of separated sets with more strict conditions than disjointness. For instance, two sets may be considered to be separated when they have disjoint closures or disjoint neighborhoods. Similarly, in a metric space, positively separated sets are sets separated by a nonzero distance.[4]

Disjointness of two sets, or of a family of sets, may be expressed in terms of intersections of pairs of them.

A Helly family is a system of sets within which the only subfamilies with empty intersections are the ones that are pairwise disjoint. For instance, the closed intervals of the real numbers form a Helly family: if a family of closed intervals has an empty intersection and is minimal (i.e. no subfamily of the family has an empty intersection), it must be pairwise disjoint.[7]

A partition of a set X is any collection of mutually disjoint non-empty sets whose union is X.[8] Every partition can equivalently be described by an equivalence relation, a binary relation that describes whether two elements belong to the same set in the partition.[8] Disjoint-set data structures[9] and partition refinement[10] are two techniques in computer science for efficiently maintaining partitions of a set subject to, respectively, union operations that merge two sets or refinement operations that split one set into two.

A disjoint union may mean one of two things. Most simply, it may mean the union of sets that are disjoint.[11] But if two or more sets are not already disjoint, their disjoint union may be formed by modifying the sets to make them disjoint before forming the union of the modified sets.[12] For instance two sets may be made disjoint by replacing each element by an ordered pair of the element and a binary value indicating whether it belongs to the first or second set.[13] For families of more than two sets, one may similarly replace each element by an ordered pair of the element and the index of the set that contains it.[14]