# Help on proving equal cardinalities

• Nov 18th 2011, 04:30 AM
gordo151091
Help on proving equal cardinalities
Hello, I am trying to proof the following claim.
$\displaystyle \left| P(A \times B) \right| = \left| P(B)^A \right|$

Where $\displaystyle P$ is the power set and $\displaystyle P(B)^A := \left \{ \left f: ( f: A \to P(B) \right ) \right \}$.

I am trying to construct a bijection or two injections and cantors theorem to proof they have the same cardinality, but I seem to be getting nowhere. Can anyone help me?
• Nov 18th 2011, 04:58 AM
Opalg
Re: Help on proving equal cardinalities
Quote:

Originally Posted by gordo151091
Hello, I am trying to proof the following claim.
$\displaystyle \left| P(A \times B) \right| = \left| P(B)^A \right|$

Where $\displaystyle P$ is the power set and $\displaystyle P(B)^A := \left \{ \left f: ( f: A \to P(B) \right ) \right \}$.

I am trying to construct a bijection or two injections and cantors theorem to proof they have the same cardinality, but I seem to be getting nowhere. Can anyone help me?

I would define a bijection $\displaystyle \psi : P(A\times B) \to P(B)^A$ by $\displaystyle \psi(S)(a) = \{b\in B:(a,b)\in S\}$, for $\displaystyle S\in P(A\times B)$ and $\displaystyle a\in A.$

The inverse map $\displaystyle \phi$ would be given by $\displaystyle \phi(f) = \{(a,b):b\in f(a)\}$, for $\displaystyle f\in P(B)^A.$

Intuitively, a subset of the product space AxB can be identified with the set of "vertical slices" given by fixed elements of A, as in the picture.
• Nov 18th 2011, 07:11 AM
gordo151091
Re: Help on proving equal cardinalities
So the $\displaystyle b \in B$ in the red line from picture would be the resulting set by the function $\displaystyle \psi$ for a particular $\displaystyle S$ and $\displaystyle a$
• Nov 18th 2011, 07:22 AM
Opalg
Re: Help on proving equal cardinalities
Quote:

Originally Posted by gordo151091
So the $\displaystyle b \in B$ in the red line from picture would be the resulting set by the function $\displaystyle \psi$ for a particular $\displaystyle S$ and $\displaystyle a$

Yes. The blobby area in the picture is supposed to represent a subset S of AxB, and $\displaystyle \psi(S)$ is the function whose value at a point $\displaystyle a$ is the set of second coordinates of all points in S whose first coordinate is $\displaystyle a.$