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

Concept of the pigeonhole principle

  1. Aug 7, 2005 #1
    This question applies with the so called "infinite" pigeonhole principle. Why is it possible to construct a one-one function out of two sets where the codomain has a length smaller than the length of the domain?
  2. jcsd
  3. Aug 7, 2005 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Could you go into a lot more detail? It's hard to answer appropriately if I don't know just where you're confused.

    The only measure of "size" that matters for one-to-one functions is cardinality.
  4. Aug 7, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    "length" what does that mean in this context?
  5. Aug 7, 2005 #4

    This is what I understood so far...

    I was able to find that in the infinite case, "If n holes contains an infinite number of points, then at least one of the holes contain an infinite number. In particular, if the holes are labeled or ordered from 1 to n, then there must be a first hole with infinitely many points in it."

    What confuses me is regarding whether this concept I have researched applies to a one-one function...

    I was thinking of cramming Q+, the positive rationals into N the natural numbers with space left over to do it infinitely more times. Let p/q always be a reduced fraction in Q+ and define the map Q+--->N;p/q--->(2^p)(3^q). I can know that
    this is a 1-1 map by the fundamenntal theorem of arithmetic. (unique prime
    factorization) and no number that has any other prime in it's decomposition
    other than 2 or 3 is in the range.

    Also, I can construct a cartesian plane with all the values of y between -1 and 1, exclusively, ie., (-1,1) and all the values of x indefinitely. From here, I can assigned a one-one function in which every value in x corresponds to a unique value of y.
  6. Aug 7, 2005 #5
    Length here, is not that important since it doesnt determine size of the interval, since the interval will always have infinitely many points...
  7. Aug 9, 2005 #6
    You can also think it of as an infinite set broken into a finite number of subsets, then one of the subsets must be an infinite set.


    ? Whats the problem ?

    Yes this is true, it follows from the schroeder-bernstein theorem. It goes to show how dense the set of (-1,1) can be.

    -- AI
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook