1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Topology question: finite sets

  1. Jul 20, 2011 #1
    1. The problem statement, all variables and given/known data
    If A and B are finite, show that the set of all functions f: A --> B is finite.


    2. Relevant equations
    finite unions and finite caretesian products of finite sets are finite


    3. The attempt at a solution
    If f: A -> B is finite, then there exists m functions fm mapping to B. Let Bm = {f1, f2, ... , fm: fx(A) [itex]\in[/itex]B [itex]\forall[/itex] x[itex]\in[/itex] Z+}. There is a bijection from Bm to Z+ and g: Bm -- {1,. .. ,m} so the set of functions is finite.

    I don't feel like this is enough. Could I get a little help? Thanks



    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Jul 20, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's not so much 'not enough' as just plain confusing. Let a be the number of elements in A and b be the number of elements in B. How many functions from A->B? You can just count them. Suppose a=2 and b=3? How many functions in that case?
     
  4. Jul 21, 2011 #3
    do you mean if the cardinality of A is 2 and the cardinality of B is 3?
     
  5. Jul 21, 2011 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes. That's what Dick said.
     
  6. Jul 22, 2011 #5
    In my opinion, Dick has started an excellent method to learn how this works. Start there & understand where that's going thoroughly, then digest my post.

    I used to get points taken off for things like notation which assumes m is finite.

    Possible Workarounds,
    A. there exists m functions, m is possibly infinite, fm ...
    B. restructure the proof, without using notation which implies m is finite, until finiteness is established.


    One key, how does the Cartesian product of A & B, written A x B relate to the number of possible functions?

    Minor point: in Dick's example, a=2, b=3, none of the functions will be onto. One might be tempted to use factorials, nCr or nPn, but those are only in the right subject area, not what we actually need.
     
  7. Jul 23, 2011 #6
    "One key, how does the Cartesian product of A & B, written A x B relate to the number of possible functions?"

    A x B must be countable since A and B are finite and countable. A x B must be finite.

    Then the set F = {f: A -->B} can be injectively mapped to the integers to get {(a, f(a)), (b,f(b)), (c,f(c)),...}. Then since A = {a1, a2, a3,... , a_m}, then B=(f(a1), f(a2), ...f(a_m)} is finite.
    But that isn't what I was looking for... :-\

    the NUMBER of functions mapping A to B is finite. If cardinality of A is 2 and the cardinality of B is 3, then the number of different mappings should be "2 choose 3" right? so then if the cardinality of A is m and cardinality of B is n then the number of different ways should be "m choose n"? (I can't find the proper latex commands).

    Is this just about right?
     
  8. Jul 23, 2011 #7
    Actually 2 choose 3, written 2C3 = 0.
    Perhaps you meant 3C2 =3
    At first I was tempted to use 3 choose 2, but the right formula is even simpler. If necessary, write out the various possible functions from A to B. For simplicity, let 1,2,3 be in A, and e,f be in B.
    Have you included {(1,e), (2,e), (3,e)}?
     
  9. Jul 23, 2011 #8
    thanks for the notation correction nickalh. I was assuming that the cardinality of A is 2 and the cardinality of B is 3, not the other way around (based on what dick said in post 2). But you're quite correct... now I'm confused... perhaps the combinatorics only works for injective functions???

    Either way, the number of functions mapping a 3 element set to a 2 element set appears to be 3C2 = 3
     
  10. Jul 23, 2011 #9
    Whoops, I switched the cardinalities of A & B.
    I have rewritten my previous post to be consistent with the rest of the thread.

    At first I was tempted to use 3 choose 2, but the right formula is even simpler. If necessary, write out the various possible functions from A to B. For simplicity, let 1,2 be in A, and e,f,g be in B.
    Have you included {(1,e), (2,e)}?
    And 3C2 is *not* what we want.

    To help clear up your confusion:
    i. For f(1) how many possible choices are there?
    ii. For f(2) how many possible choices are there?
    (injectivity is not required unless that was left out of the original problem statement)
    iii. Multiply the answer for i. * answer for ii.

    Off the top of my head, I believe 3C2 is right for injective, 1 to 1, functions.


    Unrelated tangent:
    Also, pretend for a moment we needed 3C2.
    To get around the 2C3 dilemna, I would define a new piecewise function, C'.
    C'(m,n) = mCn if m>=n
    nCm if m<n
    Why can we swap m & n so easily? Because | A X B | = |B X A|.
    Does anyone know how to display piecewise functions on this board?
     
    Last edited: Jul 23, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Topology question: finite sets
  1. Finite set (Replies: 7)

Loading...