__
TR94-014 | 12th December 1994 00:00
__

#### The Independence of the modulo p Counting Principles

**Abstract:**
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.