Equivalence of Definitions of Set Partition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set


The following definitions of the concept of Set Partition are equivalent:

Definition 1

A partition of $S$ is a set of subsets $\Bbb S$ of $S$ such that:

$(1): \quad$ $\Bbb S$ is pairwise disjoint: $\forall S_1, S_2 \in \Bbb S: S_1 \cap S_2 = \O$ when $S_1 \ne S_2$
$(2): \quad$ The union of $\Bbb S$ forms the whole set $S$: $\displaystyle \bigcup \Bbb S = S$
$(3): \quad$ None of the elements of $\Bbb S$ is empty: $\forall T \in \Bbb S: T \ne \O$.

Definition 2

A partition of $S$ is a set of non-empty subsets $\Bbb S$ of $S$ such that each element of $S$ lies in exactly one element of $\Bbb S$.


Proof

Definition 1 implies Definition 2

Let $\Bbb S$ be a set of subsets $\Bbb S$ of $S$ such that:

$(1): \quad$ $\Bbb S$ is pairwise disjoint: $\forall S_1, S_2 \in \Bbb S: S_1 \cap S_2 = \O$ when $S_1 \ne S_2$
$(2): \quad$ The union of $\Bbb S$ forms the whole set $S$: $\displaystyle \bigcup \Bbb S = S$
$(3): \quad$ None of the elements of $\Bbb S$ is empty: $\forall T \in \Bbb S: T \ne \O$.


By $(3)$ all sets in $\Bbb S$ are non-empty.


Suppose there exists $x \in S$ in more than one set of $\Bbb S$.

That is:

$\exists S_1, S_2 \in \Bbb S, S_1 \ne S_2: x \in S_1 \land x \in S_2$

Then by definition of set intersection:

$x \in S_1 \cap S_2$

and so $S_1 \cap S_2 \ne \varnothing$.

This contradicts condition $(1)$.

So no element of $S$ can be in more than one set of $\Bbb S$.


Suppose there exists $x \in S$ in none of the sets of $\Bbb S$.

Then $\displaystyle x \notin \bigcup \Bbb S$ and so $\Bbb S \notin S$.

This contradicts condition $(2)$.

So every element of $S$ is in at least one set of $\Bbb S$.


Thus $x$ lies in exactly one element of $\Bbb S$.

Hence it follows that $\Bbb S$ is a set of non-empty subsets of $S$ such that each element of $S$ lies in exactly one element of $\Bbb S$.

$\Box$


Definition 2 implies Definition 1

Let $\Bbb S$ be a set of non-empty subsets of $S$ such that each element of $S$ lies in exactly one element of $\Bbb S$.


$(3)$ is fulfilled automatically by definition.


Consider $\Bbb S$.

From Union of Subsets is Subset: Subset of Power Set:

$\displaystyle \bigcup \Bbb S \subseteq S$

Let $x \in T$.

By hypothesis:

$\exists S_1 \in \Bbb S: x \in S_1$

That is:

$\displaystyle x \in \bigcup \Bbb S$

and so:

$\displaystyle S \subseteq \bigcup \Bbb S$

By definition of set equality:

$\displaystyle \bigcup \Bbb S = S$

thus demonstrating that $(2)$ holds.


Suppose $\Bbb S$ were not pairwise disjoint, and that:

$\exists S_1, S_2 \in \Bbb S: S_1 \cap S_2 \ne \O$

Then:

$\exists x \in S: x \in S_1 \cap S_2$

By definition of set intersection:

$x \in S_1$ and $x \in S_2$

thus contradicting the supposition that each element of $S$ lies in exactly one element of $\Bbb S$.

So $\Bbb S$ is pairwise disjoint and so $(1)$ holds.

Hence the result.

$\blacksquare$