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: Help me out with proof for countable

  1. Feb 7, 2009 #1
    1. The problem statement, all variables and given/known data

    If S is a set of function from {2,5} to a set of natural numbers, show S is countable?

    The question also ask what if S is from a set of natural number to {2,5}, is that countable

    2. Relevant equations

    3. The attempt at a solution
    I try to do it like this. Suppose E={2,5}, F be the set of natural numbers. suppose there are n natural numbers there. then
    f(2)={n elements}. f(5) = elements, so there are n^2 elements of the function. So S is countable? It that right that I just assume there are n elements in the natural set?
  2. jcsd
  3. Feb 7, 2009 #2
    It's not really necessary to know the number of elements of each function, just the number of functions. It is also not apparent that the subset of natural numbers is finite. The defining property of a function is that each element of the domain is mapped to exactly one element of the range. Thus, we can count how many ways there are to associate the 2 numbers in the domain to elements of the codomain in ordered pairs (f(2), a), (f(2), b) and so on. Since this is just a relabeling of the existing elements, the cardinality of the set remains unchanged. The same can be done to construct a countable set for f(5). You can then use the theorem that the union of a finite amount of countable sets is countable, or prove it if you haven't already done so (not very difficult).
    Last edited: Feb 7, 2009
  4. Feb 7, 2009 #3


    User Avatar
    Science Advisor
    Homework Helper

    That's pretty confusing. The function is defined by the value of the ordered pair (f(2),f(5)). The the cardinality of that is (similar to what the OP said) the cardinality of the cartesian product (not the union) NxN, where N is the integers. Have you shown NxN is countable?
  5. Feb 8, 2009 #4


    User Avatar
    Science Advisor

    f(2) can be any natural number. f(3) can be any natural number. Since the domain consists only of 2 and 3, there is a natural correspondence between the set of such functions and the set of ordered pairs of natural numbers: f-> (f(2), f(3)). Do you know the proof that N x N is countable?
  6. Feb 8, 2009 #5
    How about the mapping f:N->{2,5}. Is this countable?
  7. Feb 8, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    Yes. Prove that it can be mapped to NxN. That's what people have been trying to point out to you.
  8. Feb 8, 2009 #7
    I get it now.Thanx so much
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook