1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Countable sets | If k:A->N is 1-to-1, then A is

  1. Sep 14, 2010 #1
    Countable sets | If k:A-->N is 1-to-1, then A is...

    1. The problem statement, all variables and given/known data
    Suppose we found a 1-to-1 function k that maps the set A to the set N, where N is the set of natural numbers. What can we say about the set A?


    2. Relevant equations



    3. The attempt at a solution

    The answer is 'A is at most countable.' I understand this. But my question is, is it also possible for A to be finite, as well as infinite? i.e. its possible for A to be either

    {a1, a2, a3}

    or

    {a1, a2, a3, a4, a5,...}

    all the way to infinity.

    Thanks,

    M
     
  2. jcsd
  3. Sep 14, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    Depends on what you mean by '1-to-1'. k(a1)=1, k(a2)=2 and k(a3)=3 is a 1-to-1 (if you mean injective) map from {a1,a2,a3}->N. But it's not onto (surjective). If you take '1-to-1' to be bijective, then sure, A is countably infinite.
     
  4. Sep 14, 2010 #3
    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    k is injective and that's all we know. I just want to know if its possible, given that k is injective, for A to be finite or infinite, not whether if it actually is.
     
  5. Sep 14, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    I already gave you an example where k is injective and A is finite. You give me an example where it's infinite.
     
  6. Sep 14, 2010 #5
    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    Ok, suppose k is injective.

    k(a1)=1, k(a2)=2, k(a3)=3, k(a4)=4, k(a5)=5, k(a6)=6,..., k(am)=m, k(a(m+1))=m+1,...

    So k is a mapping from {a1, a2, a3, a4, a5, a6,..., am, a(m+1),...} --->N.

    So thus, A is allowed to be a countably infinite set.

    All right, now whats wrong with my argument?
     
  7. Sep 14, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    Why do you think there is anything wrong with it? The solution said 'A is at most countable'. So yes, A can be either finite or countably infinite. Isn't that what 'at most countable' means? What's the question again?
     
  8. Sep 14, 2010 #7
    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    Thank you for your help, I really appreciate it.

    All right then, I was just confused by the phrase "at most countable." It would have been clearer for me if they said "A is, at the very least, countable" but we don't know whether it's finite or infinite.

    My question was whether its possible for A to be finite or infinite given that k is an injection from A to N.
     
  9. Sep 14, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    Ok, then we agree. A is either finite or countably infinite. "at most countable" means the same thing as "A is, at the very least, countable". You knew the answer from the beginning, it was just the phrasing.
     
  10. Sep 14, 2010 #9
    Re: Countable sets | If k:A-->N is 1-to-1, then A is...

    Awesome, thanks man!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook