Question

1) State a useful denial of the phrase "X is finite". That is, state the definition of X being infinite in a more positive way than just "not finite".

2) The Pigeonhole Principle also says that there does not exist a surjection from N_m to N_m, where m<n. Write this as a statement about pigeons and pigeonholes.

Answer 1

1) A set is said to be countably infinite (or just countable) if and only if it has cardinality equal with that of the set of Natural Numbers N.A set X is said to be at most countable if and only if it is either countable or finite.

Let X be a countable set than by definition, we know that there exists a bijection f : N -> X from N to X. Thus every element of X can be written in the form f(n) for exactly one natural number n.

2) According to this statement if n pigeons are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one pigeon.

So if f sends pigeons from a finite set S to a set labeled with elements of a proper subset S, there are distinct pigeons x and y with

f(x) = f(y)