Set of All Mappings of Cartesian Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $R$, $S$, and $T$ be sets.


Then:

$R^{S \times T} \sim \paren {R^S}^T$


Proof

Define the mapping $F: \paren {R^S}^T \to R^{S \times T}$ as follows:

$\map {\map F f} {x, y} = \map {\paren {\map f x} } y$ for all $x \in S , y \in T$.


Suppose $\map F {f_1} = \map F {f_2}$.

Then $\map {\paren {\map {f_1} x} } y = \map {\paren {\map {f_2} x} } y$ for all $x \in S , y \in T$ by the definition of $F$.

Therefore, $\map {f_1} x = \map {f_2} x$ and $f_1 = f_2$ by Equality of Mappings.

It follows that $F$ is an injection.


Take any $g \in R^{S \times T}$.

Define a function $f$ as $\map {\paren {\map f x} } y = \map g {x, y}$.


It follows that:

\(\ds \map {\map F f} {x, y}\) \(=\) \(\ds \map {\paren {\map f x} } y\) Definition of $F$
\(\ds \) \(=\) \(\ds \map g {x, y}\) Definition of $f$

Therefore, $F$ is a surjection.


Thus, $F$ is a bijection.

It follows that $ R^{S \times T} \sim \paren {R^S}^T$ by the definition of set equivalence.

$\blacksquare$


Sources