# Equivalence of Definitions of Set Partition

## Contents

## 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$.

- $\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$