MHB Is Φ a Bijective Map from Power Set to Characteristic Functions?

[mathmari]

Hey!

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 in the following two ways that $\Phi$ is bijective:

1. verify directly that $\Phi$ is injective and surjective
2. give explicitly an inverse map

Could you give me a hint how we can show that? I don't really have an idea. (Wondering)

 

[I like Serena]

Hey!

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 in the following two ways that $\Phi$ is bijective:

1. verify directly that $\Phi$ is injective and surjective
2. give explicitly an inverse map

Could you give me a hint how we can show that? I don't really have an idea. (Wondering)

Hey mathmari!

Let's look at an example.
Suppose $X=\{1,2,3\}$, can we find the answers then? (Wondering)

 

[mathmari]

Let's look at an example.
Suppose $X=\{1,2,3\}$, can we find the answers then? (Wondering)

Using the first way:

$\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 so far?
Using the second way:

Can we determine the inverse? (Wondering)

 

[Olinguito]

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

You probably need to say a bit more. Start by considering an element of $\{0,1\}^X$, namely a function $f:X\to\{0,1\}$. Can you find an element of $\mathcal P(X)$, namely a subset $A$ of $X$, such that $\Phi(A)=f$?

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

No, not that way. Consider two elements of $\mathcal P(X)$, namely subsets $A$ and $B$ of $X$. Suppose $\Phi(A)=\Phi(B)$, i.e. their characteristic functions are equal, $1_A=1_B$. Can you show from this that the subsets must be equal, $A=B$? To do so, let $x\in A$ and show that $x\in B$, which will prove that $A\subseteq B$. The reverse inclusion will follow by symmetry.

Can we determine the inverse?

Here’s a hint: the method used in proving surjectivity can come in handy here. It will help you find a function $\Psi:\{0,1\}^X\to\mathcal P(X)$ such that $\Psi\circ\Phi=\Phi\circ\Psi=I_{\mathcal P(X)}$ (the identity map on the power set of $X$). (Happy)

 

[mathmari]

You probably need to say a bit more. Start by considering an element of $\{0,1\}^X$, namely a function $f:X\to\{0,1\}$. Can you find an element of $\mathcal P(X)$, namely a subset $A$ of $X$, such that $\Phi(A)=f$?

We set $A$ the subset of $X$ such that $f(x)=1$ for $x\in X$, i.e. $A=\{ x\in X\mid f(x)=1$, or not? (Wondering)

No, not that way. Consider two elements of $\mathcal P(X)$, namely subsets $A$ and $B$ of $X$. Suppose $\Phi(A)=\Phi(B)$, i.e. their characteristic functions are equal, $1_A=1_B$. Can you show from this that the subsets must be equal, $A=B$? To do so, let $x\in A$ and show that $x\in B$, which will prove that $A\subseteq B$. The reverse inclusion will follow by symmetry.

I got it! (Smile)

Here’s a hint: the method used in proving surjectivity can come in handy here. It will help you find a function $\Psi:\{0,1\}^X\to\mathcal P(X)$ such that $\Psi\circ\Phi=\Phi\circ\Psi=I_{\mathcal P(X)}$ (the identity map on the power set of $X$). (Happy)

We have that $\Phi (A)=f$ then the inverse is of the form $\Psi (f)=A$, right? But how is this defined? (Wondering)

 

[Olinguito]

We set $A$ the subset of $X$ such that $f(x)=1$ for $x\in X$, i.e. $A=\{ x\in X\mid f(x)=1$, or not? (Wondering)

$A$ should be the subset of $X$ such that for all $x\in X$, $x\in A$ if and only if $f(x)=1$. Can you see what happens next?

I got it! (Smile)

Great! (Happy)

We have that $\Phi (A)=f$ then the inverse is of the form $\Psi (f)=A$, right? But how is this defined? (Wondering)

Given a function $f:X\to\{0,1\}$, let $A\subseteq X$ be as defined above in the surjectivity proof, and set $\Psi(f)=A$. Now work out $\Psi\circ\Phi$ and $\Phi\circ\Psi$.

 

[mathmari]

$A$ should be the subset of $X$ such that for all $x\in X$, $x\in A$ if and only if $f(x)=1$. Can you see what happens next?

With this $A$ we get that $1_A=f$, right? (Wondering)

Given a function $f:X\to\{0,1\}$, let $A\subseteq X$ be as defined above in the surjectivity proof, and set $\Psi(f)=A$. Now work out $\Psi\circ\Phi$ and $\Phi\circ\Psi$.

We have that $\Phi (A)=1_A$. Using the definition of $A$ as aboce we have that $\Phi (A)=f$ and then $\Psi (f)=A$ is the inverse which maps elements from $\{0,1\}^X$ to $\mathcal{P}(X)$.

Is everything correct? (Wondering)

 

[Olinguito]

That’s basically it. (Nod)

This exercise proves the following. While every characteristic function is a function from $X$ to $\{0,1\}$ (by definition), the converse is also true: every function from $X$ to $\{0,1\}$ is a characteristic fuction.