> [!NOTE] Definition (Partition of a Set) > Suppose $X$ is a non-empty [[Sets|set]]. A *partition* $\mathbb{P}$ of $X$ is a set of subsets of $X,$ $\mathbb{P} \subset \mathcal{P}(X)$ that satisfies following properties: > > (i) For all $p\in \mathbb{P},$ $p$ is non-empty > > (ii) The [[Union of sets|union]] of $\mathbb{P}$ is $X$: that is, $X= \bigcup_{P\in \mathbb{P}} P$. > > (iii) If $P,Q \in \mathbb{P}$ then either $P=Q$ or $P\cap Q = \emptyset$ (or equivalently $P \cap Q = \emptyset \implies P=Q$). > > The elements of $\mathbb{P}$ are called **parts** of the **partition**. # Properties Note that a [[Partition induces equivalence relation|partition of a set induces an equivalence relation on the set]]. Moreover, [[For every partition there is a unique equivalence relation|every partition corresponds to a unique equivalence relation and vice versa]]. By [[Cardinality of Union of Disjoint Sets]], if $A$ is finite set and $\{ A_{1},\dots A_{r} \}$ is a partition of $A$ then $|A|=|A_{1}|+|A_{2}|+\dots+|A_{r}|.$ ###### Counting partitions of finite sets: By [[Number of Partitions of n Letters into Subsets of Given Sizes]], there are $\frac{n!}{k_{1}!k_{2}!\dots k_{r}!}$ partitions of a finite set $A$ with $|A|=n$ into $r$ subsets $A_{1},\dots,A_{r}$ such that $|A_{1}|=k_{1},|A_{2}|=k_{2},\dots,|A_{r}|=k_{r}.$ The total number of partitions of $n$ letters is the $n$th [[Bell Numbers|Bell number]], $B_{n}.$ # Applications See [[Finite Partition of Closed Real Interval]].