First-order expressibility of languages with neutral letters or: The Crane Beach conjecture

We investigate the CBC in detail, showing that it fails for N={+,×}, or, possibly stronger, for any set N that allows counting up to the m times iterated logarithm, for any constant m. On the positive side, we prove the conjecture for the case of all monadic numerical predicates, for the addition predicate +, for the fragment BC(Σ1) of first-order logic, for regular languages, and for languages over a binary alphabet. We explain the precise relation between the CBC and so-called natural-generic collapse results in database theory. Furthermore, we introduce a framework that gives better understanding of what exactly may cause a failure of the conjecture.