The independence of the modulo p counting principles
Miklós Ajtai · 1994
If p is a prime and n is a positive integer then the mod p counting principle for n (CPp,n ) is the following statement: there are no two equivalence relations @ and @ on a set A of size n with the following properties: (a) each class of@ cent ains exactly p elements, and (b) each class of IO with one exception contains exactly p elements, the exceptional class contains 1 element.We will always assume that p is constant and n is sufficiently large.If we associate Boolean variables x ~, b, ya, b with all pairs formed from the elements of A then CPP,n can be expressed as a Boolean formula of constant depth and polynomial size.(We may think that a@b iff xa, h = 1, aQb iff Ya,b = 1.)This formula is a tautology.We show that if p, q are distinct primes then there is no constant depth polynomial (in n) size Frege proof of CF'P,n even if we are allowed to use CF'q,n as an axiom schema.(We get the axiom schema from C'Pg,n by replacing in every possible way the variables in G'pq,n by constant depth polynomial size fromulae formed from the variables used in the Frege proof.This schema says the if we define the partitions 0, W in an arbi-