5.3 Monadic second-order logic and recognizability

This section is devoted to the proof of the Recognizability Theorem, a corner-stone of the theory developed in this book. Informally, *every* CMS*-definable set of graphs or of relational structures is recognizable* with respect to an appropriate algebra.

The most technical part of the proof (in the next section) is that of the Splitting Theorem for , the union of disjoint graphs or structures. This theorem says that, for every MS formula *φ*, the set of assignments that satisfy *φ* in the union of two disjoint structures *S* and *T* can be determined from the sets of those that satisfy auxiliary formulas ...

Start Free Trial

No credit card required