论文标题
一些经典模型的理论方面有界灌木深度类别
Some classical model theoretic aspects of bounded shrub-depth classes
论文作者
论文摘要
我们考虑有界灌木深度的任意（有限或无限）图的类别，特别是$ \ Mathrm {tm} _ {r，p} _ {r，p}（d）$ $ p $ p $ bug $ p $的任意图，其基础未标记的未标记图具有高度$ d $ d $ d $ $ r $ $ $ $ $ $ $ $ r $ $ $ r $ $ $。我们表明，此类可以满足经典的Löwenheim-Skolem属性的扩展，并以$ \ Mathrm {MSO} $延长。该扩展是对小型模型属性的概括，我们获得了$ \ mathrm {tm} _ {r，p}（d）$的图形。此外，我们获得了有关许多已知结果（有限图）和$ \ mathrm {tm} _ {r，p}（d）$的已知结果的全新证明。其中包括$ \ mathrm {MSO} $的小型属性，具有基本界限，$ \ Mathrm {tm} _ {r，p}（d）$的模型理论的经典紧凑定理，以及$ \ mso {mso} $} $ and $ \ mathrm {fo} $ {fo} $ { p}（d）$，因此在有限的灌木深度类别上。最后的证明是通过改编经典的Lindström定理的证明，以任意结构来表征$ \ mathrm {fo} $。
We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the class $\mathrm{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 $\mathrm{MSO}$. This extension being a generalization of the small model property, we obtain that the graphs of $\mathrm{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 $\mathrm{TM}_{r, p}(d)$. These include the small model property for $\mathrm{MSO}$ with elementary bounds, the classical compactness theorem from model theory over $\mathrm{TM}_{r, p}(d)$, and the equivalence of $\mathrm{MSO}$ and $\mathrm{FO}$ over $\mathrm{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 $\mathrm{FO}$ over arbitrary structures.
