I realize that there's already this thread:
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