Name
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 is based on Shelah's composition method and uses basic results from descriptive set theory. The elimination result is constructive, yielding a decision procedure for the extended logic. Furthermore, by the well-known correspondence between monadic second-order logic and tree automata, our findings translate to analogous results on the extension of first-order logic by cardinality quantifiers over injectively presentable Rabin-automatic structures, generalizing the work of Kuske and Lohrey. |
Year | Venue | Keywords |
|---|---|---|
2009 | CSL | sets definable,analogous result,monadic second-order logic,continuum hypothesis,plain monadic second-order logic,composition method,extended logic,cardinality quantifiers,basic result,first-order logic,descriptive set theory |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Second-order logic,Zeroth-order logic,Cardinality,Linear temporal logic,Descriptive set theory,Predicate logic,Monadic predicate calculus,Higher-order logic,Mathematics | Conference | 5771 |
ISSN | ISBN | Citations |
0302-9743 | 3-642-04026-8 | 2 |
PageRank | References | Authors |
0.43 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vince Bárány | 1 | 88 | 9.23 |
| Łukasz Kaiser | 2 | 2307 | 89.08 |
| Alexander Rabinovich | 3 | 68 | 4.89 |