Jayvion Caldwell

Answered

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=\{(A,B):|A|=|B|\}$

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}?

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}?

Answer & Explanation

grocbyntza

Expert

2022-07-18Added 25 answers

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}(A)$, see that we always have $|B|=|B|$

so R is reflexive. This would mean $(B,B)\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|$

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}(A)$, see that we always have $|B|=|B|$

so R is reflexive. This would mean $(B,B)\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

2022-07-19Added 10 answers

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 $(}\genfrac{}{}{0ex}{}{k}{2}{\textstyle )}=\frac{k(k-1)}{2$

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 $(}\genfrac{}{}{0ex}{}{k}{2}{\textstyle )}=\frac{k(k-1)}{2$

Most Popular Questions