Indistinguishability and First-Order Logic

Authors: Skip Jordan and Thomas Zeugmann

Source: Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 2008, Proceedings , (Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, Eds.), Lecture Notes in Computer Science 4978, pp. 94-104, Springer 2008.

Abstract. The “richness” of properties that are indistinguishable from first-order properties is investigated. Indistinguishability is a concept of equivalence among properties of combinatorial structures that is appropriate in the context of testability. All formulas in a restricted class of second-order logic are shown to be indistinguishable from first-order formulas. Arbitrarily hard properties, including RE-complete properties, that are indistinguishable from first-order formulas are shown to exist. Implications on the search for a logical characterization of the testable properties are discussed.