  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).
