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?


1 Answer 1


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).

  • $\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
    Commented Sep 30, 2018 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$ Commented Sep 30, 2018 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
    Commented Sep 30, 2018 at 12:16
  • $\begingroup$ I haven't understood the part $f^{-1}[\{1\}]$. $\endgroup$
    – Mary Star
    Commented Sep 30, 2018 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$ Commented Sep 30, 2018 at 12:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .