×

Isols and the pigeonhole principle. (English) Zbl 0688.03029

This paper proves that every isolated set A satisfies the following generalized pigeonhole principle: if g: \(A\to B\) and \([A]>n[B]\), then \([g^{-1}(b)]>n\) for some \(b\in B\). ([A] denotes the recursive equivalence type of A.) However, the analogous principle, using an arbitrary isol in place of the number n, will not hold in general for isolated A - although it will hold if [A] is multiple-free. Other related notions and applications are also treated.
Reviewer: L.Harkleroad

MSC:

03D50 Recursive equivalence types of sets and structures, isols
05A15 Exact enumeration problems, generating functions
Full Text: DOI

References:

[1] DOI: 10.2307/1970338 · Zbl 0101.01203 · doi:10.2307/1970338
[2] Regressive sets and the theory of isols (1982) · Zbl 0484.03025
[3] University of California Publications in Mathematics (N.S.) 3 pp 67– (1960)
[4] DOI: 10.1305/ndjfl/1093891011 · Zbl 0245.02039 · doi:10.1305/ndjfl/1093891011
[5] Ciencia y Tecnologia, Revista de la Universidad de Costa Rica 8 pp 77– (1984)
[6] Sets, models and recursion theory pp 272– (1967)
[7] DOI: 10.1016/0003-4843(74)90002-3 · Zbl 0281.02048 · doi:10.1016/0003-4843(74)90002-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.