1

Let $f:A\to B$ be bijective. Show that $g:P(A)\to P(B)$, defined as $$g(X)=\{f(x)|x\in X\},X\subseteq A$$ is also bijective.

Let's first try to show that $g$ is injective. So we need to show that if $g(X_1)=g(X_2)$, then $X_1=X_2$. $$g\left(X_1\right)=g\left(X_2\right)\land X_1\subseteq A\land X_2\subseteq A\\X_1,X_2\subseteq A\land \{f(x)|x\in X_1\}=\{f(x)|x\in X_2\}\\X_1,X_2\subseteq A\land\forall x\left(x\in\{f(x)|x\in X_1\}\iff x\in\{f(x)|x\in X_2\}\right)$$ I have basically used the fact that $A=B\iff \forall x(x\in A \iff x\in B)$, as we have $g(X_1)=g(X_2)$ and using the definition of $g$ gives what I wrote. I don't know how to show from here that $X_1=X_2$ which is enough to say that $g$ is injective. Where am I supposed to use that $f$ is bijective?

Any help would be appreciated.

Math Student
  • 2,656

1 Answers1

2

We first want to show $X_1 \subset X_2$. So, let $x_1 \in X_1$. Then $f(x_1) \in \{f(x) \mid x \in X_1\} = g(X_1)$. We know $g(X_1)=g(X_2)$. It then follows that $$f(x_1) \in g(X_2) = \{f(x) \mid x \in X_2\}$$ That means that there exists a $x_2 \in X_2$ such that $$f(x_1)=f(x_2)$$ But since $f$ is a bijection we can look at the inverse of both sides giving us: $$x_1=x_2$$ and since $x_2 \in X_2$ we have $$ x_1 = x_2 \in X_2$$ So $x_1 \in X_2$ which shows that $X_1 \subset X_2$. The other inclusion follows analogously.

Flynn Fehre
  • 484
  • Thank you! Do we really need that $f$ is surjective as well though? – Math Student Nov 11 '23 at 20:35
  • @MathStudent In this proof we only need injectivity. However, that proof only gives the injectivity of $g$. But you also want to show the surjectivity of $g$ where we will need the surjectivity of $f$. – Flynn Fehre Nov 11 '23 at 20:49
  • Yep, I reached to that conclusion as well. May you give me a hint for the surjectivity? We start with $Y\in P(B)$, right? And now how do we find a set $X\in P(A)$ s.t. $g(X)=Y$? That's the idea, right? – Math Student Nov 11 '23 at 20:51
  • @MathStudent Yes exactly. As a hint look at the set ${x \in A \mid f(x) \in Y}$. – Flynn Fehre Nov 11 '23 at 21:00
  • Ugh, sorry, but this hint isn't enough for me. Can you clarify it a bit more? – Math Student Nov 11 '23 at 21:05
  • @MathStudent $$g({x\in A,|,f(x)\in Y})={f(x),|,f(x)\in Y}=Y$$where the last equality follows from $f$ being surjective – Lorago Nov 11 '23 at 21:10
  • @Lorago, thank you for your answer, but I think the problem is I don't see where this set comes from ${x\in A | f(x)\in Y}$. What's the intuition behind it? How do I come up with it? – Math Student Nov 11 '23 at 21:13
  • @Lorago, and also why when we apply the function g to that set we get ${f(x)|f(x)\in Y}$? That's not clear for me as well. Thank you and sorry for the multiple questions, but I'm really trying to understand what's going on. – Math Student Nov 11 '23 at 21:16
  • @MathStudent Applying $g$ to a set is the same as applying $f$ to every element in the set. The set we consider is simply the set of all points which map to $Y$ under $f$, meaning when we apply $g$ and apply $f$ to every element, all the points get mapped to $Y$ – Lorago Nov 11 '23 at 21:18