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$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ $f:\mathcal{P}(A)\to \{0,1\}^A$ defined by $f(X)=\chi_X$ $\endgroup$– HamouAug 12, 2014 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$– user147263Aug 12, 2014 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. CaicedoAug 12, 2014 at 19:42
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered Aug 12, 2014 at 9:52
-
$\begingroup$ I wouldn’t call it a mistake. I think the author uses “$f\colon X → χ_X$” for “$f\colon X ↦ χ_X$”. $\endgroup$– k.stmAug 12, 2014 at 10:12
$\begingroup$
$\endgroup$
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)$.
$\begingroup$
$\endgroup$
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:
