Count(q) does not imply Count(p) - Riis, Søren (BRICS Report Series, 1994)
I solve a conjecture originally studied by M.Ajtai. It states that for different primes q, p the matching principles Count(q) and Count(p) are logically independent. I prove that this indeed is the case. Actually I show that Count(q) implies Count(p) exactly when each prime in p also is a factor in q.