[FOM] FOM RE:Pigeonholes

[Jeff Hirst]

Hi-

It seems to me that there are two very similar formats for
a naive formulation of the pigeonhole principle:

Form 1:  If we put P pigeons into H pigeonholes and P>H, then
some hole must contain at least two pigeons.

Form 2:  If we put P pigeons into H pigeonholes and P>H, then
some hole must contain P pigeons.

The first form holds for any cardinal P (especially the finite
ones), while the second holds for exactly the regular cardinals
(and in particular for aleph_0).  Ramsey's theorem can be viewed
as a generalization of the second form when P is aleph_0.
(Ramsey's theorem for exponent 1 is the second form when
P is aleph_0.)

It's not clear to me whether or not these forms actually constitute
some Ur-pigeonhole principle, or if they're more in the nature of
common motifs that mathematicians like to riff on.

I thought I would append the following list of bibtex entries for some
of my favorite sources on pigeonhole variants and their
connections to reverse math, computability and set theory.
This is far from being a complete list, and has much to do with
what I find close at hand at the moment.

For first-order versions and relationships to inductive hierarchies,
I.2 of Hajek and Pudlak:

@book {MR2000m:03003,
    AUTHOR = {H{\'a}jek, Petr and Pudl{\'a}k, Pavel},
     TITLE = {Metamathematics of first-order arithmetic},
    SERIES = {Perspectives in Mathematical Logic},
      NOTE = {Second printing},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {Berlin},
      YEAR = {1998},
     PAGES = {xiv+460},
      ISBN = {3-540-63648-X},
   MRCLASS = {03-02 (03D15 03F30 03H15 11U09 11U10 68Q15)},
  MRNUMBER = {2000m:03003},
}



For reverse math of Ramsey's theorem for exponents greater than or
equal to three, section III.7 of Simpson.  (Plus the other results
on the open Ramsey theorem, etc.)

@book {MR2001i:03126,
    AUTHOR = {Simpson, Stephen G.},
     TITLE = {Subsystems of second order arithmetic},
    SERIES = {Perspectives in Mathematical Logic},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {Berlin},
      YEAR = {1999},
     PAGES = {xiv+445},
      ISBN = {3-540-64882-8},
   MRCLASS = {03F35 (03-02 03B30)},
  MRNUMBER = {2001i:03126},
MRREVIEWER = {Michael M{\"o}llerfeld},
}

For reverse math of Ramsey's theorem for exponents 1 and 2 (and
more relationships to inductive hierarchies):

@article {MR2002c:03094,
    AUTHOR = {Cholak, Peter A. and Jockusch, Carl G. and Slaman, Theodore
              A.},
     TITLE = {On the strength of {R}amsey's theorem for pairs},
   JOURNAL = {J. Symbolic Logic},
  FJOURNAL = {The Journal of Symbolic Logic},
    VOLUME = {66},
      YEAR = {2001},
    NUMBER = {1},
     PAGES = {1--55},
      ISSN = {0022-4812},
     CODEN = {JSYLA6},
   MRCLASS = {03F35 (03C62 03D30 03D80)},
  MRNUMBER = {2002c:03094},
MRREVIEWER = {Roman Murawski},
}



For computability theoretic analysis of Ramsey's theorem:

@article {MR51:12495,
    AUTHOR = {Jockusch, Jr., Carl G.},
     TITLE = {Ramsey's theorem and recursion theory},
   JOURNAL = {J. Symbolic Logic},
    VOLUME = {37},
      YEAR = {1972},
     PAGES = {268--280},
   MRCLASS = {02F35 (02F50)},
  MRNUMBER = {51 \#12495},
MRREVIEWER = {John W. Berry},
}



For a nice exposition of Seetapun's result on RT(2):

@article {MR95j:03080,
    AUTHOR = {Hummel, Tamara Lakins},
     TITLE = {Effective versions of {R}amsey's theorem: avoiding the cone
              above {${\bf 0}'$}},
   JOURNAL = {J. Symbolic Logic},
  FJOURNAL = {The Journal of Symbolic Logic},
    VOLUME = {59},
      YEAR = {1994},
    NUMBER = {4},
     PAGES = {1301--1325},
      ISSN = {0022-4812},
     CODEN = {JSYLA6},
   MRCLASS = {03D30 (03D55 03F35)},
  MRNUMBER = {95j:03080},
MRREVIEWER = {Roman Murawski},
}



For elementary exposition of the relationship to cardinal properties:
(I admit particular bias in this selection.)

@book {MR1770510,
    AUTHOR = {Harris, John M. and Hirst, Jeffry L. and Mossinghoff, Michael
              J.},
     TITLE = {Combinatorics and graph theory},
    SERIES = {Undergraduate Texts in Mathematics},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {New York},
      YEAR = {2000},
     PAGES = {xiv+225},
      ISBN = {0-387-98736-3},
   MRCLASS = {05-01},
  MRNUMBER = {1 770 510},
}




Best,

-Jeff

-- 
Jeff Hirst   jlh at math.appstate.edu
Professor of Mathematics
Appalachian State University, Boone, NC  28608
vox:828-262-2861    fax:828-265-8617