Monday, 16 June 2014

elementary set theory - Let $2^A$ be the set of functions from a set $A$ to ${0, 1}$. Prove that there is a bijection between $2^A$ and the power set of $A$



I realize that there's already this thread:



Prove that there is a bijection between the set of all subsets of $X$, $P(X)$, and the set of functions from $X$ to $\{0,1\}$.



I thought maybe there's a shorter proof?





Let $f : A \to B$ be any function. Then the graph $Γ_f := \{(a, b) \in A \times B | b = f(a)\} \subseteq A \times B$ of $f$ is isomorphic to $A$.




Let $f: 2^A \to P(A)$ and $g: P(A) \to 2^A$. Then $2^A$ is bijective to $Γ_f \subseteq 2^A \times P(A)$ and $Γ_g \subseteq P(A) \times 2^A$ is bijective to $P(A).$ Since $Γ_g$ and $Γ_f$ are bijective and bijection is an equivalence realtion, $2^A$ is bijective to $P(A).$



Is it possible to argue like the above? Thanks.



edit:



Let $A = \{0, 1\}$. Subsets of $A$ can either contain an element of $A$ or not. Set up a bijection like so:




$\{0, 1\} \leftrightarrow (yes, yes)$



$\{0\} \leftrightarrow (yes, no)$



$\{1\} \leftrightarrow (no, yes)$



$\{\} \leftrightarrow (yes, no)$



If an element in the subset of $A$, then it corresponds to yes in the corresponding list. Now we can simply count the number of lists. Consider the set $\{yes, no\}$. There are $2$ choices for $yes$ and $2$ choices for $no$. So that there are $2^2$ lists of the form $(yes, no)$.



Answer



Here's a bijection $2^A \to \mathscr{P}(A)$:
$$
f \mapsto \{a \in A \mid f(a) = 1\}
$$
You can either (easily) show that this is 1-1 and onto, or show that the following function $\mathscr{P}(A) \to 2^A$ is its inverse:
$$
X \mapsto c_X
$$
where $c_X$ is the characteristic function of a set $X \subseteq A$, defined by: $c_X(a) = 1$ if $a \in X$, and $c_X(a) = 0$ if $a \notin X$.



No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...