Journal article

### Expressing Cardinality Quantifiers in Monadic Second−Order Logic over Trees

Abstract:

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

### Access Document

Files:
• (pdf, 234.8kb)

### Authors

Vince Barany More by this author
Lukasz Kaiser More by this author
Alexander Rabinovich More by this author
Publication date:
2010
URN:
uuid:56b6bcf9-5b6a-447b-9478-d257f1b278f7
Local pid:
cs:3583