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: Pigeonhole principle and counting

  1. Dec 7, 2007 #1
    1. The problem statement, all variables and given/known data
    1) 100 of the 5-element subsets of {1, . . . , Y } have the same SUM. (Fill in Y . Make Y as small as you can, however you need NOT prove that it is smallest possible. You might
    need a calculator.)

    2) Let FUNC be the set of all FUNCTIONS from N to N. Show that FUNC is NOT countable.

    2. Relevant equations
    Pigeonhole principle.

    3. The attempt at a solution
    1) The only thing I know is that I need to apply pigeonhole principle... Can someone give me a nudge?
    2) Definitely confused here. Since the integers are countable, the naturals must be countable too right? THen how the heck are I supposed to show that FUNC isn't countable when it is?
  2. jcsd
  3. Dec 11, 2007 #2
    a) Can you venture a guess as to what the pigeons and holes are?

    Natural numbers are countable, but that does not mean that all functions on N are countable. There are definitely an infinite number of functions mapping N to N, and there is no way to write them such that they could be counted.

    The set of all rational numbers is countable, even though there is an infinite gap between any two rational numbers. If the all the rational numbers were written in an [tex]\infty X \infty[/tex] array, they could be counted by the diagonals. No such rule exists for functions over N.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook