# Inj, surj, equivalence relation. Is this exercise correctly resolved?

This is the problem that I've tried to solve. Let me know if I was right. It was written originally in italian, but I don't know how translate some mathematical words in english, so sorry in advice.

Given $S = \{1, 2, 3\}$, and the following function $$f:X\in\mathbb{P}(S)\longmapsto X\backslash\{2\} \in \mathbb{P}(S)$$

1. Talk about injectivity and surjectivity
2. Given the equivalence relation $\mathcal{R}_f$ induced by $f$ defined as following: $$X \mathcal{R}_f Y \Longleftrightarrow f(X)=f(Y)$$ describe every equivalence class in $\mathcal{R}_f$.
3. Define in $\mathbb{P}(S)\backslash\{\varnothing\}$ the following order relation $$X \quad \Sigma \quad Y \Leftrightarrow X =Y \quad \text{or}\quad \max(X)<\max(Y).$$ Determine in $\{\mathbb{P}(S)\backslash\{\varnothing\}, \Sigma\}$ min, max, maximal and minimal element.
4. Is $\{\mathbb{P}(S)\backslash\{\varnothing\}, \Sigma\}$ a totally ordered set?

This is my solution:

1. Not injective. $$\{1,3\}\neq\{1,2,3\}\quad \text{but} \quad f(\{1,3\})=f(\{1,2,3\})$$ Not surjective. (e.g. $\{1,2\}\in B$ have not corresponding element in $A$ )
2. Four equivalence classes: $$[\{1\}]_{\mathcal{R}_f}=\{\{1\},\{1,2\}\}$$ $$[\{3\}]_{\mathcal{R}_f}=\{\{3\},\{2,3\}\}$$ $$[\{\varnothing\}]_{\mathcal{R}_f}=\{\{2\},\{\varnothing\}\}$$ $$[\{1,3\}]_{\mathcal{R}_f}=\{\{1,3\},\{1,2,3\}\}$$

Am I right? How can I start to resolve 3rd and 4th point?

Best regard

• On $4$: If I understand the problem correctly, let $X=\{1,3\}$ and $Y=\{2,3\}$. Then neither $X\:\Sigma\:Y$ nor $Y\:\Sigma\:X$ is true. So the order cannot be total. – André Nicolas Jan 10 '12 at 10:09
• For 3, just write down all the elements of $\mathbb{P}(S)$ and draw a digraph with an arrow from $X$ to $Y$ exactly when $X\Sigma Y$. This should make the max, min, maximal, minimal elements obvious. – Neal Jan 10 '12 at 11:29
• @Neal, I have $\mathbb{P}(S)$ that looks like $\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\},\{\varnothing\},\}$. Final order should be something like {1}--{2}--{3}--{1,2}--{1,2,3}. Then {1} min, {1,2,3} max and no minimal or maximal element, is that true? – BAD_SEED Jan 10 '12 at 14:51

For 3, just write down all the elements of $\Bbb P(S)$ and draw a digraph with an arrow from $X$ to $Y$ exactly when $X\Sigma Y$. This should make the max, min, maximal, minimal elements obvious.
On 4: If I understand the problem correctly, let $X = \{1,3\}$ and $Y=\{2,3\}$. then neither $X\;\Sigma\;Y$ nor $Y\;\Sigma\;X$ is true. So the order cannot be total.