6 December 2019, 10:30-11:30
ENS, S16
Order-invariant first-order logic over hollow trees.
Order-invariant first-order logic is the extension of first-order logic in which the usage of an additional ordering relation on the structure’s universe is allowed, provided that the evaluation of sentences is independent of the choice of a particular order. We show that the expressive power of order-invariant first-order logic collapses to first-order logic over hollow trees. A hollow tree is an unranked ordered tree where every non leaf node has at most four adjacent nodes: two siblings (left and right) and its first and last children. In particular there is no predicate for the linear order among siblings nor for the descendant relation. Moreover only the first and last nodes of a siblinghood are linked to their parent node, and the parent-child relation cannot be completely reconstructed in first-order.
