Results 1 to 8 of 8

Math Help - Set theory/ Cardinal Help

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    4

    Set theory/ Cardinal Help

    If f : A-B is the given function, the graph f is the subset of AcrossB consisting of all (a,f(a)).
    1. Prove that a-(a,f(a)) is a one-to-one map of A onto the graph of f.

    2. Let D and E be sets with cardinal numbers d and e. Suppose d is infinite and that e<=d. Prove that d^e is the number of one-to-one maps of E into D.(Hint: of course d^e is an upper bound. To get the reverse inequality, use part(a))

    I am OK with question 1.
    Here is my trial on Q2

    H(E,D) is the set of all functions from E to D. |H(E,D)| = d^e
    H'(E,D) is the set of all one-to-one functions from E to D. |H'(E,D)|= n

    n <= d^e since H'(E,D) is a subset of H(E,D)

    Construct a map F(H(E,D), H'(E,D)) making every function in H(E,D) be a one-to-one function. Then the graph of F is a subset of
    H(E,D)crossH'(E,D). Suppose the set of graph F is with cardinal t.

    Then, H(E,D) - (H(E,D), H'(E,D)) is a one-to-one map of H(E,D) onto the graph F.

    Then we have d^e = t <= d^e * n

    I am stuck here. Can we now conclude d^e <= n ? I guess no. But do you guys have any other solutions? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Suppose that  \mathbb{G} = \left\{ {(a,f(a):a \in A} \right\} then define \phi:A\mapsto \mathbb{G} as \phi(a)=(a,fa)
    It is clear that \phi must be onto.
    Suppose that  \phi (b)= \phi (c) then by definition that means (b,f(b))=(c,f(c)).
    By ordered pairs that means c=b so it is one-to-one.

    The second one is false. Let D=\{a,b,c\}~\&~E=\{0,1\}.
    There are no onto functions E\mapsto D
    There are no one-to-one functions D\mapsto E
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    4

    Smile

    Quote Originally Posted by Plato View Post
    Suppose that  \mathbb{G} = \left\{ {(a,f(a):a \in A} \right\} then define \phi:A\mapsto \mathbb{G} as \phi(a)=(a,fa)
    It is clear that \phi must be onto.
    Suppose that  \phi (b)= \phi (c) then by definition that means (b,f(b))=(c,f(c)).
    By ordered pairs that means c=b so it is one-to-one.

    The second one is false. Let D=\{a,b,c\}~\&~E=\{0,1\}.
    There are no onto functions E\mapsto D
    There are no one-to-one functions D\mapsto E
    The question says D is infinite.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by yaoyao View Post
    The question says D is infinite.
    Ha. Read too quickly.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2010
    Posts
    4
    Could someone move this thread to the Topology subforum? Thank you.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by yaoyao View Post
    Could someone move this thread to the Topology subforum? Thank you.
    Why? This isn't topology. Also, do you still need help for number two?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2010
    Posts
    4
    Yes I need. Not answered yet? Do you have a sol?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jan 2008
    Posts
    19
    Ha. So I just saw this on yahoo answers and answered it there, and I remembered I saw it here and was going to answer it, but ran out of time. Here's the solution, but properly formatted.
    ---------------------
    This is trivial with observation in part 1.

    Firstly, it's silly a lot of times to think of the graph of a function to be different than the function itself, because the general set theoretic definition of a function is the set of ordered pairs, ie the graph. This is one times where thinking about the graph of a function is actually very very useful.

    So, what do we need to show? We need to show there is an injection K:E\to D to the set of injections from E to D. Take f:E\to D arbitrary. Then define k_f:E\to E\times D to be the injection from defined in part 1.
    NOTE: Here is where we will use all of our assumptions. there is a natural bijection between E\times D to D because |D|\geq\aleph_0 and |E|\leq|D|. So therefore, we can view k_f as an injection from E to D itself just by coding elements of E\times D into elements of D. This is actually the only place where this proof uses AC as well. But it's very essential, without AC this theorem will most def. fail violently.

    Then define the map K as f\mapsto k_f. This map is clearly an injection (as a function is completely determined by it's graph) and this, we are done, as K is an injective map from the set of functions from E to D to the set of injections between E and D.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinal numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 16th 2010, 01:25 PM
  2. Cardinal Exponentiation
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 1st 2010, 03:22 AM
  3. regular cardinal. ZFC
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 04:47 PM
  4. Cardinal Exponentials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 13th 2009, 12:25 PM
  5. Cardinal number
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 16th 2008, 02:57 PM

Search Tags


/mathhelpforum @mathhelpforum