Counting Quantifiers on Automatic Structures

In chapter 2 we asked how first-order logic can be extended and analyzed using infinitary logic, which lead us to the regular game quantifier and to clarifying the connection to games.

In this chapter we consider extensions of first-order logic in another direction, by generalized unary quantifiers. As usual, we require these extensions to preserve regularity on automatic structures. It turns out that the only generalized unary quantifiers with this property are the counting quantifiers:

the

modulo counting quantifiers

“there exist k mod

m

many”,

the

infinity quantifier

“there exist infinitely many”, and

the

uncountability quantifier

“there exist uncountably many”.

While it is known that all counting quantifiers indeed preserve regularity over finite-word automatic structures, and even over injectively presented

ω

- automatic structures, this was open for general

ω

-automatic structures. Our proof [10] uses

ω

-semigroups and leads to an additional corollary that all countable

ω

-automatic structures have injective presentations. It follows that countable

ω

-automatic structures have automatic presentations over finite words, which answers a question of Blumensath [11].