0
$\begingroup$

enter image description here

I don't quite understand the part where the author writes that $f$ is a one-to-one correspondence between the power set of $A$ and the set of all mappings from $A$ into $\{0, 1\}$. Isn't the function $f$ mapping only $X$ onto $\mathcal{X}_X$?

$\endgroup$
  • 1
    $\begingroup$ $f:\mathcal{P}(A)\to \{0,1\}^A$ defined by $f(X)=\chi_X$ $\endgroup$ – Hamou Aug 12 '14 at 9:59
  • 1
    $\begingroup$ Please avoid the word "help" in the title; it's clear that you'd like help, since you are posting a question. $\endgroup$ – user147263 Aug 12 '14 at 12:46
  • $\begingroup$ It is probably just a matter of notation. It would have been better to write as Hamou suggests in the comment above. Another common way to avoid ambiguity is to write $f: X\mapsto \chi_X$. $\endgroup$ – Andrés E. Caicedo Aug 12 '14 at 19:42
0
$\begingroup$

Injectivity: if $f(X)=f(Y)$ then $\chi_X=\chi_Y$ so it is clear that $X=Y$. Surjectivity: Let $\varphi\in \{0,1\}^A$, $i.e$ $\varphi:A\to \{0,1\}$, put $X=\varphi^{-1}(\{1\})$, we have $\varphi=\chi_X=f(X)$.

$\endgroup$
2
$\begingroup$

That is a mistake then. It should be: the function $f:\mathcal P(X) \to 2^X$ given by $f(X)=\chi _X$ is a bijection.

$\endgroup$
  • $\begingroup$ I wouldn’t call it a mistake. I think the author uses “$f\colon X → χ_X$” for “$f\colon X ↦ χ_X$”. $\endgroup$ – k.stm Aug 12 '14 at 10:12
0
$\begingroup$

Just try to spell it out.

The power set of $A$ contains all the subsets of $A$.

The set of all mappings from $A$ into $\{0, 1\}$ contains $n$-tuples of $1$s and $0$s with $n = |A|$, e.g. for $n=5$ it would contain: $$(0,0,0,0,0)$$ $$(0,0,0,0,1)$$ $$(0,0,0,1,0)$$ $$(0,0,0,1,1)$$ $$...$$ $$(1,1,1,1,1)$$ This is a one-to-one correspondence because you can characterize every subset by labeling the elements of $A$ with $a_i$ ($i=1,...,n$) and mapping it to an $n$-tuple of of $1$s and $0$s such that you put $1$ on the $i$-th place if $a_i$ is an element of that subset and $0$ otherwise.

Visual aid:

enter image description here

$\endgroup$

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.