Kummer's Cardinality Theorem states that a language A must be
recursive if a Turing machine can exclude for any n words
w₁, …, wn one of the n + 1 possibilities for the
cardinality of {w₁,…,wn} ∩ A. There was good reason
to believe that this theorem is a peculiarity of recursion theory:
neither the Cardinality Theorem nor weak forms of it hold for
resource-bounded computational models like polynomial time. This
belief may be flawed. In this paper it is shown that weak
cardinality theorems hold for finite automata and also for other
models. An explanation is proposed as to why recursion-theoretic and
automata-theoretic weak cardinality theorems hold, but not
corresponding ‘middle-ground theorems’: The recursion- and
automata-theoretic weak cardinality theorems are instantiations of
purely logical weak cardinality theorems. The logical
theorems can be instantiated for logical structures characterizing
recursive computations and finite automata computations. A
corresponding structure characterizing polynomial time computations
does not exist.