Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR94-014 | 12th December 1994 00:00

The Independence of the modulo p Counting Principles


Authors: Miklos Ajtai
Publication: 12th December 1994 00:00
Downloads: 1035


The modulo $p$ counting principle is a first-order axiom
schema saying that it is possible to count modulo $p$ the number of
elements of the first-order definable subsets of the universe (and of
the finite Cartesian products of the universe with itself) in a
consistent way. It trivially holds on every finite structure. An
equivalent form of the the mod $p$ counting principle is the following:
there are no two first-order definable equivalence relations $\Phi$ and
$\Psi$ on a (first-order definable) subset $X$ of the universe $A$ (or
of $A^{i}$ for some $i=1,2,...$) with the following properties: (a)
each class of $\Phi$ contains exactly $p$ elements, and (b) each class
of $\Psi $ with one exception contains exactly $p$ elements, the
exceptional class contains $1$ element. In this paper we show that the
mod $p$ counting principles, for various prime numbers $p$, are
independent in a strong sense.

ISSN 1433-8092 | Imprint