We study an extension of monadic second-order logic of order with the uncountability quantifier ``there exist uncountably many sets''. We prove that, over the class of finitely branching trees, this extension is equally expressive to plain monadic second-order logic of order. Additionally we find that the continuum hypothesis holds for classes of sets definable in monadic second-order logic over finitely branching trees, which is notable for not all of these classes are analytic. Our approach...Expand abstract
- In Proceedings of the 18th Annual Conference of the European Association for Computer Science Logic‚ CSL '09.
- Publication date:
- Local pid:
- Copyright date: