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!

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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook