# [FOM] foundations of the pigeonhole principle

Arnon Avron aa at post.tau.ac.il
Fri Nov 21 03:23:58 EST 2003

>
> There are such a number of ways of formalizing the pigeonhole
> principle. I'm inclined to view it as a fundamental principle.
>
> Or is it best to view it as a special case of a more general principle?
>   Does it suffice to formulate it for natural numbers (sets of natural
> numbers)
> ?
> Maybe it is conceptually/foundationally best to think of it as
> characterizing finite sets (not necessarily finite sets of natural
> numbers)?

Maybe I miss understood what you are asking or have in mind, but
pigeonhole principle is a special case of the following well known
simple principle, which applies to *all* sets:

(*)  "If for every i in the set I, A_i is a set and a_i is a cardinality
such that Card(A_i) \leq a_i (and the sum of the a_i's
is well-defined), then the cardinality
of the union of the A_i's is less or equal to the sum of the a_i's."

Indeed, by contraposition the above principle we get the following
general formulation of the pigeonhole principle:

(**) "If for every i in the set I, A_i is a set and a_i is a cardinality
such that  (a_i \leq card(A_i) or card(A_i) \leq a_i),
the sum of the a_i's is defined, and the cardinality
of the union of the A_i's is greater than this sum,
then there exists i in I such that Card(A_i) > a_i."

Now of course by AC "(a_i \leq card(A_i) or card(A_i) \leq a_i)"
is always valid, and  the sum of the a_i's
is always well-defined, so (**) can in ZFC be simplified to:

(***) "If for every i in the set I, A_i is a set and a_i is a cardinality
such that  the cardinality
of the union of the A_i's is greater than the sums of the a_i's,
then there exists i in I such that Card(A_i) > a_i."

But even if one does not accept AC (and so rejects (***)), (**) remains
valid and applicable for finite sets, *and in many other cases*. (Of course
in its general form (*) itself depends on AC).

Arnon Avron