Axiomatizability and decidability of universal theories of hereditary classes of models of finite and infinite languages | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 66. DOI: 10.17223/20710410/66/2

In the paper, hereditary classes of L-structures are studied with language of the form L = Lfin ∪ L∞, where Lfin = ⟨R1,R2, . . . ,Rm,=⟩ and L∞ = ⟨Rm+1,Rm+2, . . .⟩, and also in L∞ the number of predicates of each arity is finite, all predicates are ordered in ascending of their arities and satisfy the non-element repetition property. A class of L-structures is called hereditary if it is closed under substructures. It is proved that the class of L-structures is hereditary if and only if it can be defined in terms of forbidden substructures. A class of L-structures is called universally axioma-tizable if there is a set Z of universal L-sentences such that the class consists of all structures satisfying Z. The problems of the universal axiomatizability of hereditary classes of L-structures are considered in the paper. It is shown that hereditary class of L-structures is universally axiomatizable if and only if it can be defined in terms of finite forbidden substructures. It is proved that the universal theory of any axiomatizable hereditary class of L-structures with a recursive set of minimal forbidden substructures is decidable.