Testable and untestable classes of first-order formulae (Q440006)

This article studies property testing which identifies structures which may have a desired property, and the classification of logic sentences according to their testability. The article begins with an introduction and a historic background to property testing, followed by a summary of the main contribution of this article, which proves that all relational properties that begin with the logic prefix \(\exists^{*}\forall\exists^{*}\) are testable. The second section contains a large number of necessary background definitions and preliminary theorems which are necessary for proving the main results. The proof of the main result follows in the third section. The next two sections, Sections 4 and 5, concentrate on the classification of testable and untestable classes, respectively. This includes a proof that Ackermann's first-order class and Ramsey's class are testable, and provide a more simple example, compared to \(\forall^{12}\exists^{5}\), of an untestable class. This very interesting article concludes with a summary of the contributions and a useful list of relevant references.