Jayvion Caldwell

2022-07-17

Let A be a finite set of size k and R a relation on the power set P(A) defined by $R=\left\{\left(A,B\right):|A|=|B|\right\}$
1. Show that A is an equivalence relation.
2. Let $a\in A$. What is the size of the equivalence class of {a}?
3. Let a,b be two different elements of A. What is the size of the equivalence class of {a,b}?

grocbyntza

Expert

Step 1
There are three criteria that must be followed in order to prove R is an equivalence relation,
1. Reflexive
2. Symmetric
3. Transitive
Step 2
To get you started, with generic sets $B,C,D\in \mathcal{P}\left(A\right)$, see that we always have $|B|=|B|$
so R is reflexive. This would mean $\left(B,B\right)\in R$ for some $B\subseteq A$
To show it's symmetric, it requires you to show that if $|B|=|C|$, then $|C|=|B|$.
To show it's transitive, it requires you to show if $|B|=|C|$, and $|C|=|D|$, then $|B|=|D|$

Nash Frank

Expert

Step 1
Informally, under this equivalence relation two subsets are equivalent when they have the same size.
Thus, the equivalence class of {a} consists of all subsets of A with cardinality/size equal to one.
Thus the size of this equivalence class is $k=|A|$.
Step 2
The equivalence class of {a,b} consists of all two element subsets of A. Thus the size of this equivalence class is $\left(\genfrac{}{}{0}{}{k}{2}\right)=\frac{k\left(k-1\right)}{2}$

Do you have a similar question?