一句话:给出序理论树中介于关系的 MSO 公理化,并证明拟树上的诱导介于关系可由一阶语句刻画。
树的三元 betweenness 关系 B(x,y,z) 表示 y 在 x 与 z 的唯一路径上。本文将其推广到序理论树:任意节点的上集为全序的偏序,此时两节点间路径可有无限多节点。前人针对 join-tree(任意两节点有最小上界)的 betweenness 定义了 quasi-tree,并给出一阶公理化,动机是定义可数图的 rank-width。本文得到序理论树中 betweenness 的 monadic second-order 公理化;定义并比较若干诱导 betweenness 关系,即不同广义树中 betweenness 对节点子集的限制;并证明 quasi-tree 中诱导 betweenness 可由一阶语句刻画,证明借助序理论树。
The ternary betweenness relation of a tree, B(x,y,z) expresses that y is on the unique path between x and z. This notion can be extended to order-theoretic trees defined as partial orders such that the set of nodes larger than any node is linearly ordered. In such generalized trees, the unique "path" between two nodes can have infinitely many nodes. We generalize some results obtained in a previous article for the betweenness of join-trees. Join-trees are order-theoretic trees such that any two nodes have a least upper-bound. The motivation was to define conveniently the rank-width of a countable graph. We called quasi-tree the structure based on the betweenness relation of a join-tree. We proved that quasi-trees are axiomatized by a first-order sentence. Here, we obtain a monadic second-order axiomatization of betweenness in order-theoretic trees. We also define and compare several induced betweenness relations, i.e., restrictions to sets of nodes of the betweenness relations in generalized trees of different kinds. We prove that induced betweenness in quasi-trees is characterized by a first-order sentence. The proof uses order-theoretic trees.