# [FOM] foundations of the pigeonhole principle?

Robert Tragesser robert at thesavvydog.com
Tue Nov 25 03:44:05 EST 2003

```Arnon Avron,
Thank you very much for this.  I did formulate for myself the
natural generalization about cardinalities...you took it some
clarifying steps further.  But I don't think that, without further
argument, this entirely answers my question, albeit my question was
Very roughly, the question I am trying to ask is this,

When do fom-ers regard a mathematical principle as having been
adequately foundationally clarified? [This is in part a request
relative to a particular case for a clarification of the use of
'foundations'.]

I can see why your (i), (ii), (iii) could be regarded as doing
the trick - it is clarified in relation to general principles about
cardinality of sets.
At the same time, when one considers the pigeonhole principle in
its most informal expressions (mentioning "pigeonholes" or "boxes"),
cardinality is not the most striking or salient aspect of it.  It is
rather that Ramsey Theorem clarifies it...which can be regarded as
another sort of "generalization" of the pigeonhole principle (the
Ramsey Theorem somehow lets us see "what's going on" with that
principle), as can indeed combinatorial theory.  Might not, then,
combinatorial theory be construed as foundationally
clarifying...combinatorial theory rather than the set theory of
cardinals(under AC)?
Does then Reverse Mathematics of Ramsey Theorem add another moment
or dimension of foundational clarification?
The principle does then seem to have some traits that make it
interesting to explore it as a test case or touchstone for getting
clear about what we want from foundational efforts - it's (what Paul
Erdös called) purely existential,  it is intuitively clear and
immediately evident,  its natural logical analysis would have us cast
it first in second order logic, and then recast it in many-sorted logic
or set theory (and so two different avenues for two kinds of
foundational regard).
It could also be viewed as a principle about natural numbers, and
so related to mathematical induction (as well as the Inutitionists
justification of mathematical induction), and so founding the more
abstract principle (thinking of the notion of finite set deriving from,
being founded on,  the notion of "finite set" of natural numbers).  It
could be regarded as a defining characteristic of finite sets.

Robert Tragesser
845-358-4515 (Ph)
26 DePew Avenue #1
Nyack, NY 10960-3839

```