On the Expressive Power of First Order Logic Extended with the Betweenness Relation
Gábor Sági · 2024
Inspired by geometry, some authors add the so called ternary betweenness relation to the first order language of graphs, the so obtained logic is called First Order Logic with Betweenness (FOLB for short). This extension enhances the expressive power of first order logic and certain classes of finite graphs become finitely axiomatizable in FOLB. In particular, in [1] it was shown that the class H2of finite 2-chromatic graphs (that is, the class of finite bipartite graphs) is finitely axiomatizable in FOLB.The main result of this work is to prove, that the class H3of finite 3-chromatic graphs remain non-elementary in FOLB, that is H3is not finitely axiomatizable in FOLB (in fact, we shall show that H3is not finitely axiomatizable in FOLB even if we allow finite models only). To prove this, we use ultraproducts, which is a classical construction in the model theory of first order logics.