Editing Disjoint sets (section)

==Disjoint unions and partitions==
A [[partition of a set]] ''X'' is any collection of mutually disjoint non-empty sets whose [[union (set theory)|union]] is ''X''.<ref name="h60-28">{{harvtxt|Halmos|1960}}, p.&nbsp;28.</ref> 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.<ref name="h60-28"/>
[[Disjoint-set data structure]]s<ref>{{Citation |first1=Thomas H. |last1=Cormen |author1-link=Thomas H. Cormen |first2=Charles E. |last2=Leiserson |author2-link=Charles E. Leiserson |first3=Ronald L. |last3=Rivest |author3-link=Ronald L. Rivest |first4=Clifford |last4=Stein |author4-link=Clifford Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press |year=2001 |isbn=0-262-03293-7 |chapter=Chapter 21: Data structures for Disjoint Sets |pages=498–524 }}.</ref> and [[partition refinement]]<ref>{{citation
 | last1 = Paige | first1 = Robert
 | last2 = Tarjan | first2 = Robert E.
 | doi = 10.1137/0216062
 | mr = 917035
 | issue = 6
 | journal = SIAM Journal on Computing
 | pages = 973–989
 | title = Three partition refinement algorithms
 | volume = 16
 | year = 1987| s2cid = 33265037
 }}.</ref> 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.<ref>{{citation|title=Discrete Mathematics: An Introduction to Proofs and Combinatorics|first=Kevin|last=Ferland|publisher=Cengage Learning|year=2008|isbn=9780618415380|page=45|url=https://books.google.com/books?id=gSeC4_uEPTUC&pg=PA45}}.</ref> 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.<ref>{{citation|title=A Basis for Theoretical Computer Science|series=The AKM series in Theoretical Computer Science: Texts and monographs in computer science|first1=Michael A.|last1=Arbib|first2=A. J.|last2=Kfoury|first3=Robert N.|last3=Moll|publisher=Springer-Verlag|year=1981|isbn=9783540905738|page=9}}.</ref> 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.<ref>{{citation|title=Understanding Formal Methods|first1=Jean François|last1=Monin|first2=Michael Gerard|last2=Hinchey|publisher=Springer|year=2003|isbn=9781852332471|page=21|url=https://books.google.com/books?id=rUudIPZD-B0C&pg=PA21}}.</ref>
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.<ref>{{citation|first=John M.|last=Lee|title=Introduction to Topological Manifolds|volume=202|series=Graduate Texts in Mathematics|publisher=Springer|edition=2nd|year=2010|isbn=9781441979407|page=64}}.</ref>