Set Partition

The partition of sets is a very important subject, especially in probability theory, Lesbegue integral, among others. In the previous post we saw equivalence relations and they are directly related to the notion of partition of sets.

Definition

Definition (Partition) Let $A$ be a nonempty set ($A\neq \emptyset$) and a family $\mathcal{F}$ of nonempty subsets of $A$. The partition definition of $A$ is valid if the following statements are true:

• (a) any two elements of $\mathcal{F}$ are either equal or disjoint;

• (b) the union of the elements of $\mathcal{F}$ is equal to $A.$

Examples

Example 1: Family $\mathcal{F} = \\{ \\{1\\}, \\{2\\}, \\{3, 4\\} \\}$ is a partition of the set $A = \\{1, 2, 3, 4\\}.$

Example 2: Let $A=\mathbb{Z}$, the family $\mathcal{F} = \\{ 3\mathbb{Z}, 3\mathbb{Z} + 1, 3\mathbb{Z} + 2 \\}$ is a partition of the set $A.$

Example 3: Let $A=\mathbb{R}$, the family $\mathcal{F} = \\{ (-\infty,-1), [-1,1], (1,+\infty) \\}$ is a partition of the set $A.$

Next, we have Richard Dedekind, responsible for Dedeking cuts, construction of real numbers ($\mathbb{R}$).

Equivalence Relation determines Set Partition

Below we present a result that shows how the equivalence relation determines the partition of a set.

Theorem (Equivalence Relation determines Partition of Sets) If $\mathcal{R}$ is an equivalence relation on a nonempty set $A$, then $A/\mathcal{R}$ is a partition of $A.$

Demo:

Initially note that by the partition definition, we have to show that each element of $A/\mathcal{R}$ is non-empty and that the properties (a) and (b) of the definition hold.

For each $\overline{a} \in A/\mathcal{R}$, as $\mathcal{R}$ is reflexive, we have $a \in \overline{a}.$ Thus, we have $\overline{a}\neq \emptyset.$

• (a) For each $\overline{a}$ and $\overline{b}$ in $A/\mathcal{R},$ we have $\overline{a} \cap \overline{b} = \emptyset$ or $\overline{a} = \overline{b}.$

Now, suppose $\overline{a} \cap \overline{b} \neq \emptyset$ is $x \in \overline{a} \cap \overline{b}$. Then $x \in \overline{a}$ and $x \in \overline{b}$.

From the definition of equivalence classes, we have $x \mathcal{R} \overline{a}$ and $x \mathcal{R} \overline{b}$.

From the fact that $\mathcal{R}$ is symmetric and transitive, we obtain that $a\mathcal{R} b.$

From the equivalences of the theorem from the previous post we have $a = b,$ which shows (a).

• (b) The objective now is to show item (b), that is:

Equivalently:

The inclusion $\bigcup_{a \in A}\overline{a} \subseteq A$ is shown with $a \subseteq A$ for each $a \in A.$

Conversely, let $x \in A,$ and $x\mathcal{R}x,$ be $x \in \overline{x},$ which implies that $\bigcup_{a \in A}\overline{a}$

Consequently:

$\square$

Partition of Sets determines Equivalence Relation

Below we present a result that shows how the partition of a set determines an equivalence relation.

Theorem (Partition of Sets determines Equivalence Relation) Let $A$ be a non-empty set and $\mathcal{F}$ a partition of $A,$ then there is an equivalence relation $\mathcal{R}$ over $A$ such that $A/\mathcal{R} = \mathcal{F}.$

Demo:

For all $a, b \in A,$ we define $\mathcal{R}$ by:

• (Part 1) Show that $\mathcal{R}$ is an equivalence relation, which we will divide into 3 items:

(1) For every $a \in A,$ since $\bigcap \mathcal{F} = A,$ there is a $X \in \mathcal{F}$ such that $a \in X.$

Therefore, $a\mathcal{R}a,$ which represents that $\mathcal{R}$ is reflexive.

(2) For $a, b \in A,$ if $a\mathcal{R}b,$ then by the definition of $\mathcal{R},$ there is an element $X \in \mathcal{F},$ such that $a, b \in X,$ which implies that $b\mathcal{R} a.$

Therefore, $\mathcal{R}$ is symmetric.

(3) If $a, b, c \in A $ are such that $a\mathcal{R} b$ and $b\mathcal{R} c$, then there are $X, Y \in \mathcal{F}$ such that $a, b \in X$ and $b, c \in Y .$

Therefore, $b \in X \cap Y$, that is, $X \cap Y \neq \emptyset.$

Since $\mathcal{F}$ is a partition, we have $X = Y$ and then $a, c \in X = Y $

Consequently $a\mathcal{R} c.$

• (Part 2) Show now that $A/\mathcal{R} = \mathcal{F}.$

Given $a \in A,$ we have that there is a unique $X \in \mathcal{F},$ such that $a \in X,$ in which the uniqueness follows from property (a) to hold for $\mathcal{F}.$

From the definition of $\mathcal{R}$ we have that $\overline{a} = X,$ which implies that $A/\mathcal{R} \subseteq \mathcal{F}.$

On the other hand, for every $X \in F,$ with $X 6\neq \emptyset,$ we have that there is $a \in X.$

Therefore $X = \overline{a},$ which shows that $A/\mathcal{R} \supseteq \mathcal{F}.$

$\square$

Application

Example 4: Given the partition $\mathcal{F} = \\{\\{a, b\\}, \\{c\\}, \\{d, e, f\\}\\}$ of $A = \\{a, b, c, d, e, f\\},$ we have the associated equivalence relation.

This is the summary of Equivalence Relations. Wait for the next posts.