0
$\begingroup$

Let $X$ be a set. We consider the map \begin{equation*}\Phi : \ \mathcal{P}(X)\rightarrow \{0,1\}^X, \ \ A\mapsto 1_A\end{equation*} that maps a subset $A\subset X$to its characteristc function $1_A$.

I want to show that $\Phi$ is bijective by givung explicitly an inverse map.

Could you give me a hint how we can show that? I don't really have an idea how to find the inverse one.

$$$$

If we want to show the bijectivity by proving that the map is injective and surjective, we do the following, or not?

$\Phi$ is surjective because for every element of in the range, i.e. $0$ and $1$ there is a preimage in $\mathcal{P}(X)$ because either one element is contained in the set $A$ or not.

$\Phi$ is injective because every element of $\Phi (X)$ has an image in $\{0,1\}$.

So, $\Phi$ is bijective.

Is everything correct? Could I improve something?

$\endgroup$
1
$\begingroup$

Your proofs for surjectiveness and injectiveness are off. You should realise that $\{0,1\}^X$ is a set of functions.

$\Phi$ is surjective because for every function $f: X \to \{0,1\}$ (this is what an element of $\{0,1\}^X$ is), there is a subset $A$ such that $\Phi(A) = f$.

$\Phi$ is injective because if $\Phi(A) = \Phi(B)$ (so these are equal functions from $X$ to $\{0,1\}$) we know that $A=B$ (as sets).

Try to show these two statements and you're done too.

And explicit inverse also exists: $\Psi: \{0,1\}^X \to \mathcal{P}(X)$ defined by $\Psi(f) = f^{-1}[\{1\}] = \{x \in X: f(x) = 1\}$ will do, assuming that $1_A: X \to \{0,1\}$ is defined as $1_A(x) = 1$ if $x \in A$ and $0$ otherwise, as is usual).

$\endgroup$
  • $\begingroup$ About the first part: I understood the injectivity. About the surjectivity, do we define as $A$ the subset of $X$ such that $f(x)\in \{0,1\}$ ? $\endgroup$ – Mary Star Sep 30 '18 at 12:11
  • $\begingroup$ You have $f$ in hand so you just define $A$ to be the set on which $f$ is $1$. That’s just the map $\Psi$ I gave. $f$ only assumes the values $0$ and $1$. The points on which it is $1$ is the preimage. $\endgroup$ – Henno Brandsma Sep 30 '18 at 12:13
  • $\begingroup$ Could you explain to me further why the inverse is defined by $\Psi(f) = f^{-1}[\{1\}] = \{x \in X: f(x) = 1\}$ ? $\endgroup$ – Mary Star Sep 30 '18 at 12:16
  • $\begingroup$ I haven't understood the part $f^{-1}[\{1\}]$. $\endgroup$ – Mary Star Sep 30 '18 at 12:28
  • $\begingroup$ You have the function and collect all $x$ where the value is $1$. That set is $A$. The function $1_A$ is then exactly $f$ because it’s $1$ iff x \in A$ iff $f(x)=1$. $\endgroup$ – Henno Brandsma Sep 30 '18 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.