294:. According to one such definition, the family is disjoint if each two sets in the family are either identical or disjoint. This definition would allow pairwise disjoint families of sets to have repeated copies of the same set. According to an alternative definition, each two sets in the family must be disjoint; repeated copies are not allowed. The same two definitions can be applied to an indexed family of sets: according to the first definition, every two distinct indices in the family must name sets that are disjoint or identical, while according to the second, every two distinct indices must name disjoint sets. For example, the family of sets
38:
90:
563:
may mean one of two things. Most simply, it may mean the union of sets that are disjoint. 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. For instance two sets may be made
564:
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. 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.
496:
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
392:
555:
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.
174:
516:
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.
497:
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. For instance, the three sets
288:
487:
231:
205:
501:
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.
251:
81:
while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of two or more sets is called disjoint if any two distinct sets of the collection are disjoint.
493:. 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.
394:
with 10 members has five repetitions each of two disjoint sets, so it is pairwise disjoint under the first definition but not under the second.
305:
1040:
666:
508:
is a system of sets within which the only subfamilies with empty intersections are the ones that are pairwise disjoint. For instance, the
628:
993:
968:
941:
916:
846:
789:
747:
720:
693:
636:
420:
with more strict conditions than disjointness. For instance, two sets may be considered to be separated when they have disjoint
573:
936:, The AKM series in Theoretical Computer Science: Texts and monographs in computer science, Springer-Verlag, p. 9,
548:
425:
31:
837:
128:
1045:
579:
449:
433:
70:
177:
66:
824:
552:
540:
398:
269:
775:
887:
532:
525:
421:
1013:
989:
964:
937:
912:
842:
785:
743:
716:
689:
683:
662:
632:
58:
958:
906:
779:
737:
710:
656:
622:
466:
871:
828:
820:
584:
210:
115:, for example). In some sources this is a set of sets, while other sources allow it to be a
883:
781:
Combinatorics: Set
Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability
183:
879:
544:
509:
715:, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, p. 62,
832:
560:
417:
236:
121:
107:
102:
98:
1034:
988:, Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64,
891:
505:
437:
429:
402:
1016:
862:
Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms",
618:
595:
513:
50:
448:
Disjointness of two sets, or of a family of sets, may be expressed in terms of
37:
17:
406:
46:
547:
that describes whether two elements belong to the same set in the partition.
1021:
736:
Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012),
490:
255:
112:
74:
30:
This article is about the mathematical concept. For the data structure, see
763:
598:, the problem of finding the largest disjoint subfamily of a family of sets
89:
590:
413:
387:{\displaystyle (\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}}
116:
266:
There are two subtly different definitions for when a family of sets
875:
742:, MAA textbooks, Mathematical Association of America, p. 59,
88:
54:
36:
908:
Discrete
Mathematics: An Introduction to Proofs and Combinatorics
401:
if their intersection is small in some sense. For instance, two
685:
Combinatorial Set Theory: With a Gentle
Introduction to Forcing
688:, Springer monographs in mathematics, Springer, p. 184,
531:
is any collection of mutually disjoint non-empty sets whose
298:
is disjoint according to both definitions, as is the family
275:
655:
Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010),
302:
of the two parity classes of integers. However, the family
932:
Arbib, Michael A.; Kfoury, A. J.; Moll, Robert N. (1981),
105:
of sets. By definition, a collection of sets is called a
69:
in common. Equivalently, two disjoint sets are sets whose
835:(2001), "Chapter 21: Data structures for Disjoint Sets",
957:
Monin, Jean François; Hinchey, Michael Gerard (2003),
539:. Every partition can equivalently be described by an
469:
308:
272:
239:
213:
186:
131:
97:
This definition of disjoint sets can be extended to
300:{ {..., −2, 0, 2, 4, ...}, {..., −3, −1, 1, 3, 5} }
481:
386:
282:
245:
225:
199:
168:
841:(Second ed.), MIT Press, pp. 498–524,
764:″Is the empty family of sets pairwise disjoint?″
463:are disjoint if and only if their intersection
587:, numbers with disjoint sets of prime divisors
180:(that is, it is a function that assigns a set
8:
379:
355:
341:
312:
169:{\displaystyle \left(A_{i}\right)_{i\in I},}
77:. For example, {1, 2, 3} and {4, 5, 6} are
784:, Cambridge University Press, p. 82,
650:
648:
468:
348:
337:
336:
307:
274:
273:
271:
238:
212:
191:
185:
151:
141:
130:
934:A Basis for Theoretical Computer Science
803:
801:
613:
611:
296:{ {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... }
607:
259:(and elements of its domain are called
807:
986:Introduction to Topological Manifolds
119:of sets, with some sets repeated. An
7:
658:A Transition to Advanced Mathematics
409:may be said to be almost disjoint.
629:Undergraduate Texts in Mathematics
25:
911:, Cengage Learning, p. 45,
661:, Cengage Learning, p. 95,
436:are sets separated by a nonzero
416:, there are various notions of
739:Bridge to Abstract Mathematics
709:Copson, Edward Thomas (1988),
520:Disjoint unions and partitions
345:
309:
283:{\displaystyle {\mathcal {F}}}
176:is by definition a set-valued
27:Sets with no element in common
1:
682:Halbeisen, Lorenz J. (2011),
574:Hyperplane separation theorem
93:A disjoint collection of sets
1041:Basic concepts in set theory
960:Understanding Formal Methods
762:See answers to the question
549:Disjoint-set data structures
233:in its domain) whose domain
32:Disjoint-set data structure
1062:
838:Introduction to Algorithms
499:{ {1, 2}, {2, 3}, {1, 3} }
29:
864:SIAM Journal on Computing
580:Mutually exclusive events
434:positively separated sets
963:, Springer, p. 21,
631:, Springer, p. 15,
576:for disjoint convex sets
405:whose intersection is a
397:Two sets are said to be
905:Ferland, Kevin (2008),
482:{\displaystyle A\cap B}
483:
388:
284:
247:
227:
226:{\displaystyle i\in I}
201:
170:
94:
42:
984:Lee, John M. (2010),
825:Leiserson, Charles E.
484:
389:
285:
248:
228:
202:
200:{\displaystyle A_{i}}
171:
92:
40:
553:partition refinement
541:equivalence relation
467:
399:almost disjoint sets
306:
270:
237:
211:
184:
129:
1014:Weisstein, Eric W.
526:partition of a set
479:
452:of pairs of them.
428:. Similarly, in a
384:
280:
243:
223:
197:
166:
95:
43:
829:Rivest, Ronald L.
821:Cormen, Thomas H.
668:978-0-495-56202-3
292:pairwise disjoint
246:{\displaystyle I}
207:to every element
41:Two disjoint sets
16:(Redirected from
1053:
1046:Families of sets
1027:
1026:
1000:
998:
981:
975:
973:
954:
948:
946:
929:
923:
921:
902:
896:
894:
859:
853:
851:
817:
811:
805:
796:
794:
772:
766:
760:
754:
752:
733:
727:
725:
706:
700:
698:
679:
673:
671:
652:
643:
641:
624:Naive Set Theory
615:
585:Relatively prime
510:closed intervals
500:
488:
486:
485:
480:
393:
391:
390:
385:
383:
382:
340:
301:
297:
289:
287:
286:
281:
279:
278:
252:
250:
249:
244:
232:
230:
229:
224:
206:
204:
203:
198:
196:
195:
175:
173:
172:
167:
162:
161:
150:
146:
145:
103:indexed families
99:families of sets
65:if they have no
21:
1061:
1060:
1056:
1055:
1054:
1052:
1051:
1050:
1031:
1030:
1017:"Disjoint Sets"
1012:
1011:
1008:
1003:
996:
983:
982:
978:
971:
956:
955:
951:
944:
931:
930:
926:
919:
904:
903:
899:
876:10.1137/0216062
861:
860:
856:
849:
833:Stein, Clifford
819:
818:
814:
806:
799:
792:
774:
773:
769:
761:
757:
750:
735:
734:
730:
723:
708:
707:
703:
696:
681:
680:
676:
669:
654:
653:
646:
639:
617:
616:
609:
605:
570:
545:binary relation
522:
498:
465:
464:
446:
344:
304:
303:
299:
295:
268:
267:
235:
234:
209:
208:
187:
182:
181:
137:
133:
132:
127:
126:
87:
85:Generalizations
61:are said to be
35:
28:
23:
22:
18:Disjoint subset
15:
12:
11:
5:
1059:
1057:
1049:
1048:
1043:
1033:
1032:
1029:
1028:
1007:
1006:External links
1004:
1002:
1001:
994:
976:
969:
949:
942:
924:
917:
897:
870:(6): 973–989,
854:
847:
812:
797:
790:
776:Bollobás, Béla
767:
755:
748:
728:
721:
701:
694:
674:
667:
644:
637:
606:
604:
601:
600:
599:
593:
588:
582:
577:
569:
566:
561:disjoint union
521:
518:
478:
475:
472:
445:
442:
418:separated sets
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
347:
343:
339:
335:
332:
329:
326:
323:
320:
317:
314:
311:
277:
262:
258:
253:is called its
242:
222:
219:
216:
194:
190:
165:
160:
157:
154:
149:
144:
140:
136:
125:
122:indexed family
108:family of sets
86:
83:
79:disjoint sets,
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1058:
1047:
1044:
1042:
1039:
1038:
1036:
1024:
1023:
1018:
1015:
1010:
1009:
1005:
997:
995:9781441979407
991:
987:
980:
977:
972:
970:9781852332471
966:
962:
961:
953:
950:
945:
943:9783540905738
939:
935:
928:
925:
920:
918:9780618415380
914:
910:
909:
901:
898:
893:
889:
885:
881:
877:
873:
869:
865:
858:
855:
850:
848:0-262-03293-7
844:
840:
839:
834:
830:
826:
822:
816:
813:
810:, p. 28.
809:
808:Halmos (1960)
804:
802:
798:
793:
791:9780521337038
787:
783:
782:
777:
771:
768:
765:
759:
756:
751:
749:9780883857793
745:
741:
740:
732:
729:
724:
722:9780521357326
718:
714:
713:
712:Metric Spaces
705:
702:
697:
695:9781447121732
691:
687:
686:
678:
675:
670:
664:
660:
659:
651:
649:
645:
640:
638:9780387900926
634:
630:
626:
625:
620:
619:Halmos, P. R.
614:
612:
608:
602:
597:
594:
592:
589:
586:
583:
581:
578:
575:
572:
571:
567:
565:
562:
557:
554:
550:
546:
542:
538:
534:
530:
527:
519:
517:
515:
511:
507:
502:
494:
492:
476:
473:
470:
462:
458:
453:
451:
450:intersections
444:Intersections
443:
441:
439:
435:
431:
427:
426:neighborhoods
423:
419:
415:
410:
408:
404:
403:infinite sets
400:
395:
376:
373:
370:
367:
364:
361:
358:
352:
349:
333:
330:
327:
324:
321:
318:
315:
293:
264:
260:
257:
254:
240:
220:
217:
214:
192:
188:
179:
163:
158:
155:
152:
147:
142:
138:
134:
123:
120:
118:
114:
111:(such as the
110:
109:
104:
100:
91:
84:
82:
80:
76:
72:
68:
64:
63:disjoint sets
60:
56:
52:
48:
39:
33:
19:
1020:
985:
979:
959:
952:
933:
927:
907:
900:
867:
863:
857:
836:
815:
780:
770:
758:
738:
731:
711:
704:
684:
677:
657:
623:
558:
536:
528:
523:
514:real numbers
506:Helly family
503:
495:
460:
456:
454:
447:
430:metric space
424:or disjoint
411:
396:
291:
265:
106:
96:
78:
71:intersection
62:
55:formal logic
44:
596:Set packing
51:mathematics
1035:Categories
603:References
407:finite set
290:is called
47:set theory
1022:MathWorld
491:empty set
474:∩
455:Two sets
371:…
353:∈
334:∈
328:∣
256:index set
218:∈
156:∈
113:power set
75:empty set
892:33265037
778:(1986),
621:(1960),
591:Separoid
568:See also
438:distance
422:closures
414:topology
178:function
117:multiset
884:0917035
512:of the
489:is the
261:indices
124:of sets
101:and to
73:is the
67:element
992:
967:
940:
915:
890:
882:
845:
788:
746:
719:
692:
665:
635:
57:, two
888:S2CID
533:union
990:ISBN
965:ISBN
938:ISBN
913:ISBN
843:ISBN
786:ISBN
744:ISBN
717:ISBN
690:ISBN
663:ISBN
633:ISBN
551:and
543:, a
459:and
59:sets
53:and
872:doi
535:is
412:In
263:).
49:in
45:In
1037::
1019:.
886:,
880:MR
878:,
868:16
866:,
831:;
827:;
823:;
800:^
647:^
627:,
610:^
559:A
524:A
504:A
440:.
432:,
1025:.
999:.
974:.
947:.
922:.
895:.
874::
852:.
795:.
753:.
726:.
699:.
672:.
642:.
537:X
529:X
477:B
471:A
461:B
457:A
380:}
377:9
374:,
368:,
365:1
362:,
359:0
356:{
350:n
346:)
342:}
338:Z
331:k
325:k
322:2
319:+
316:n
313:{
310:(
276:F
241:I
221:I
215:i
193:i
189:A
164:,
159:I
153:i
148:)
143:i
139:A
135:(
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
