• Support PF! Buy your school textbooks, materials and every day products Here!

Pigeonhole principle and counting

  • #1

Homework Statement


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.

Homework Equations


Pigeonhole principle.


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?
 

Answers and Replies

  • #2
23
0
a) Can you venture a guess as to what the pigeons and holes are?


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

Related Threads on Pigeonhole principle and counting

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
6K
Replies
12
Views
897
  • Last Post
Replies
1
Views
773
  • Last Post
Replies
3
Views
445
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
9
Views
2K
Top