From  Fri May 8 19:18:46 1998
From: Bill Dubuque
Newsgroups: sci.math,sci.logic
Subject: Re: pigeon hole theory
Date: 07 May 1998 21:31:09 0400
Organization: MIT
Lines: 144
MessageID:
References:
<6iqp7g$i25@mcmail.CIS.McMaster.CA> <6irdgs$16d$1@Radon.Stanford.EDU>
Vaughan R. Pratt wrote:

 Zdislav V. Kovarik wrote:
 > hillary <03923@udel.edu> wrote:
 > : Could you explain how to go about proving the pigeon hole theory
 > : by induction?
 >
 > How far did you get trying on your own?

 Hear, hear. And when you've done it, try the converse: infer the
 induction principle from the pigeon hole principle. (Reference: Floyd
 and Beigel, "The Language of Machines", CS Press, 1994, exercise 0.622).
Most informal "proofs" of equivalence of wellordering, induction,
and the pigeonhole principle are nonsense. Such a proof must be given
relative to a weak base theory to avoid begging the principle. Further,
one must be precise about where such equivalences hold because there
are easy counterexamples involving ordinals and cardinals (cf. below).
Unless the author of such a "proof" has a good grasp of logic, it
probably fails on both of these points, e.g. see the Math Reviews
and my prior posts below.
Bill Dubuque

83f:04001 0401
Hansen, Rodney T.; Swanson, Leonard G.
Placing the pigeonhole principle within the defining axioms of the integers.
Proceedings of the West Coast Conference on Combinatorics, Graph Theory
and Computing (Humboldt State Univ., Arcata, Calif., 1979), pp. 183186,
Congress. Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980.

The authors argue very informally that the pigeonhole principle can
replace the induction axiom or the wellordering principle in the set
theoretic characterization of the natural numbers. However, this claim
must be formulated carefully if it is to be correct. For example, (1) the
ordinals less than omega + omega satisfy the first four (Dedekind) Peano
postulates and the wellordering principle, but not the induction axiom or
the pigeonhole principle; (2) the class of all cardinals satisfies the
first four Peano postulates, the wellordering principle, and the
pigeonhole principle (if m elements are distributed into n boxes and m > n
then two elements must go into the same box), but not the induction axiom.
Reviewed by Perry Smith

89e:03084 03E20
Swanson, Leonard G. (1PRLS); Hansen, Rodney T.
The equivalence of the multiplication, pigeonhole, induction, and well
ordering principles. (English)
Internat. J. Math. Ed. Sci. Tech. 19 (1988), no. 1, 129131.

Informal settheoretic arguments are given for the equivalence of the
principles mentioned in the title, all of which are stated for the natural
numbers. The authors work in ZermeloFraenkel set theory, but such arguments
should be given in a weaker system of set theory or arithmetic in which the
principles in question are not theorems. The strength of several forms of
the pigeonhole principle was studied by T. von der Twer [Arch. Math. Logik
Grundlag. 21 (1981), no. 12, 6976; MR 84e:03072].
Reviewed by Perry Smith
From: Bill Dubuque
Date: 1998/02/19
Newsgroups: sci.math,sci.logic
Robin Chapman writes:

 Michael David Cochran wrote:
 >
 > Does anyone have a fast proof of the WellOrdering Property? ...

 The wellordering theorem is equivalent to the Principle of induction...
Technically they are not equivalent and the informal claim that
they are is a common oversight. For example, various classes of
ordinals and cardinals are easily seen to satisfy all of Peano's
postulates with wellordering replacing induction, but they don't
enjoy induction. To characterize the naturals one needs also the
property that every nonzero element has an immediate predecessor.
Analogous remarks apply to the informal claim that induction is
"equivalent" to the pigeonhole principle.
Subject: Re: Is the PigeonHole Principle a standard tool?
From: Bill Dubuque
Date: 1996/12/04
Newsgroups: sci.math,sci.logic
blackj@toadflax.cs.ucdavis.edu (John R. Black) writes:
>
> A friend of mine just submitted a paper to a refereed journal, and although
> it was an Algebraic Geometry paper, he used the PigeonHole Principle (rare
> in that neck of the woods). The paper was returned to him, and the ref had
> written "What is the PigeonHole Principle?"
>
> Is the PHP really that nonstandard? I must have seen it 5 times as an
> undergrad, but I suppose it's not part of the normal math curriculum?
> (I was comp science.) Would you use it without definition in one of
> your papers?
According to Paul Halmos it is one of the "elements" of math, see
Halmos, P. R.
Does mathematics have elements?
Math. Intelligencer 3 (1980/81), no. 4, 147153.
MR 83e:00004 00A05 00A25 03A05
There has recently been a lot of work by logicians studying the strength
of the pigeonhole principle in weak fragments of logic, and for
establishing lower bounds for prooflength in propositional systems, e.g.
Ajtai, M. (1IBM2)
The complexity of the pigeonhole principle.
Combinatorica 14 (1994), no. 4, 417433. MR 96a:03065 03F20
Here are some other useful references culled from MathSciNet:
Erickson, Martin (1NMOS)
An introduction to combinatorial existence theorems.
Math. Mag. 67 (1994), no. 2, 118123. 95e:05004 05A05 05C55
Graham, N. (1NMSCL); Entringer, R. C. (1NM); Szekely, L. A. (HEOTVOC)
New tricks for old trees: maps and the pigeonhole principle.
Amer. Math. Monthly 101 (1994), no. 7, 664667. MR 95m:05144 05C38 05C05
Hutchinson, Joan P.; Trow, Paul B.
Some pigeonhole principle results extended.
Amer. Math. Monthly 87 (1980), no. 8, 648651.
MR 82g:05016 05A99
Swanson, Leonard G. (1PRLS); Hansen, Rodney T.
The equivalence of the multiplication, pigeonhole, induction, and well
ordering principles.
Internat. J. Math. Ed. Sci. Tech. 19 (1988), no. 1, 129131.
MR 89e:03084 03E20
von der Twer, T.
On the strength of several versions of Dirichlet's ("pigeonhole")
principle in the sense of firstorder logic.
Arch. Math. Logik Grundlag. 21 (1981), no. 12, 6976.
MR 84e:03072 03F30 03B30 03C62 03H15
Bill Dubuque
From  Fri May 8 21:31:19 1998
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Newsgroups: sci.math,sci.logic
Subject: Re: pigeon hole theory
Date: 8 May 1998 18:13:37 GMT
Organization: Stanford University: Computer Science Department, CA USA
Lines: 59
MessageID: <6ivi0h$ot7$1@Radon.Stanford.EDU>
References: <6iqp7g$i25@mcmail.CIS.McMaster.CA> <6irdgs$16d$1@Radon.Stanford.EDU>
Xref: ar4dec01 sci.math:68691 sci.logic:7658
In article ,
Bill Dubuque wrote:
>Most informal "proofs" of equivalence of wellordering, induction,
>and the pigeonhole principle are nonsense. Such a proof must be given
>relative to a weak base theory to avoid begging the principle. Further,
>one must be precise about where such equivalences hold because there
>are easy counterexamples involving ordinals and cardinals (cf. below).
>Unless the author of such a "proof" has a good grasp of logic, it
>probably fails on both of these points, e.g. see the Math Reviews
>and my prior posts below.
The proof of PHP>IND as given by Floyd and Beigel does not fail on the
second point, for the rather boring reason (relative to the exotic
counterexamples in Smith's reviews) that it is correct, provided PHP is
taken to be the statement that there is no injective map f from {x  0
<= x <= m} to {x  0 <= x <= m1} for any m > 0. I've reproduced the
proof below, it's short and sweet and you can easily convince yourself
of its correctness.
Addressing your first point, the possibility that IND was already
implicitly present in the system before PHP was added is a reasonable
concern, albeit one that is beyond the scope of the chapter of the
automatatheory text it appeared in (Chapter 0: Mathematical
Preliminaries). However the proof of PHP>IND given there (which seems
canonical enough to be the standard proof of this implication) is short
enough to make it easy to see (a) what else besides PHP it depends on
and (b) that IND fails for those assumptions less PHP, which takes care
of your second concern.
F&B start with a predicate Q satisfying Q(0) and Q(i) > Q(i+1) for all
i. They then ask whether Q holds at an arbitrary m. They suppose for
a contradiction that it does not. By Q(0), m > 0. They then define
f : {x  0 <= x <= m} > {x  0 <= x <= m1} as f(x) = x or x1
according to whether Q(x) is or is not true respectively. They then
prove that f is injective by considering any two numbers i, j such that
0 <= i < j <= m.
Case 1. i <= j2 or not Q(i). Then f(i) <= j2 < f(j), so f(i) != f(j).
Case 2. i = j1 and Q(i). But then by Q(i) > Q(i+1) we have Q(j),
whence f(i) = i and f(j) = j and so f(i) != f(j).
Now PHP says this impossible, which concludes the proof. But suppose
we did not have PHP. Could we have obtained a contradiction anyway?
It is very easy to show not: just take the universe to be N+Z, the
natural numbers followed by a copy of the integers, take Q to be true
on N and false on Z, and take f to be the identity on N and predecessor
on Z. Clearly f is injective on N+Z. This setup is consistent with
everything used in the argument prior to bringing in PHP, whence there
is no inconsistency that would let us complete the proof of IND without
bringing in PHP.
This is hardly profound logic, and I can only conclude that any crybaby
complaining about PHP>IND has been bamboozled by too much wandering
around in exotic weakenings of Peano Arithmetic. My complaint would be
with AIMR>TRUE (Appears In Math Reviews).
Vaughan Pratt