[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
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
More information about the FOM
mailing list