Definition:Set Partition

Although this article appears correct, it's inelegant. There has to be a better way of doing it. In some places, e.g. Quotient Set Determined by Relation Induced by Partition is That Partition, $\Bbb S$ is instead written as $\PP$. While not wrong, it would be an idea to settle on a single notation You can help Proof Wiki by redesigning it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Improve}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Definition

Let $S$ be a set.

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$: $\ds \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$.

Component

The elements $S_1, S_2, \ldots \in \mathbb S$ are known as the components of the partition.

Finite Expansion

Let $S$ be a set.

Let $\Bbb S = \set {S_1, S_2, \ldots, S_n}$ form a partition of $S$.

Then the representation by such a partition $\ds \bigcup_{k \mathop = 1}^n S_k = S$ is also called a finite expansion of $S$.

The notations:

$S = S_1 \mid S_2 \mid \cdots \mid S_n$

or:

$\Bbb S = \set {S_1 \mid S_2 \mid \cdots \mid S_n}$

are sometimes seen.

Partitioning

Let $S$ be a set.

Let $\family {S_i}_{i \mathop \in I}$ be a family of subsets of $S$ such that:

$(1): \quad \forall i \in I: S_i \ne \O$, that is, none of $S_i$ is empty

$(2): \quad \ds S = \bigcup_{i \mathop \in I} S_i$, that is, $S$ is the union of $\family {S_i}_{i \mathop \in I}$

$(3): \quad \forall i, j \in I: i \ne j \implies S_i \cap S_j = \O$, that is, the elements of $\family {S_i}_{i \mathop \in I}$ are pairwise disjoint.

Then $\family {S_i}_{i \mathop \in I}$ is a partitioning of $S$.

The image of this partitioning is the set $\set {S_i: i \in I}$ and is called a partition of $S$.

Note the difference between:

the partitioning, which is an indexing function (that is a mapping)

and

the partition, which is the effect (that is, the image) of that mapping.

Also known as

A partition is sometimes called a decomposition.

This same definition is also encountered in the field of combinatorics.

Also defined as

Some sources do not impose the condition that all sets in $\Bbb S$ are non-empty.

This is most probably more likely to be an accidental omission rather than a deliberate attempt to allow $\O$ to be an element of a partition.

The point is minor; proofs of partitionhood usually include a demonstration that all elements of such a partition are indeed non-empty.

Examples

Integers by Sign

Let $\Z$ denote the set of integers.

Let $\Z_{> 0}$ denote the set of strictly positive integers.

Let $\Z_{< 0}$ denote the set of strictly negative integers.

Let $\Z_0$ denote the singleton $\set 0$

Then $P = \set {\Z_{> 0}, \Z_{< 0}, \Z_0}$ forms a partition of $\Z$.

Partition into Singletons

Let $S$ be a set.

Consider the family of subsets $\family {\set x}_{x \mathop \in S}$ indexed by $S$ itself.

Then $\family {\set x}_{x \mathop \in S}$ is a partitioning of $S$ into singletons.

Its associated partition is:

$\set {\set x: x \in S}$

Also see

• Equivalence of Definitions of Set Partition

• Definition:Partition (Topology): a slightly more specialized definition.

• Results about set partitions can be found here.