-1

I have a homework question that plays off my las question about the characteristic function $\chi_A(x)$. It is:

Prove that there is a function $f$ that gives a one-to-one correspondence between $\mathcal{P}(X)$ and $2^X$.

Here the power set $\mathcal{P}(X)=\{A|A\subseteq{X}\}$ and $2^X$ is the set of all functions that map elements into the set $\{0,1\}$ Now i know that $|\mathcal{P}(X)|=2^{|X|}$, but the hint in the example mentions this:

"Now let us define a function $f$ on $\mathcal{P}(X)$ into $2^X$ by taking as the image a subset $A$ of $X$ the characteristic function of $A$," so then this mapping looks like this

$$f:\mathcal{P}(X)\rightarrow{2^X}$$ $$f(A)=\chi_A{x}$$

From here I must show injectivity and surjectivity. So $$f(A)=f(B)\Rightarrow{A=B}$$

So by the definition of the characteristic function we can show that injectivity holds since if $$x\in{A}, \chi_A(x)=1=\chi_B(x) \text{ if } x\in{B}$$ and $$x\in{X-A}, \chi_A(x)=0=\chi_B(x) \text{ if } x\in{X-B}$$ But how do we create a surjectivity argument?

Iceman
  • 1,783

2 Answers2

8

Hint: Take an element $h$ of $2^X.$ You need to find some $A\subseteq X$ such that $\chi_A=h.$ There's only one way to do it.

Cameron Buie
  • 102,994
  • there is only one way because of the way $\chi_A(x)$ is defined? By saying there is only one way to do it, I don't see the way...i'm confused – Iceman Sep 17 '13 at 14:08
  • Which $x$ need to be in $A$ for $h=\chi_A$? Which $x$ need to not be in $A$? (Since $h$ only takes on two possible values, there isn't much left to do.) – Cameron Buie Sep 17 '13 at 14:10
  • got it, you can basically go from ${0,1}$ and work backwards. I've done surjectivity arguments, but outside these ideas. – Iceman Sep 17 '13 at 14:16
  • thanks guys! This was easier than I expected, but helped a lot... – Iceman Sep 17 '13 at 14:23
5

Hint: $A = \{x \in X \colon \chi_A(x)=1\}$.

njguliyev
  • 14,473
  • 1
  • 26
  • 43
  • 1
    so for all $h\in{2^X},$ there exists an $A\in{\mathcal{P}(X)}$ such that $h(A)=\chi_A(x)$? – Iceman Sep 17 '13 at 14:14
  • Yes. ${}{}{}{}$ – njguliyev Sep 17 '13 at 14:15
  • @Iceman: Close, but not quite. Rather, there exists an $A\in\mathcal{P}(X)$ such that $h(x)=\chi_A(x)$ for all $x\in X$. – Cameron Buie Sep 17 '13 at 14:37
  • 1
    right...i suppose that condition is of utmost importance, since you can't have a function without it! :) My problem is i'm trying to visualize this thing as opposed to just using the rules for proving one-to-one correspondence. Like I'm trying to visualize all the functions in $2^X$ instead of just letting the logic work through. – Iceman Sep 17 '13 at 14:51