Disjoint sets

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Disjoint sets are sets that share no elements. If A and B have no elements in common, then A and B are disjoint.

Examples:
- {1, 2, 3} and {4, 5, 6} are disjoint.
- {1, 2, 3} and {3, 4, 5} are not disjoint.

A collection of two or more sets is disjoint if every pair of distinct sets in the collection is disjoint. There are two common ways to state this:

- Definition 1 (allows repeats): In a collection, two sets may be identical or disjoint, and the collection is disjoint if every pair is either identical or disjoint.
- Definition 2 (no repeats): In a collection, any two distinct sets must be disjoint; duplicates are not allowed.

An indexed family is just a list of sets labeled by indices. The same two definitions apply to indexed families.

Notes and examples:
- The family { {0, 1, 2}, {3, 4, 5}, {6, 7, 8} } is disjoint under both definitions.
- The pair of parity classes of integers {even numbers} and {odd numbers} are disjoint.
- A list like { {n + 2k | k ∈ Z} for n = 0, 1, ..., 9 } has repeats (five copies of two different sets), so it’s disjoint under Definition 1 but not under Definition 2.

Two sets are almost disjoint if their intersection is small (for example, infinite sets with a finite intersection).

In topology, there are stronger ideas of separation. For example, two sets can be separated by disjoint closures or disjoint neighborhoods; in metric spaces, sets can be positively separated by a positive distance.

Key fact: A ∩ B is empty exactly when A and B are disjoint. The empty set is disjoint from every set, and only the empty set is disjoint from itself. If a collection has at least two sets and is disjoint, the intersection of all the sets in the collection is empty. But having an empty overall intersection does not always mean the sets are pairwise disjoint (as shown by { {1, 2}, {2, 3}, {1, 3} } which has empty overall intersection but is not pairwise disjoint). The empty family (no sets) is considered pairwise disjoint.

Partition and equivalence:
- A partition of a set X is a collection of nonempty disjoint sets whose union is X.
- Partitions correspond to equivalence relations: elements in the same block are related.

Disjoint-set data structures and partition refinement:
- In computer science, these tools help keep track of partitions while you merge sets (union) or split them (refinement).
- A disjoint union means the union of sets that are already disjoint. If you unite non-disjoint sets, you can “make them disjoint” by tagging each element with which set it came from (a label). For many sets, you can tag each element with the index of the set it belongs to.