Jump to content

Disjoint sets

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Wcherowi (talk | contribs) at 20:30, 19 July 2020 (Reverted good faith edits by 27.62.239.31 (talk): Not an improvement (TW)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

This article is about the mathematical concept. For the data structure, see Disjoint-set data structure.
Two disjoint sets.

In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.[1] For example, {1, 2, 3} and {4, 5, 6} are disjoint sets, while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of more than two sets is called disjoint if any two distinct sets of the collection are disjoint.

Generalizations

A disjoint collection of sets

This definition of disjoint sets can be extended to a family of sets : the family is pairwise disjoint, or mutually disjoint if whenever . Alternatively, some authors use the term disjoint to refer to this notion as well.

For families the notion of pairwise disjoint or mutually disjoint is sometimes defined in a subtly different manner, in that repeated identical members are allowed: the family is pairwise disjoint if whenever (every two distinct sets in the family are disjoint).[2] For example, the collection of sets { {0,1,2}, {3,4,5}, {6,7,8}, ... } is disjoint, as is the set { {...,-2,0,2,4,...}, {...,-3,-1,1,3,5 }} of the two parity classes of integers; the family with 10 members is not disjoint (because the classes of even and odd numbers are each present five times), but it is pairwise disjoint according to this definition (since one only gets a non-empty intersection of two members when the two are the same class).

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]

Intersections

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

Two sets A and B are disjoint if and only if their intersection is the empty set.[1] It follows from this definition that every set is disjoint from the empty set, and that the empty set is the only set that is disjoint from itself.[5]

If a collection contains at least two sets, the condition that the collection is disjoint implies that the intersection of the whole collection is empty. However, a collection of sets may have an empty intersection without being disjoint. Additionally, while a collection of less than two sets is trivially disjoint, as there are no pairs to compare, the intersection of a collection of one set is equal to that set, which may be non-empty.[2] For instance, the three sets { {1, 2}, {2, 3}, {1, 3} } have an empty intersection but are not disjoint. In fact, there are no two disjoint sets in this collection. Also the empty family of sets is pairwise disjoint.[6]

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]

Disjoint unions and partitions

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]

See also

References

  1. ^ a b Halmos, P. R. (1960), Naive Set Theory, Undergraduate Texts in Mathematics, Springer, p. 15, ISBN 9780387900926.
  2. ^ a b Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), A Transition to Advanced Mathematics, Cengage Learning, p. 95, ISBN 978-0-495-56202-3.
  3. ^ Halbeisen, Lorenz J. (2011), Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer monographs in mathematics, Springer, p. 184, ISBN 9781447121732.
  4. ^ Copson, Edward Thomas (1988), Metric Spaces, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, p. 62, ISBN 9780521357326.
  5. ^ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA textbooks, Mathematical Association of America, p. 59, ISBN 9780883857793.
  6. ^ See answers to the question ″Is the empty family of sets pairwise disjoint?″
  7. ^ Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038.
  8. ^ a b Halmos (1960), p. 28.
  9. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Chapter 21: Data structures for Disjoint Sets", Introduction to Algorithms (Second ed.), MIT Press, pp. 498–524, ISBN 0-262-03293-7.
  10. ^ Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035.
  11. ^ Ferland, Kevin (2008), Discrete Mathematics: An Introduction to Proofs and Combinatorics, Cengage Learning, p. 45, ISBN 9780618415380.
  12. ^ Arbib, Michael A.; Kfoury, A. J.; Moll, Robert N. (1981), A Basis for Theoretical Computer Science, The AKM series in Theoretical Computer Science: Texts and monographs in computer science, Springer-Verlag, p. 9, ISBN 9783540905738.
  13. ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21, ISBN 9781852332471.
  14. ^ Lee, John M. (2010), Introduction to Topological Manifolds, Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64, ISBN 9781441979407.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Disjoint_sets&oldid=968506680"