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!

Cardnality of Infinite Sets (4)

  1. May 2, 2008 #1
    I am trying to get some practice on this topic by looking at past exams, but I am completely stuck at the following:

    1) Let N={natural numbers}. What is the cardnality of the set of all functions from N to {1,2,7}, |N| or c or 2c?

    [attempt: If it's the other way around, i.e. {all functions from {1,2,7} to N}, then I know that it has cardnality |NxNxN|=|N|]

    2) Assume that |A1|=|B1| and |A2|=|B2|.
    2a) Prove that |A1 x A2| = |B1 x B2|.
    2b) If A1 is disjoint from A2 and B1 is disjoint from B2, then |A1 U A2|=|B1 U B2|.


    [attempt: |A1|=|B1| means there exsits f: A1->B1 that is one-to-one and onto]

    Can someone give me some general hints on these questions, please? Any help would be greatly appreciated!
     
  2. jcsd
  3. May 2, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Those aren't 'attempts'. The first one just says you could solve it if it were a different problem (without even trying to solve the given one) and the other one is just a definition. You've asked dozens of question on this subject over the last week or so, try and show you've learned something.
     
  4. May 2, 2008 #3
    2a) f:A1->B1
    f(a1)=b1 bijection

    g:A2->B2
    g(a2)=b2 bijection

    Define h: A1xA2->B1xB2
    h(a1,a2)=(b1,b2)
    Then h would be a bijection (one-to-one and onto) and we're done, right?



    1) 2b) No clue and I can't even find a starting point. General hints would be appreicated!
     
  5. May 2, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. You are done with 2a). That wasn't so bad, was it? If x is in the union of A1 and A2 then it's either in A1 or it's in A2, but not both since they are disjoint. So you can use either f or g (that you defined for 2a)) to map it into B1 union B2. It's no more complicated than 2a).
     
  6. May 2, 2008 #5
    But to prove that|A1 U A2|=|B1 U B2|, I need a single function F: A1UA2 -> B1UB2 that is 1-1 and onto. f and g may be unrelated, how can I combine f and g into one function?
     
  7. May 2, 2008 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Define a new function by cases.
     
  8. May 2, 2008 #7
    But how?

    Let b1 E B1, b2 E B2

    F: A1UA2->B1UB2
    F(x)=b1 if x E A1
    F(x)=b2 if x E A2

    Would this work? (bijection?)
     
    Last edited: May 2, 2008
  9. May 2, 2008 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. Exactly like that. But put union instead of cross product. And I would put F(x)=f(x) and F(x)=g(x) with f and g defined as in 2a). You tell me if it's a bijection.
     
  10. May 2, 2008 #9
    I think putting
    F(x)=f(x)
    F(x)=g(x)
    is a very good idea

    Since f, g are onto, F must be onto

    f, g are 1-1 + disjoint => F is 1-1 ?? How can I prove this more rigorously?
     
  11. May 2, 2008 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The same way you usually prove a function is 1-1 or onto. Show me how.
     
  12. May 2, 2008 #11
    f is 1-1 iff f(x)=f(y) always implies x=y

    To prove f is 1-1:
    Suppose f(x)=f(y)
    Must show that this implies x=y

    But here in our case,
    F(x)=F(y) => ???

    I've never encountered a problem on proving a "piecewise" function is 1-1 so far...
     
  13. May 2, 2008 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Keep going. F(x)=F(y) is an element of B1 union B2. So it's either in B1 or B2 but not both. Split into cases.
     
  14. May 2, 2008 #13
    Are they both in B1? B2? or one in B1 and the other in B2?
     
  15. May 2, 2008 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    F(x)=F(y). There's only ONE of 'them'.
     
  16. May 2, 2008 #15
    But two different elements in the domain may be mapped to the same element in the codomain

    If A1 is disjoint from A2 and B1 is disjoint from B2, why does this imply F defined above is one-to-one? What is going to change if the sets are not disjoint?
     
    Last edited: May 2, 2008
  17. May 2, 2008 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    A lot will change if they aren't disjoint. But that's not the problem you are working on. Don't get distracted. Under the conditions given, two different elements in the domain are NOT mapped to the same element in the codomain. That's what you are trying to prove. And I am not going to prove it for you.
     
  18. May 2, 2008 #17
    F: A1UA2->B1UB2
    F(x)=f(x) if x E A1
    F(x)=g(x) if x E A2

    If F(x)=F(y) is in B1
    => F(x)=f(x)=f(y)=F(y) ??
    => x=y since f is 1-1 ??

    Similarly for B2...
     
  19. May 2, 2008 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Exactly. Again, not so hard, yes? Nicely done. And it's pretty much the same thing for onto.
     
    Last edited: May 2, 2008
  20. May 2, 2008 #19

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    And since you did so well on that one, finally. I'll give you a free hint. On the first problem suppose it were, what's the cardinality of the set of maps from N->{0,1}? Isn't that 2^N? No extra charge.
     
    Last edited: May 2, 2008
  21. May 2, 2008 #20
    For your simplified problem,

    Let T={f|f: N->{0,1} }
    T <-> {characteristic function of subsets of N} <-> {all subsets of N} <-> {power set of N}=P(N)
    (<-> means a bijection exists)

    And it's proven in my class that |P(N)|=c, so |T|=c. So I think I have a solid strategy for your simplified problem, but when one more element is added to the codmain, everything screws up...

    I am not too sure about the meaning of 2^(aleph_0)...what is it?
    The only cardinal numbers discussed in my class are aleph_0, c, 2^c, 2^(2^c), etc...
     
    Last edited: May 2, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cardnality of Infinite Sets (4)
  1. Infinite Sets (Replies: 2)

  2. Infinite set (Replies: 11)

Loading...