# bijection between two sets of functions

• Jan 1st 2012, 06:34 AM
issacnewton
bijection between two sets of functions
Hi

here's a problem I am trying to solve. Suppose A,B,C,D are sets

$\displaystyle [(A\sim B)\wedge(C\sim D)\Rightarrow (^AC \sim \; ^BD)]$

where $\displaystyle ^AC$ is set of all functions from A to C. and $\displaystyle ^BD$ is
set of all functions from B to D. Following is my work. I have already prove that

$\displaystyle [((A\sim B)\wedge(C\sim D)\Rightarrow(A\times C \sim B \times D)]$

Suppose

$\displaystyle (A\sim B)\wedge(C\sim D)$

$\displaystyle \therefore A\times C \sim B \times D$

I have also already proved that, for any sets A and B,

$\displaystyle (A\sim B)\Rightarrow(\mathcal{P}(A)\sim \mathcal{P}(B))$

$\displaystyle \therefore \mathcal{P}(A\times C) \sim \mathcal{P}(B \times D)$

that means that there is a bijection from $\displaystyle \mathcal{P}(A\times C)$
to $\displaystyle \mathcal{P}(B \times D)$.

$\displaystyle \mathcal{P}(A\times C)$ is the set of all subsets of $\displaystyle A\times C$
. But subsets of $\displaystyle A\times C$ are just relations from A to C. So
$\displaystyle \mathcal{P}(A\times C)$ is set of all relations from A to C. In similar way,
$\displaystyle \mathcal{P}(B\times D)$ is set of all relations from B to D. Functions are special kind of relations , So

$\displaystyle ^AC\subseteq \mathcal{P}(A\times C)$

$\displaystyle ^BD \subseteq \mathcal{P}(B\times D)$

Since $\displaystyle \mathcal{P}(A\times C) \sim \mathcal{P}(B\times D)$ , there is some bijection between these two sets. Let it be h

$\displaystyle h:\mathcal{P}(A\times C)\to \mathcal{P}(B\times D)$

From here on, I am stuck. We have a bijection between one family of relations to another family of relations. What we need is a bijection between the subsets of
these families.

(Emo)
• Jan 1st 2012, 09:29 AM
FernandoRevilla
Re: bijection between two sets of functions
Quote:

Originally Posted by issacnewton
Suppose A,B,C,D are sets

$\displaystyle [(A\sim B)\wedge(C\sim D)\Rightarrow (^AC \sim \; ^BD)]$

where $\displaystyle ^AC$ is set of all functions from A to C. and $\displaystyle ^BD$ is
set of all functions from B to D.

I suppose you mean functions or mappings. Then, consider bijections $\displaystyle \pi:A\to B$ and $\displaystyle \phi: C\to D$ . Now, define $\displaystyle \Gamma:^AC\to ^BD$ such that $\displaystyle \Gamma (f)=\phi\circ f\circ \pi^{-1}$ . Easily proved, $\displaystyle \Gamma$ is bijective hence $\displaystyle ^AC \sim \; ^BD$ .

Edited: Wrong argument.
Edited: Wrong day for posting.
• Jan 1st 2012, 09:45 AM
emakarov
Re: bijection between two sets of functions
Here is a picture.

Note that since $\displaystyle \pi$ and $\displaystyle \phi$ are bijections, there exist $\displaystyle \pi^{-1}$ and $\displaystyle \phi^{-1}$ such that $\displaystyle \pi\circ\pi^{-1}=\mathrm{id}_B$, $\displaystyle \pi^{-1}\circ\pi=\mathrm{id}_A$, $\displaystyle \phi\circ\phi^{-1}=\mathrm{id}_D$ and $\displaystyle \phi^{-1}\circ\phi=\mathrm{id}_C$, where $\displaystyle \mathrm{id}_X$ is the identity function on $\displaystyle X$. Therefore, you can multiply various equalities by these functions. E.g., $\displaystyle \Gamma (f)=\phi\circ f\circ \pi^{-1}$ implies $\displaystyle \Gamma (f)\circ\pi= \phi\circ f\circ \pi^{-1}\circ\pi =\phi\circ f\circ \mathrm{id}_A= \phi\circ f$.
• Jan 1st 2012, 10:03 AM
FernandoRevilla
Re: bijection between two sets of functions
Right. A quick, mental (and wrong) reasoning led me to $\displaystyle \Gamma (f)=\Gamma (g)\Rightarrow\ldots \Rightarrow f=g$ . Better appproach: denoting $\displaystyle a=\textrm{card} (A),\ldots, \textrm{card}(D)=d$ we have $\displaystyle a=b,\;c=d$ , $\displaystyle \textrm{card}(^AC)=c^a$ etc.
• Jan 1st 2012, 10:17 AM
emakarov
Re: bijection between two sets of functions
Um, why is it wrong?
• Jan 1st 2012, 10:30 AM
FernandoRevilla
Re: bijection between two sets of functions
Quote:

Originally Posted by emakarov
Um, why is it wrong?

Perhaps too much whisky and champagne last night. :)
• Jan 2nd 2012, 01:18 AM
issacnewton
Re: bijection between two sets of functions
thanks. I was almost there as I have proved the bijection between the set of relations from A to C to the set of relations from B to D.