2
$\begingroup$

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)$

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

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)\}.$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Dec 24 '15 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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