Almost Everywhere Equivalence of Logics in Finite Model Theory
Lauri Hella, Phokion G. Kolaitis, Kerkko Luosto · Bulletin of Symbolic Logic · 1996
Abstract We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept ofalmost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, ifL, L′are two logics andμis an asymptotic measure on finite structures, thenL≡a.e.L′(μ) means that there is a classCof finite structures withμ(C)= 1 and such thatLandL′define the same queries onC. We carry out a systematic investigation of ≡a.e.with respect to the uniform measure and analyze the ≡a.e.-equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework.