# Two basic set theory questions

Is there a bijection between:

1. The set of all functions that map from $$A$$ to $$P(B)$$

2. The set $$P(A × B)$$

Is there a bijection between:

1. The set of all functions that map from $$A$$ to $$B$$

2. The $$P(A) × P(B)$$

• Welcome to MSE! Can you share what you've tried, and explain what you're having trouble with here?
– user296602
Dec 24 '15 at 0:46
• For the second you can use a finite example to show that sometimes there is no such bijection. Dec 24 '15 at 1:01
• For finite $A,B$ can you compute the cardinality of each set in terms of $a=|A|,b=|B|$? Dec 24 '15 at 1:38

First question: Yes. The set of functions from $A$ to $\mathcal{P}(B)$ has cardinality $|\mathcal{P}(B)|^{|A|} = (2^{|B|})^{|A|} = 2^{|A|\times |B|} = 2^{|A\times B|} = |\mathcal{P}(A\times B)|$.

Second question: No. For example, let $A = \{a\}$ and $B = \{b\}$ be sets with a single element. Then there is exactly one function from $A$ to $B$, but $\mathcal{P}(A)$ and $\mathcal{P}(B)$ each have two elements, so $\mathcal{P}(A)\times \mathcal{P}(B)$ has size $4$.

Added: Let's say you wanted to find an explicit bijection for the first question. Let's work from left to right in the chain of equalities. Suppose we have a function $f\colon A\to \mathcal{P}(B)$. We can identify its codomain $\mathcal{P}(B)$ with $2^B$, the set of functions $B\to 2 = \{0,1\}$ by sending a set $X$ to its characteristic function $1_X$. So $f$ corresponds to a function $g\colon A\to 2^B$ by $g(a) = 1_{f(a)}$. Now a function from $A$ to the set of functions from $B$ to $2$ is the same as a function from $A\times B$ to $2$, by plugging in the arguments one at a time ("currying"). Under this bijection, $g$ corresponds to the function $h(a,b) = (g(a))(b) = 1_{f(a)}(b) = 1$ if $b\in f(a)$ and $0$ otherwise. So $h$ is the characteristic function of the subset of $A\times B$ given by $\{(a,b)\mid b\in f(a)\}$, which is an element of $\mathcal{P}(A\times B)$. All in all, our bijection is given by $$f\mapsto \{(a,b)\mid b\in f(a)\}.$$

This should depend on the cardinality. Finite sets are easy. You just have to show if the sets contain the same number of elements. Now for countable infinite sets:

For the first problem, if A, B are countable infinite, then $A \times B$ is also countable infinite, then both P(B) and P($A \times B$) have the same cardinality as $\mathbb{R}$, which is $\beth_1$. Now we must ask if all functions $\mathbb{N} \to \mathbb{R}$ have the same cardinality as $\mathbb{R}$. This is just the set of all sequences of real numbers, and also has cardinality $\beth_1$. So the two sets have the same cardinality, and a bijection exists

For the second problem, if A, B are countable infinite, the set of all functions from A to B have the same cardinality as $\mathbb{R}$, while $P(A) \times P(B)$ also have the same cardinality as $\mathbb{R}$, therefore, the two sets have the same cardinality, and a bijection must exist.

You can find reference for most of the above statements here https://en.wikipedia.org/wiki/Beth_number

The situation where $A$ and $B$ are larger than countable infinite sets is more difficult, but the basic principle is the same. You find the $\beth$ number of each of the involved sets, and there is a bijection if and only if the two sets have the same cardinality.

• The answer to the second question happens to be yes when $A$ and $B$ are both countably infinite, but the cardinals $|B|^{|A|}$ and $2^{|A|}2^{|B|} = 2^{|A|+|B|}$ are not equal in general! Dec 24 '15 at 4:17