ECCC-Report TR94-014https://eccc.weizmann.ac.il/report/1994/014Comments and Revisions published for TR94-014en-usMon, 12 Dec 1994 00:00:00 +0200
Paper TR94-014
| The Independence of the modulo p Counting Principles |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/1994/014The 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.
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/014