Question

Let A = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10} and B = {1; 2; 3; 4}. Let R be the relation on P (A)
defined by:
For any X,Y element in P(A), XRY if and only if X-B = Y-B.
How many equivalence classes are there? Explain

Answer 1

Answer on Question #79754 - Math - Discrete Mathematics

August 13, 2018

Question. Let $A=\{1;2;3;4;5;6;7;8;9;10\}$ and $B=\{1;2;3;4\}$. Let $R$ be the relation on $\mathcal{P}(A)$ defined by:

For any $X,Y$ element in $\mathcal{P}(A)$, $XRY$ if and only if $X-B=Y-B$. How many equivalence classes are there? Explain.

Answer. Define a function $f$ on $\mathcal{P}(A)$ by $f(X)=X-B$. Then $XRY$ if and only if $f(X)=f(Y)$.

We will show that there is a one-to-one correspondence from $R$-equivalence classes to the range of $f$ denoted by $\mathrm{range}(f)$. For every equivalence class with a representative $X$, let $f(X)$ correspond to this equivalence class. As every equivalence class has at least one representative, at least one element of $\mathrm{range}(f)$ corresponds to every equivalence class. If $X$ and $Y$ are representatives of the same equivalence class, then $XRY$, $f(X)=f(Y)$, hence at most one element of $\mathrm{range}(f)$ corresponds to this equivalence class.

The range of $f$ is $\mathcal{P}(A-B)$, as we will show.

- Assume that $X\subseteq A-B$. $X-B\subseteq X$. Every $x\in X$ does not belong to $B$ (because $X\subseteq A-B$), so $x\in X-B$. Hence $f(X)=X-B=X$, and $X\in\mathrm{range}(f)$.

- Assume that $X\in\mathrm{range}(f)$. Then there is $Y\subseteq A$ such that $f(Y)=X$. Hence $X=Y-B$. Every element of $X$ belongs to $Y$, hence it belongs to $A$, and does not belong to $B$, so $X\subseteq A-B$.

$A-B=\{5;6;7;8;9;10\}$. The set $A-B$ has exactly 6 members. It follows that $\mathcal{P}(A-B)$ has exactly $2^{6}=64$ elements. Therefore, there are exactly 64 $R$-equivalence classes.

Answer provided by https://www.AssignmentExpert.com