Positive Primitive Structures
Boris A. Romov
We investigate a positive primitive formula closure (formed by (∃, &, =)- formulas) in countable structures which establishes an algebraic framework for Constraint Satisfaction Problems on a countable set. The main question under consideration is the characterization of countable structures, called positive primitive, in which, similar to a finite case, such closure coincides with the Galois closure on predicates invariant to all polymorphisms of those structures. Next we establish criteria for existential quantifier elimination in positive primitive formulas.
Keywords: Galois connection, positive primitive formula, partial polymorphism, extendable partial clone, constraint satisfaction problem, elimination set.