On Logics and Homomorphism Closure

Predicate logic is the premier choice for specifying classes of relational structures. Homomorphisms are key to describing correspondences between relational structures. Questions concerning the interdependencies between these two means of characterizing (classes of) structures are of fundamental interest and can be highly non-trivial to answer. We investigate several problems regarding the homomorphism closure (homclosure) of the class of all (finite or arbitrary) models of logical sentences: membership of structures in a sentence's homclosure; sentence homclosedness; homclosure characterizability in a logic; normal forms for homclosed sentences in certain logics. For a wide variety of fragments of first-and second-order predicate logic, we clarify these problems' computational properties.

2 Note that Iτ has a homomorphism into every τ -structure, and every τ -structure has a homomorphism into Fτ , i.e., Iτ → is the class of all τ -structures, whereas Fτ ∈ C → for every non-empty class C of τ -structures.

3 As = can be axiomatized in SO, we do not distinguish SO from SO = .