Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Showing the cardinality of A is less than B's

  1. Mar 4, 2012 #1
    1. The problem statement, all variables and given/known data
    If A and B are sets we say that |A|≤|B| if and only if there exists a one-to-one function f:A→B.

    Prove that if A and B are sets such that A[itex]\subseteq[/itex]B , then |A|≤|B|.



    2. Relevant equations
    Our text does not define this, so the definition comes from my class notes.

    Definition: Suppose A and B are sets.
    Then |A|≤|B| iff there exists a 1-1 function from A to B.
    Note: Such an an f, if it exists, may or may not be onto. If f is also onto, then |A|=|B|


    3. The attempt at a solution

    Since A[itex]\subseteq[/itex]B, then either A is B or all of A is in B.

    Hence, there exists an injection f such that f:A→B defined by f(a)=a for all a in A.
    Since f is not a onto B, then |A| < |B|

    If f is a bijection, then, by definition, it follows that |A|=|B|.


    Does this proof make sense?
     
  2. jcsd
  3. Mar 4, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Just because f is not onto does not imply that |A|<|B|. That's only true for finite sets. Can you give me a counterexample?
     
  4. Mar 4, 2012 #3
    |N| < |R| and there is not an onto mapping of N to R
     
  5. Mar 4, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's not a counterexample. I want an example where f is not onto but |A|=|B|.
     
  6. Mar 4, 2012 #5
    I am unsure of an example of that. For infinite sets, all I know is either it will be the same as |N| else it will be what |R| is.
     
  7. Mar 4, 2012 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    How about A=even integers, B=all integers? Have you looked at cases like that?
     
  8. Mar 4, 2012 #7
    If f is a function that takes all integers to even integers, f can be defined as f(n)=2n for all n in the integers. That is onto.
     
  9. Mar 4, 2012 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That function would show |A|=|B|. But the function you are using in your proof is f(n)=n. That's is not onto. What I'm trying to point out the that f(n)=n not being onto does not show |A|<|B| which you are saying in your proof.
     
  10. Mar 4, 2012 #9
    I see. Then if for all a in A there exists a b in B such that f(a)=b and if A is countable and B is not, f is not onto and |A| < |B|. If A is a countable subset of B, then |A| = |B|.

    Is this correct thinking?
     
  11. Mar 4, 2012 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Pretty much. But that's not something you need to include in your proof. You defined a 1-1 function from A to B by defining f(a)=a. By your definition that shows |A|≤|B|. That's about all you need to say.
     
  12. Mar 4, 2012 #11
    I see. Thank you for the help!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook