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.
Feed/

What is a partition of a set?

Channel

Brisk

1 page

"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."

Flowchart preview
Series cover
👍
0
0 comments0 shares

Sign in to view and post comments.