Axiomatisability and hardness for universal Horn classes of hypergraphs

摘要

We consider hypergraphs as symmetric relational structures. In this setting, we characterise finite axiomatisability for finitely generated universal Horn classes of loop-free hypergraphs. An Ehrenfeucht-Fraiss'e game argument is employed to show that the results continue to hold when restricted to first order definability amongst finite structures. We are also able to show that every interval in the homomorphism order on hypergraphs contains a continuum of universal Horn classes and conclude the article by characterising the intractability of deciding membership in universal Horn classes generated by finite loop-free hypergraphs.