Rob Egrot

Recursive axiomatizations from separation properties

First I will describe some recent results on the axiomatizability of the class of posets that can be embedded into powerset algebras while preserving finite meets and joins (i.e. the class of representable posets). This provides a motivating example for a general theory as follows. We can a define a fragment of monadic infinitary second-order logic corresponding to a kind of abstract separation property. Using this we can define certain subclasses of elementary classes as separation subclasses (the representable posets are such a class). Using model theoretic techniques we can show that separation subclasses which are, in a sense, recursively enumerable in our second-order fragment can also be recursively axiomatized in their original first-order language. There are also some easily obtainable computability and complexity results for separation subclasses. After talking about this I'll use the general theory of separation subclasses to get easy proofs of some old results about the elementary theory of n-colourable graphs.

https://arxiv.org/abs/1907.00202