Logics with Counting, Auxiliary Relations, and Lower Bounds for Invariant Queries

In this paper, we study the expressive power of counting logics in the presence of auxiliary relations such as orders and preorders. The simplest such logic, first-order with counting, is known to capture the uniform TC sup 0 in the presence of an order relation. We also consider first-order logic with arbitrary unary quantifiers (that can express any numerical property), and infinitary extensions. The main result of the paper is that all the counting logics above, in the presence of pre-orders that are almost everywhere linear orders, exhibit a very tame behavior normally associated with first-order expressible properties of unordered structures. This is in sharp contrast with the expressiveness of these logics in the presence of linear orders: such a tame behavior is not the case even for the first-order logic with counting, and the most powerful logic we consider can express every property of ordered structures.