On the Expressive Power of First Order Logic Extended with the Betweenness Relation

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 H<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> of 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 H<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</inf> of finite 3-chromatic graphs remain non-elementary in FOLB, that is H<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</inf> is not finitely axiomatizable in FOLB (in fact, we shall show that H<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</inf> is 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.