Defining algorithmically presented structures in first order logic

We aim to describe the isomorphism types of infinite structures in the language of first-order logic. This pursuit holds importance in logic in computer science, encompassing model theory, descriptional complexity, and the foundations of computability. We introduce the notion of quasi-axiomatizability aimed at describing the isomorphism types of structures. Our focus centers on two classes of algorithmically presented structures. The first is the class of structures for which the positive atomic diagrams are computably enumerable. We call these structures positive structures. The second is the class of structures for which the negative atomic diagrams are computably enumerable. We call these structures negative structures. We study quasi-axiomatizability of structures from these classes by ∃, ∀, ∃∀, and ∀∃-sentences in expansions of languages. Our work is a contribution to the interplay between expressive power of first-order logic, computability, and model theory.

Ҳали таржима қилинмаган