1

The following are the details of the problem:

Let $M = \{m,a,t,h,f,u,n\}$ and $N = \{h,u,m,a,n\}$. For any $A,B \subseteq M$, $A \sim B \iff A \cap N = B \cap N$ where $\sim$ is an equivalence relation.

The question asks to enumerate unique elements of $P(M) / \sim $, where $P(M)$ is a power set of $M$. I'm not quite sure what this means. What I know is that there are elements in $P(M)$ that can represent other elements under the relation $\sim$. For instance, I can find two sets $A$ and $B$ such that $A \sim B$ and there's a common result.

To illustrate what I mean, let $A = \emptyset$ and $B = \{t\}$. Obviously $A \sim B$ because $ \emptyset \cap N = \{t\} \cap N \implies \emptyset = \emptyset$. So in this case, the common result is $\emptyset$. There are other sets in $P(M)$ that will yield this.

Either way, I'm clueless. I'm not sure what's the implication of this to the original question. I'm not quite sure what should $P(M) / \sim $ mean and what exactly makes the element in that set unique. Can anyone help? Thanks

epsil0ndelta
  • 171

1 Answers1

2

In general if $f:X\to Y$ is a function then the relation $\sim$ on $X$ defined by:$$u\sim v\iff f(u)=f(v)$$is an equivalence relation.

Then $X/\sim$ denotes the set of equivalence classes which is the set of non-empty fibers of $f$.

If moreover $f$ is surjective then we can write:$$X/\sim=\{f^{-1}(\{y\})\mid y\in Y\}$$and the number of equivalence classes is actually the cardinality of $Y$.

We can apply that here for the surjective function $f:\mathcal P(M)\to\mathcal P(N)$ prescribed by $A\mapsto A\cap N$ leading to:$$\mathcal P(M)/\sim=\{f^{-1}(\{E\})\mid E\in\mathcal P(N)\}$$ where: $$f^{-1}(\{E\})=\{A\in\mathcal P(M)\mid A\cap N=E\}$$and $\mathcal P(M)/\sim$ has $|\mathcal P(N)|=2^5$ elements.

For e.g. $E=\{h,u\}$ we find:$$f^{-1}(\{h,u\})=\{A\in\mathcal P(M)\mid A\cap N=\{h,u\}\}=\{\{h,u\},\{h,u,t\},\{h,u,f\},\{h,u,t,f\}\}$$

drhab
  • 151,093