Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

I want to prove that $\{f|f:A\rightarrow\{0,1\}\} \approx P(A)$ where P(A) is the power set of A.

I think the idea is to show that there is a monotonic function from the set A to its power set. But I cannot go any further.

share|cite|improve this question

marked as duplicate by Asaf Karagila, Micah, Stefan Hansen, Norbert, Clive Newstead Feb 24 '13 at 16:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

I am fairly certain there are plenty of other answers posted on the site to this question, but I am too busy to find those. – Asaf Karagila Feb 24 '13 at 15:43
up vote 2 down vote accepted

Other answers have already said essentially this, but perhaps this phrasing will make it clearer:

On the left side, you have the set of all functions from A to {0,1}. So this is the set of functions that take input any element of A, and spit out either 0 or 1 for each.

On the right side, you have the power set of A. This is the set of all subsets of A. When specifiying a subset of A, we go through each of the elements and say whether we include it, or exclude it.

The functions on the left are basically doing the same thing - they are picking which elements of $A$ to include and exclude, say by outputting 1 for include, 0 for exclude. So we have a natural correspondence between the functions on the left side, and the sets on the right side.

Zev's hint was basically saying that a function from A to {0,1} is completely known as long as you know which elements from A get sent to 0 (that is, the elements of $f^{-1}(0)$), because if you know which ones get sent to 0, all the other ones must be sent to 1.

Let us do this: Let $f$ be a function from A to {0,1}. We associate a subset of A to this function: The elements in our subset, are the elements that are sent to 0 by f (i.e, $f^{-1}(0)$). This association is injective because if two functions from A to {0,1} are associated to the same subset of A, meaning they agree on what they send to 0, then by Zev's hint they also agree on what to send to 1, i.e they are the same. It is surjective because any subset $X\subseteq A$ can be attained from this association from some function A to {0,1} - namely the function that sends things in $X$ to 0, and the other things to 1.

share|cite|improve this answer
Now I've got it. Could you define an injective and surjective function for it? Do you recommend the same function that @Zev suggested as well? – Gigili Feb 24 '13 at 13:16
@Gigili Please see my edit. I hope this clears things up for you. – Ragib Zaman Feb 24 '13 at 14:51
As clear as day, thank you for your edit. – Gigili Feb 24 '13 at 17:16

Hint: A function $f:A\to\{0,1\}$ is uniquely determined by $f^{-1}(0)$.

share|cite|improve this answer
I figured $f$ is the characteristic function of $P(A)$ but I cannot relate it to what you said, could you please elaborate? – Gigili Feb 24 '13 at 12:38
I don't understand what you mean by "$f$ is the characteristic function of $P(A)$". What I'm saying is that, to each element of the set $\{f\mid f:A\to\{0,1\}\}$, one can associate to it a subset of $A$, namely $f^{-1}(0)$, and that this is unique. Do you see how this is relevant? – Zev Chonoles Feb 24 '13 at 12:40
I'm sorry but I don't seem to get how $f^{-1}(0)$ is obtained! – Gigili Feb 24 '13 at 12:53
This is the preimage, a.k.a. inverse image, of the element $0\in\{0,1\}$. Given sets $X$ and $Y$, an element $y\in Y$, and a function $g:X\to Y$, we say that $$g^{-1}(y):=\{x\in X\mid g(x)=y\}$$ is the preimage of $y$ under the function $g$. It is a subset of $X$. – Zev Chonoles Feb 24 '13 at 12:55
Thank you for your explanation. – Gigili Feb 24 '13 at 17:11

You can associate $\{x\in A|f(x)=1\}$ to every function of your set, this gives you a bijection to the power set $\mathcal{P}(A)$. Since this is homework, I will not give you further hints about how to prove this.

share|cite|improve this answer

Every $f: A\rightarrow \{0, 1\}$ always makes a subset $B$ of $A$ such that $f(B)=0$ and $f(A\setminus B)=1$. In fact, $f$ is decided by the subset $B$ of $A$. So the number of the subsets of $A$ decided the cardinality of $\{f|f: A \rightarrow \{0,1\}\}$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.