Concept of the pigeonhole principle

Main Question or Discussion Point

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?
 

Answers and Replies

Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
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.
 
matt grime
Science Advisor
Homework Helper
9,394
3
"length" what does that mean in this context?
 
Hello...

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.
 
Length here, is not that important since it doesnt determine size of the interval, since the interval will always have infinitely many points...
 
644
1
irony of truth said:
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."
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.

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

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.
? Whats the problem ?

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.
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
 

Related Threads for: Concept of the pigeonhole principle

  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
8
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
3
Views
511
  • Last Post
Replies
11
Views
3K
Replies
4
Views
2K
Top