How Many Equivalence Relations Can Be Defined On Set ABC?

A set with three elements, such as {A, B, C}, has 5 equivalence relations. This is because each equivalence relation on a set corresponds to a unique partition of that set. A partition of a set is a division of its elements into non-empty, disjoint subsets. The number of ways to partition a set of nn 𝑛 elements is given by the nn

𝑛

-th Bell number, Bncap B sub n

𝐵𝑛

. For a set with 3 elements, n=3n equals 3

𝑛=3

, so the number of equivalence relations is B3=5cap B sub 3 equals 5

𝐵3=5

.

Detailed explanation

An equivalence relation is a binary relation on a set that satisfies three key properties for all elements xx

𝑥

, yy

𝑦

, and zz

𝑧

in the set:

• **Reflexive:**xx

  𝑥

  is related to itself (x∼xx tilde x

  𝑥∼𝑥

  ).

• Symmetric: If xx

  𝑥

  is related to yy

  𝑦

  , then yy

  𝑦

  is related to xx

  𝑥

  (if x∼yx tilde y

  𝑥∼𝑦

  , then y∼xy tilde x

  𝑦∼𝑥

  ).

• Transitive: If xx

  𝑥

  is related to yy

  𝑦

  and yy

  𝑦

  is related to zz

  𝑧

  , then xx

  𝑥

  is related to zz

  𝑧

  (if x∼yx tilde y

  𝑥∼𝑦

  and y∼zy tilde z

  𝑦∼𝑧

  , then x∼zx tilde z

  𝑥∼𝑧

  ).

The fundamental theorem of equivalence relations states that there is a one-to-one correspondence between the set of all equivalence relations on a set and the set of all partitions of that same set. Therefore, to find the number of equivalence relations, one simply needs to count the number of ways to partition the set.

Partitions of the set {A, B, C}

The five partitions for the set {A, B, C} are as follows:

1. All elements in one subset

• Partition: {{A, B, C}}
• Corresponding Equivalence Relation: The universal relation where every element is related to every other element.

  • R1={(A,A),(B,B),(C,C),(A,B),(B,A),(A,C),(C,A),(B,C),(C,B)}cap R sub 1 equals the set open paren cap A comma cap A close paren comma open paren cap B comma cap B close paren comma open paren cap C comma cap C close paren comma open paren cap A comma cap B close paren comma open paren cap B comma cap A close paren comma open paren cap A comma cap C close paren comma open paren cap C comma cap A close paren comma open paren cap B comma cap C close paren comma open paren cap C comma cap B close paren end-set

    𝑅1={(𝐴,𝐴),(𝐵,𝐵),(𝐶,𝐶),(𝐴,𝐵),(𝐵,𝐴),(𝐴,𝐶),(𝐶,𝐴),(𝐵,𝐶),(𝐶,𝐵)}

2. All elements in their own subsets

• Partition: {{A}, {B}, {C}}
• Corresponding Equivalence Relation: The identity relation, where each element is only related to itself.

  • R2={(A,A),(B,B),(C,C)}cap R sub 2 equals the set open paren cap A comma cap A close paren comma open paren cap B comma cap B close paren comma open paren cap C comma cap C close paren end-set

    𝑅2={(𝐴,𝐴),(𝐵,𝐵),(𝐶,𝐶)}

**3. Two elements in one subset and one element in its own subset (3 ways)**There are three ways to choose which two elements are grouped together.

• Partition: {{A, B}, {C}}
• Corresponding Equivalence Relation:

  • R3={(A,A),(B,B),(C,C),(A,B),(B,A)}cap R sub 3 equals the set open paren cap A comma cap A close paren comma open paren cap B comma cap B close paren comma open paren cap C comma cap C close paren comma open paren cap A comma cap B close paren comma open paren cap B comma cap A close paren end-set

    𝑅3={(𝐴,𝐴),(𝐵,𝐵),(𝐶,𝐶),(𝐴,𝐵),(𝐵,𝐴)}

• Partition: {{A, C}, {B}}
• Corresponding Equivalence Relation:

  • R4={(A,A),(B,B),(C,C),(A,C),(C,A)}cap R sub 4 equals the set open paren cap A comma cap A close paren comma open paren cap B comma cap B close paren comma open paren cap C comma cap C close paren comma open paren cap A comma cap C close paren comma open paren cap C comma cap A close paren end-set

    𝑅4={(𝐴,𝐴),(𝐵,𝐵),(𝐶,𝐶),(𝐴,𝐶),(𝐶,𝐴)}

• Partition: {{B, C}, {A}}
• Corresponding Equivalence Relation:

  • R5={(A,A),(B,B),(C,C),(B,C),(C,B)}cap R sub 5 equals the set open paren cap A comma cap A close paren comma open paren cap B comma cap B close paren comma open paren cap C comma cap C close paren comma open paren cap B comma cap C close paren comma open paren cap C comma cap B close paren end-set

    𝑅5={(𝐴,𝐴),(𝐵,𝐵),(𝐶,𝐶),(𝐵,𝐶),(𝐶,𝐵)}

Connecting to combinatorics: Bell numbers

The number of equivalence relations on a set with nn

𝑛

elements is given by the nn

𝑛

-th Bell number, denoted as Bncap B sub n

𝐵𝑛

.

• B0=1cap B sub 0 equals 1

  𝐵0=1

• B1=1cap B sub 1 equals 1

  𝐵1=1

• B2=2cap B sub 2 equals 2

  𝐵2=2

• B3=5cap B sub 3 equals 5

  𝐵3=5

• B4=15cap B sub 4 equals 15

  𝐵4=15

• ...and so on.

For the set {A, B, C}, the number of elements is 3, so the number of equivalence relations is the third Bell number, B3=5cap B sub 3 equals 5

𝐵3=5

. The Bell numbers can be calculated using a recurrence relation or the Bell triangle. They are the sum of the Stirling numbers of the second kind, which count the number of partitions of a set of nn

𝑛

elements into exactly kk

𝑘

non-empty subsets.

For n=3n equals 3

𝑛=3

, the Bell number is the sum of the Stirling numbers S(3,k)cap S open paren 3 comma k close paren

𝑆(3,𝑘)

for k=1,2,3k equals 1 comma 2 comma 3

𝑘=1,2,3

:

• S(3,1)cap S open paren 3 comma 1 close paren

  𝑆(3,1)

  (partitions into 1 part) = 1: {{A, B, C}}

• S(3,2)cap S open paren 3 comma 2 close paren

  𝑆(3,2)

  (partitions into 2 parts) = 3: {{A, B}, {C}}, {{A, C}, {B}}, {{B, C}, {A}}

• S(3,3)cap S open paren 3 comma 3 close paren

  𝑆(3,3)

  (partitions into 3 parts) = 1: {{A}, {B}, {C}}

• B3=S(3,1)+S(3,2)+S(3,3)=1+3+1=5cap B sub 3 equals cap S open paren 3 comma 1 close paren plus cap S open paren 3 comma 2 close paren plus cap S open paren 3 comma 3 close paren equals 1 plus 3 plus 1 equals 5

  𝐵3=𝑆(3,1)+𝑆(3,2)+𝑆(3,3)=1+3+1=5

  .