Count(q) versus the Pigeon-Hole Principle

Abstract

For each p <= 2 there exist a model M* of IDelta_{0}(alpha) which satisfies the Count(p) principle. Furthermore if p contain all prime factors of q there exist n, r in M* and a bijective map f in Set(M*) mapping {1, 2, ..., n} onto {1,2,...,n+q^r}.

A corollary is a complete classification of the Count(q) versus Count(p) problem. Another corollary solves an open question by M. Ajtai.