Some classical model theoretic aspects of bounded shrub-depth classes
share
We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the class TM_r, p(d) of p-labeled arbitrary graphs whose underlying unlabeled graphs have tree models of height d and r labels. We show that this class satisfies an extension of the classical Löwenheim-Skolem property into the finite and for MSO. This extension being a generalization of the small model property, we obtain that the graphs of TM_r, p(d) are pseudo-finite. In addition, we obtain as consequences entirely new proofs of a number of known results concerning bounded shrub-depth classes (of finite graphs) and TM_r, p(d). These include the small model property for MSO with elementary bounds, the classical compactness theorem from model theory over TM_r, p(d), and the equivalence of MSO and FO over TM_r, p(d) and hence over bounded shrub-depth classes. The proof for the last of these is via an adaptation of the proof of the classical Lindström's theorem characterizing FO over arbitrary structures.
READ FULL TEXT