Count(q) versus the pigeon-hole principle

For each there exists a model of which satisfies the Count() principle. Furthermore, if contains all prime factors of there exist and a bijective map mapping onto . A corollary is a complete classification of the Count() versus Count() problem. Another corollary shows that the pigeon-hole principle for injective maps does not follow from any of the Count() principles. This solves an open question [Ajtai 94]. Received August 16, 1994 / Revised version received April 29, 1996