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 Answer 1

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$
11
  • $\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 .