Bifalgorithm post · Brisk · Chapter 1
What is a partition of a set?
What is a partition of a set? (Brisk · Chapter 1) — "A partition is a group of subsets of another set that together are both collectively exhaustive and mutual…
Ideas in this flowchart
- Partition of sets
- A partition is a group of subsets that is collectively exhaustive and mutually exclusive.
- Every element of the original set belongs to exactly one subset.
- Formal characterization: X₁ ∪ X₂ ∪ · · · ∪ Xₙ = X and Xᵢ ∩ Xⱼ = ∅ for all i, j.
- Collectively exhaustive: combining all subsets gives exactly the original set X.
- Mutually exclusive: no two subsets have an element in common.
- Example set D = {Dad, Mom, Lizzy, T.J., Marina}.
- Valid partition: {Lizzy, T.J.}, {Mom, Dad}, and {Marina}.
- Valid partition with empty subsets: ∅, ∅, {Lizzy, T.J., Marina, Mom, Dad}, and ∅.
- Not a partition: {Mom, Lizzy, T.J.} and {Dad}, because Marina is omitted.
- Not a partition: {Dad}, {Mom, T.J.}, and {Marina, Lizzy, Dad}, because Dad appears twice.
