Recursive axiomatisations from separation properties

DOI10.1017/JSL.2021.19MaRDI QIDQ6321264arXivFDO

Authors Robert Egrot

Publication date 29 June 2019

Published in arXiv

Full work available at URL https://doi.org/10.1017/JSL.2021.19

Mathematics Subject Classification ID

Higher-order logic (03B16) Applications of model theory (03C98) Coloring of graphs and hypergraphs (05C15) Partial algebras (08A55)

arXiv classification

cs.LOmath.LO

Abstract: We define a fragment of monadic infinitary second-order logic corresponding to an abstract separation property. We use this to define the concept of a separation subclass. We use model theoretic techniques and games to show that separation subclasses whose axiomatisations are recursively enumerable in our second-order fragment can also be recursively axiomatised in their original first-order language. We pin down the expressive power of this formalism with respect to first-order logic, and investigate some questions relating to decidability and computational complexity. As applications of these results, by showing that certain classes can be straightforwardly defined as separation subclasses, we obtain first-order axiomatisability results for these classes. In particular we apply this technique to graph colourings and a class of partial algebras arising from separation logic.

This page was built for publication: Recursive axiomatisations from separation properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321264)