partition

Sets that form a partition are mutually exclusive and collectively exhaustive.

Partition

$\{A_i\mid i\in I\}$ is a partition of $A$ if:

• $\forall i\in I:A_i\subseteq A\wedge A_i\ne \varnothing$ (all $A_i$ are non-empty and subsets of $A$)
• ${\bigcup }_{i\in I}{A}_i=A$ (the union of all $A_i$ is $A$ – they cover $A$)
• $\forall i,j\in I:i\ne j⟹A_i\cap A_j=\varnothing$ (all $A_i$ are pairwise disjoint)

$A_i$ are called the blocks of the partition.

Like a school: all students are in a single class, no classs is empty and all classes together make up the school.

Partitions for equivalence relations:
$P_R=\{[x{]}_R\mid x\in X\}$, $R\dots$ relation on $X$

Equivalence Relations ↔ Partitions

Every equivalence relation induces a partition and every partition induces an equivalence relation:

Equivalence Relation → Partition:
Given equivalence relation $R$ on $A$, the equivalence classes $[x{]}_R=\{y\in A\mid xRy\}$ form a partition. Properties of $R$ ensure partition properties: reflexivity means blocks are non-empty ($x\in [x{]}_R$), symmetry and transitivity ensure blocks are disjoint ($[x{]}_R=[y{]}_R$ or $[x{]}_R\cap [y{]}_R=\varnothing$), and together they guarantee blocks cover $A$ (${\bigcup }_{x\in A}[x{]}_R=A$).

Partition → Equivalence Relation:
Given partition $\{A_i\mid i\in I\}$ of $A$, define $xRy:⟺\exists i\in I:x,y\in A_i$. Partition properties ensure equivalence relation properties: non-empty blocks give reflexivity, disjoint blocks give symmetry, and covering gives transitivity.

Like sorting items into boxes: Each item goes in exactly one box (partition), and two items are related if they’re in the same box (equivalence relation).

If $E$ is the disjoint union of $\{A_j\}$, then $\{A_j\}$ is a partition of $E$.

Link to original