论文标题
有界灌木深度的任意图的伪填充性
Pseudo-finiteness of arbitrary graphs of bounded shrub-depth
论文作者
论文摘要
我们考虑有界灌木深度的任意类（有限或无限）的类别，特别是$ \ mathrm {tm} _r（d）$的类，该级具有高度$ d $和$ r $ labels的树模型的任意图。 We show that the graphs of $\mathrm{TM}_r(d)$ are $\mathrm{MSO}$-pseudo-finite relative to the class $\mathrm{TM}^{\text{f}}_r(d)$ of finite graphs of $\mathrm{TM}_r(d)$;也就是说，在$ \ mathrm {tm} _r（d）$的图中，每一个$ \ mathrm {mso} $句子在$ \ mathrm {tm Mathrm {tm}^{\ text {f text {f}} _ r（d）$中也是正确的。我们还表明，$ \ mathrm {tm} _r（d）$在超庞大和超摩托车下关闭。这些结果有两个后果。首先是$ \ mathrm {MSO} [m] $ - $ \ mathrm {tm} _r（d）$在$（d+1）$ - fold off $ m $中的索引。第二个是$ \ mathrm {tm} _r（d）$恰恰是所有图形的类，这些图是$ \ mathrm {mso} $ - pseudo-finite相对于$ \ mathrm {tm}^{\ text {\ text {f text {f}}} _ r（d）$。
We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the classes $\mathrm{TM}_r(d)$ of arbitrary graphs that have tree models of height $d$ and $r$ labels. We show that the graphs of $\mathrm{TM}_r(d)$ are $\mathrm{MSO}$-pseudo-finite relative to the class $\mathrm{TM}^{\text{f}}_r(d)$ of finite graphs of $\mathrm{TM}_r(d)$; that is, that every $\mathrm{MSO}$ sentence true in a graph of $\mathrm{TM}_r(d)$ is also true in a graph of $\mathrm{TM}^{\text{f}}_r(d)$. We also show that $\mathrm{TM}_r(d)$ is closed under ultraproducts and ultraroots. These results have two consequences. The first is that the index of the $\mathrm{MSO}[m]$-equivalence relation on graphs of $\mathrm{TM}_r(d)$ is bounded by a $(d+1)$-fold exponential in $m$. The second is that $\mathrm{TM}_r(d)$ is exactly the class of all graphs that are $\mathrm{MSO}$-pseudo-finite relative to $\mathrm{TM}^{\text{f}}_r(d)$.
