World Library  
Flag as Inappropriate
Email this Article

Disjoint sets

Article Id: WHEBN0000039359
Reproduction Date:

Title: Disjoint sets  
Author: World Heritage Encyclopedia
Language: English
Subject: Glossary of topology, Urysohn's lemma, Connected space, Formal grammar, Probability space
Publisher: World Heritage Encyclopedia

Disjoint sets

Two disjoint sets.

In mathematics, two sets are said to be disjoint if they have no element in common. Equivalently, 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.


This definition of disjoint sets can be extended to any family of sets. A family of sets is pairwise disjoint or mutually disjoint if every two different sets in the family are disjoint.[1] For example, the collection of sets { {1}, {2}, {3}, ... } is pairwise disjoint.

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.[2]

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.[3]


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

Two sets A and B are disjoint if and only if their intersection A\cap B 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.[4]

A family F of sets is pairwise disjoint if, for every two sets in the family, their intersection is empty.[1] If the family contains more than one set, this implies that the intersection of the whole family is also empty. However, a family of only one set is pairwise disjoint, regardless of whether that set is empty, and may have a non-empty intersection. Additionally, a family of sets may have an empty intersection without being pairwise disjoint.[5] For instance, the three sets { {1, 2}, {2, 3}, {1, 3} } have an empty intersection but are not pairwise disjoint. In fact, there are no two disjoint sets in this collection.

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.[6]

Disjoint unions and partitions

A partition of a set X is any collection of mutually disjoint non-empty sets whose union is X.[7] 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.[7] Disjoint-set data structures[8] and partition refinement[9] 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.[10] 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.[11] 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.[12] 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.[13]

See also


  1. ^ a b c d  .
  2. ^ Halbeisen, Lorenz J. (2011), Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer monographs in mathematics, Springer, p. 184,  .
  3. ^ Copson, Edward Thomas (1988), Metric Spaces, Cambridge Tracts in Mathematics 57, Cambridge University Press, p. 62,  .
  4. ^ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA textbooks, Mathematical Association of America, p. 59,  .
  5. ^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), A Transition to Advanced Mathematics, Cengage Learning, p. 95,  .
  6. ^  .
  7. ^ a b Halmos (1960), p. 28.
  8. ^  .
  9. ^ Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing 16 (6): 973–989,  .
  10. ^ Ferland, Kevin (2008), Discrete Mathematics: An Introduction to Proofs and Combinatorics, Cengage Learning, p. 45,  .
  11. ^ 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,  .
  12. ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21,  .
  13. ^ Lee, John M. (2010), Introduction to Topological Manifolds, Graduate Texts in Mathematics 202 (2nd ed.), Springer, p. 64,  .

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.