Monday, 16 June 2014

elementary set theory - Let 2A be the set of functions from a set A to 0,1. Prove that there is a bijection between 2A 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:AB 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}...