Results 1 to 7 of 7

Math Help - bijection between two sets of functions

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    bijection between two sets of functions

    Hi

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

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

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

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

    Suppose

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

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

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

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

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

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

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

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

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

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

    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.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: bijection between two sets of functions

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

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

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

    Edited: Wrong argument.
    Edited: Wrong day for posting.
    Last edited by FernandoRevilla; January 1st 2012 at 10:31 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: bijection between two sets of functions

    Here is a picture.



    Note that since \pi and \phi are bijections, there exist \pi^{-1} and \phi^{-1} such that \pi\circ\pi^{-1}=\mathrm{id}_B, \pi^{-1}\circ\pi=\mathrm{id}_A, \phi\circ\phi^{-1}=\mathrm{id}_D and \phi^{-1}\circ\phi=\mathrm{id}_C, where \mathrm{id}_X is the identity function on X. Therefore, you can multiply various equalities by these functions. E.g., \Gamma (f)=\phi\circ f\circ \pi^{-1} implies \Gamma (f)\circ\pi= \phi\circ f\circ \pi^{-1}\circ\pi =\phi\circ f\circ \mathrm{id}_A= \phi\circ f.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: bijection between two sets of functions

    Right. A quick, mental (and wrong) reasoning led me to \Gamma (f)=\Gamma (g)\Rightarrow\ldots \Rightarrow f=g . Better appproach: denoting a=\textrm{card} (A),\ldots, \textrm{card}(D)=d we have a=b,\;c=d , \textrm{card}(^AC)=c^a etc.
    Last edited by FernandoRevilla; January 1st 2012 at 10:16 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: bijection between two sets of functions

    Um, why is it wrong?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: bijection between two sets of functions

    Quote Originally Posted by emakarov View Post
    Um, why is it wrong?
    Perhaps too much whisky and champagne last night.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijection between Sets(again)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: October 20th 2009, 01:27 PM
  2. Bijection between Sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 19th 2009, 03:18 PM
  3. Bijection functions and inverses
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2009, 09:28 AM
  4. Bijection and Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 23rd 2009, 03:45 AM
  5. Bijection in infinite sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: May 25th 2008, 02:57 PM

/mathhelpforum @mathhelpforum