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
- How do partitions simplify counting?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How do partitions divide an event into mutually exclusive and exhaustive pieces?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Are {Mark, Luke} and {Matthew, Luke} a partition of G?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Do { Matthew, Mark, Luke } and { John } form a partition of G?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is this a partition of G into gospels with and without a Christmas story?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is this a partition of G into groups based on the writers’ nationalities?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How are all the subsets of a set formed?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What operations can be used to combine sets?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1