Equal Cardinality

Question

Let X be any set(it could be finite or infinite),and let T={0,1}. Prove that |𝓟(X)| = |F(X,T)| where 𝓟(X) is the power set of X and F(X , T) is the set of all functions from X to T.

So, I have tried to formulate a bijective function between the two sets, in order to prove that they are in one-to-one correspondence, and that means that they have the same cardinality.

Intuitively, this makes sense, because I lets say we have a finite set: X= {1,2,3,4}. So the 𝓟(X)={{1},{2},{3},{4},{1,2},{1,3},{1,4},{1,2,3},{1,2,4},{1,2,3,4},{2,3},{2,4},{3,4},{2,3,4}...}

Essentially, there are 2^n elements in the power set. So there have to be the same amount of functions that map from the set X to T.

Now, for this we define a function that takes all the even numbers and maps them to zero; odd numbers that maps them to one. So every subset of X gives a function that provides this mapping. So every subset of X has a mapping to T.

How do I go about constructing and proving a bijective function between the set X and the set of functions from X to T? My main problem is constructing that function!

Answer 1

You need a bijective map $\phi\colon F(X,T)\to \mathcal P (X)$. So given a function $f\colon X\to T$ (which is characterized by the fact that for $x\in X$ the function value is either $f(x)=1$ or $f(x)=0$), you want to associate it with a subset $\phi(f)$ (which is characterized by the fact that for $x\in X$ we may have either $x\in \phi(f)$ or $x\notin \phi(f)$). Don't you think something suggests itself?

Answer 2

$\phi:F\left(X,T\right)\rightarrow\wp\left(X\right)$ defined by $f\mapsto\left\{ x\in X\mid f\left(x\right)=1\right\} $ is a bijection.

Answer 3

We can take the function F:P(X)->(F(X,T)) with: F(A)=f(x) and f(x) is 1 whenever x is in A as an element of P(X) and f(x) is 0 whenever x is not in A as an element of P(X). Than F is a bijection.