__
TR03-024 | 25th February 2003 00:00
__

#### Weak Cardinality Theorems for First-Order Logic

**Abstract:**
Kummer's cardinality theorem states that a language is recursive

if a Turing machine can exclude for any n words one of the

n + 1 possibilities for the number of words in the language. It

is known that this theorem does not hold for polynomial-time

computations, but there is evidence that it holds for finite

automata: at least weak cardinality theorems hold for finite

automata. This paper shows that some of the recursion-theoretic

and automata-theoretic weak cardinality theorems are

instantiations of purely logical theorems. Apart from unifying

previous results in a single framework, the logical approach

allows us to prove new theorems for other computational models.

For example, weak cardinality theorems hold for Presburger

arithmetic.