ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# Partition of a set

A partition of a set X is a set P of nonempty subsets of X such that every element x in X is in exactly one of these subsets. The elements of P are sometimes called the blocks of the partition.

 Table of contents 1 Examples 2 Definition 3 Partitions and Equivalence Relations 4 Partial ordering of partitions: the "lattice of partitions" 5 The Number of Partitions

#### Examples

The set {1, 2, 3} has the following partitions

Note that
• { {}, {1,3}, {2} } is not a partition because it contains an empty subset.
• { {1,2}, {2, 3} } is not a partition because the element 2 is contained in more than one subset.
• { {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3. It is a partition of {1, 2}.

#### Definition

Suppose S is a set. P, a set of subsets of S, is a partition if:

1. The union of the elements of P is equal to S
2. The intersection of any two elements of P is empty
3. No element of P is empty

#### Partitions and Equivalence Relations

If an equivalence relation is given on the set X, then the set of all equivalence classes forms a partition of X. Conversely, if a partition P is given on X, we can define an equivalence relation on X by writing x ~ y iff there exists a member of P which contains both x and y. The notions of "equivalence relation" and "partition" are thus essentially equivalent.

#### Partial ordering of partitions: the "lattice of partitions"

The set of all partitions of a set is a partially ordered set; one may say that one partition is "finer" than another if it splits the set into smaller blocks. This partially ordered set is a lattice.

#### The Number of Partitions

The Bell number Bn (named in honor of Eric Temple Bell) is the number of different partitions of a set with n elements. The first several Bell numbers are B0=1, B1=1, B2=2, B3=5, B4=15, B5=52, B6=203.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.