Tuesday, February 12, 2013

The power set of X

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Suppose X and Y are sets. What is YX?
YX is the set of all functions from X to Y. From the last post, we see that if X has n elements and Y has m elements, then YX has mn elements.

What is 2X?
If we write like that, we identify 2 with a set with two elements, in particular we can consider 2={0,1}. Therefore 2X is simply a set of functions that for each x∈X, f(x) takes up values as 0 or 1.

How do we describe a function in 2X?
Since f(x) can only have two values, we can describe the function f using the preimage of 0, i.e. f-1(0)={x∈X   :   f(x)=0}. In other words, each function in 2X corresponds to exactly one subset of X.

2X is sometimes used to denote the power set of X, right?
A power set of X, usually denoted by P(X), is the set of all subsets of X. Because there exists a correspondence between the functions in 2X and the subsets in P(X), so we sometimes really consider them identical.
For example, if X={a,b,c}, then P(X)={∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} and the eight functions in 2X are
f(a)=f(b)=f(c)=1;
f(a)=0, f(b)=f(c)=1;
f(b)=0, f(a)=f(c)=1;
f(c)=0, f(a)=f(b)=1;
f(a)=f(b)=0, f(c)=1;
f(a)=f(c)=0, f(b)=1;
f(b)=f(c)=0, f(a)=1;
f(a)=f(b)=f(c)=0.