We study on which classes of graphs first-order logic ( fo ) and monadic second-order logic ( mso ) have the same expressive power. We show that for all classes C of graphs that are closed under taking subgraphs,  fo  and  mso  have the same expressive power on C if and only if, C has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking  induced  subgraphs, we show an analogous result for guarded second-order logic ( gso ), the variant of  mso  that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman--Vaught-type theorem that works for infinite collections of structures despite being constructive.
['Michael Elberfeld', 'Martin Grohe', 'Till Tantau']
Where First-Order and Monadic Second-Order Logic Coincide