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 Message-ID: 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.6-22). Most informal "proofs" of equivalence of well-ordering, 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 04-01 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. 183--186, Congress. Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980. --------------------------------------------------------------------------- The authors argue very informally that the pigeonhole principle can replace the induction axiom or the well-ordering 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 well-ordering principle, but not the induction axiom or the pigeonhole principle; (2) the class of all cardinals satisfies the first four Peano postulates, the well-ordering 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. (1-PRLS); 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, 129--131. ----------------------------------------------------------------------------- Informal set-theoretic 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 Zermelo-Fraenkel 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. 1-2, 69--76; 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 Well-Ordering Property? ... | | The well-ordering 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 well-ordering 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 Pigeon-Hole 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 Pigeon-Hole Principle (rare > in that neck of the woods). The paper was returned to him, and the ref had > written "What is the Pigeon-Hole Principle?" > > Is the PHP really that non-standard? 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, 147--153. 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 proof-length in propositional systems, e.g. Ajtai, M. (1-IBM2) The complexity of the pigeonhole principle. Combinatorica 14 (1994), no. 4, 417--433. MR 96a:03065 03F20 Here are some other useful references culled from MathSciNet: Erickson, Martin (1-NMOS) An introduction to combinatorial existence theorems. Math. Mag. 67 (1994), no. 2, 118--123. 95e:05004 05A05 05C55 Graham, N. (1-NMS-CL); Entringer, R. C. (1-NM); Szekely, L. A. (H-EOTVO-C) New tricks for old trees: maps and the pigeonhole principle. Amer. Math. Monthly 101 (1994), no. 7, 664--667. MR 95m:05144 05C38 05C05 Hutchinson, Joan P.; Trow, Paul B. Some pigeonhole principle results extended. Amer. Math. Monthly 87 (1980), no. 8, 648--651. MR 82g:05016 05A99 Swanson, Leonard G. (1-PRLS); Hansen, Rodney T. The equivalence of the multiplication, pigeonhole, induction, and well ordering principles. Internat. J. Math. Ed. Sci. Tech. 19 (1988), no. 1, 129--131. MR 89e:03084 03E20 von der Twer, T. On the strength of several versions of Dirichlet's ("pigeon-hole"-) principle in the sense of first-order logic. Arch. Math. Logik Grundlag. 21 (1981), no. 1-2, 69--76. 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 Message-ID: <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 well-ordering, 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 <= m-1} 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 automata-theory 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 <= m-1} as f(x) = x or x-1 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 <= j-2 or not Q(i). Then f(i) <= j-2 < f(j), so f(i) != f(j). Case 2. i = j-1 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