Publication: Recursive Axiomatisations from Separation Properties
4
item.page.dc.date.issued
2021-09-03
item.page.dc.type
item.page.dc.identifier.issn
00224812
item.page.dc.identifier.doi
item.page.dc.identifier.other
2-s2.0-85121134044
item.page.dc.rights
Mahidol University
item.page.dc.rights.holder
SCOPUS
item.page.dc.identifier.citation
Journal of Symbolic Logic. Vol.86, No.3 (2021), 1228-1258
punsarn.item.page.citation
Rob Egrot Recursive Axiomatisations from Separation Properties. Journal of Symbolic Logic. Vol.86, No.3 (2021), 1228-1258. doi:10.1017/jsl.2021.19 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/75828
Research Projects
Organizational Units
Authors
Journal Issue
relationships.isThesisOf
item.page.dc.title
Recursive Axiomatisations from Separation Properties
item.page.dc.contributor.author
item.page.dc.contributor.other
item.page.dc.description.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.