Axiomatizability and decidability of universal theories of hereditary classes of models of finite and infinite languages

A. V. Ilev

Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 14-29.

Résumé

In the paper, hereditary classes of ${\rm L}$‑structures are studied with language of the form ${{\rm L} = {\rm L_{fin}} \cup {\rm L_\infty}}$, where ${{\rm L_{fin}} = \langle R_1,R_2,\ldots, R_m, = \rangle}$ and ${{\rm L_\infty} = \langle R_{m+1}, R_{m+2}, \ldots \rangle}$, and also in ${\rm L_\infty}$ 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 ${\rm L}$‑structures is called hereditary if it is closed under substructures. It is proved that the class of ${\rm L}$‑structures is hereditary if and only if it can be defined in terms of forbidden substructures. A class of ${\rm L}$‑structures is called universally axiomatizable if there is a set $Z$ of universal ${\rm L}$‑sentences such that the class consists of all structures satisfying $Z$. The problems of the universal axiomatizability of hereditary classes of ${\rm L}$‑structures are considered in the paper. It is shown that hereditary class of ${\rm 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 ${\rm L}$‑structures with a recursive set of minimal forbidden substructures is decidable.

Détail

Mots-clés : structure
Keywords: hereditary class, universal theory, universal axiomatizability, decidability.

Bibliographie

[1] Il'ev A. V. and Il'ev V. P., “Algorithms for solving systems of equations over various classes of finite graphs”, Prikladnaya Diskretnaya Matematika, 2021, no. 53, 89–102 (In Russian) | Zbl

[2] Nikitin A. Yu. and Rybalov A. N., “On complexity of the satisfiability problem of systems over finite posets”, Prikladnaya Diskretnaya Matematika, 2018, no. 39, 94–98 (In Russian) | Zbl

[3] Baldzhanova R. V., Il'ev A. V., and Il'ev V. P., “On the complexity of graph clustering in the problem with bounded cluster sizes”, Prikladnaya Diskretnaya Matematika, 2023, no. 60, 76–84 (In Russian) | MR | Zbl

[4] Il'ev A. V. and Il'ev V. P., “Bounds for the clustering complexity in a graph clustering problem with clusters of bounded size”, J. Math. Sci., 275 (2023), 78–84 | DOI | MR | Zbl

[5] Zykov A. A., Fundamentals of Graph Theory, Vuzovskaia kniga, M., 2004, 664 pp. (In Russian)

[6] Ershov Yu. L., Lavrov I. A., Taimanov A. D., and Taitslin M. A., “Elementary theories”, Russian Math. Surveys, 20:4 (1965), 35–105 | DOI | MR | Zbl

[7] Bozapalidis A. and Kalampakas A., “An axiomatization of graphs”, Acta Inform., 41 (2004), 19–61 | DOI | MR | Zbl

[8] Taylor W., “Atomic compactness and graph theory”, Fundamenta Mathematicae, LXV (1969), 139–145 | DOI | MR | Zbl

[9] Yamamoto M., Nishizaki S., Hagiya M., and Toda Y., “Formalization of planar graphs”, LNCS, 971, 1995, 369–384 | MR | Zbl

[10] Caicedo X., “Finitely axiomatizable quasivarieties of graphs”, Algebra Univers., 34:2 (1995), 314–321 | DOI | MR | Zbl

[11] Il'ev A. V., “On axiomatizability of hereditary classes of graphs and matroids”, Siberian Electronic Math. Reports, 13 (2016), 137–147 (In Russian) | Zbl

[12] Ham L. and Jackson M., “Axiomatisability and hardness for universal Horn classes of hypergraphs”, Algebra Univers., 79 (2018), 30 | DOI | MR | Zbl

[13] Il'ev A. V. and Il'ev V. P., “On axiomatizability and decidability of universal theories of hereditary classes of matroids”, J. Physics: Conf. Ser., 1210 (2019), 012056 | DOI

[14] Stronkowski M. M., “Axiomatizations of universal classes through infinitary logic”, Algebra Univers., 79 (2018), 26 | DOI | MR | Zbl

[15] Ershov Yu. L. and Palyutin E. A., Mathematical Logic, Nauka, M., 1987, 336 pp. (In Russian) | MR

[16] Gorbunov V. A., Algebraic Theory of Quasivarieties, Plenum, New York, 1998, 298+xii pp. | MR

[17] Il'ev A. V., “Decidability of universal theories and axiomatizability of hereditary classes of graphs”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 22, no. 1, 2016, 100–111 (In Russian)