Existential monadic second order logic on random rooted trees

We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO....

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2019-01, Vol.342 (1), p.152-167
Main Authors: Holroyd, Alexander E., Levy, Avi, Podder, Moumanti, Spencer, Joel
Format: Article
Language:English
Subjects:
Almost sure expressibility
Existential monadic second order properties
Finiteness of tree
Galton–Watson tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton–Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2018.09.012