Concept

What is a partition of a set?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"A partition is a group of subsets of another set that together are both collectively exhaustive and mutually exclusive. This means that every element of the original set is in one and only one of the sets in the partition. Formally, a partition of X is a group of sets X₁, X₂, . . . , Xₙ such that: X₁ ∪ X₂ ∪ · · · ∪ Xₙ = X, and Xᵢ ∩ Xⱼ = ∅ for all i, j. The first line says that if we combine the contents of all of them, we get everything that’s in X (and nothing more). This is called being collectively exhaustive. The second line says that no two of the sets have anything in common: they are mutually exclusive. Suppose the set D is {Dad, Mom, Lizzy, T.J., Marina}. A partition is any way of dividing D up into subsets that meet the above conditions. One such partition is: {Lizzy, T.J.}, {Mom, Dad}, and {Marina}. Another one is: {Lizzy}, {T.J.}, {Mom}, and {Marina, Dad}. Yet another is: ∅, ∅, {Lizzy, T.J., Marina, Mom, Dad}, and ∅. All of these are ways of dividing up the Davies family into groups so that no one is in more than one group, and everyone is in some group. The following is not a partition: {Mom, Lizzy, T.J.}, and {Dad} because it leaves out Marina. This, too, is not a partition: {Dad}, {Mom, T.J.}, and {Marina, Lizzy, Dad} because Dad appears in two of the subsets."

Related Ideas

What is a partition of a set? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm