[FOM] foundations of the pigeonhole principle

[Arnon Avron]

> 
> 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 
as formulated above, the answers to your question are simple. The
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