EXTENSION PRESERVATION THEOREMS ON CLASSES OF ACYCLIC FINITE STRUCTURES
A class of structures satisfies the extension preservation theorem if, on this class, every first-order sentence is preserved under extensions iff it is equivalent to an existential sentence. We consider different acyclicity notions for hypergraphs (gamma-, beta-, and alpha-acyclicity and also acyclicity on hypergraph quotients) and estimate their influence on the validity of the extension preservation theorem on classes of finite structures. More precisely, we prove that the extension preservation theorem is satisfied for classes of finite structures having a gamma-acyclic k-quotient that are closed under induced substructures and disjoint unions. We show that this is not the case for classes of beta-acyclic structures. To achieve this, we make logical reductions from finite structures to their k-quotients and from gamma-acyclic hypergraphs to acyclic graphs.
preservation theorem finite model theory hypergraph acyclicity