Testable and untestable classes of first-order formulae

In property testing, the goal is to distinguish structures that have some desired property from those that are far from having the property, based on only a small, random sample of the structure. We focus on the classification of first-order sentences according to their testability. This classification was initiated by Alon et al. (2000) [2], who showed that graph properties expressible with prefix ∃⁎∀⁎∃⁎∀⁎ are testable but that there is an untestable graph property expressible with quantifier prefix ∀⁎∃⁎∀⁎∃⁎. The main results of the present paper are as follows. We prove that all (relational) properties expressible with quantifier prefix ∃⁎∀∃⁎∃⁎∀∃⁎ (Ackermannʼs class with equality) are testable and also extend the positive result of Alon et al. (2000) [2] to relational structures using a recent result by Austin and Tao (2010) [8]. Finally, we simplify the untestable property of Alon et al. (2000) [2] and show that prefixes ∀3∃∀3∃, ∀2∃∀∀2∃∀, ∀∃∀2∀∃∀2 and ∀∃∀∃∀∃∀∃ can express untestable graph properties when equality is allowed.

► We deal with the logical classification of testability. ► We examine the testability of prefix-vocabulary classes of first-order logic. ► We prove that Ackermannʼs class with equality is testable with one-sided error. ► We show that Ramseyʼs class is testable. ► We show that there are untestable properties expressible with four quantifiers.