I realize that there's already this thread:
I thought maybe there's a shorter proof?
Let f:A→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