We investigate the extension of monadic second-order logic of order with cardinality quantifiers "there exists uncountably many sets such that... " and "there exists continuum many sets such that... ". We prove that over the class of countable linear orders the two quantifiers are equivalent and can be effectively and uniformly eliminated. Weaker or partial elimination results are obtained for certain wider classes of chains. In particular, we show that over the class of ordinals the uncountability quantifier can be effectively (...) and uniformly eliminated. Our argument makes use of Shelah's composition method and Ramsey-like theorem for dense linear orders. (shrink)

Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We show that if the monadic second-order theory of a countable chain C is decidable then C has a non-trivial expansion with decidable monadic second-order theory.

A monadic formula Ψ (Y) is a selector for a formula φ (Y) in a structure M if there exists a unique subset P of μ which satisfies Ψ and this P also satisfies φ. We show that for every ordinal α ≥ ωω there are formulas having no selector in the structure (α, <). For α ≤ ω₁, we decide which formulas have a selector in (α, <), and construct selectors for them. We deduce the impossibility of a full (...) generalization of the Büchi-Landweber solvability theorem from (ω, <) to (ωw, <). We state a partial extension of that theorem to all countable ordinals. To each formula we assign a selection degree which measures "how difficult it is to select". We show that in a countable ordinal all non-selectable formulas share the same degree. (shrink)

A monadic formula ψ is a selector for a monadic formula φ in a structure if ψ defines in a unique subset P of the domain and this P also satisfies φ in . If is a class of structures and φ is a selector for ψ in every , we say that φ is a selector for φ over .For a monadic formula φ and ordinals α≤ω1 and δ<ωω, we decide whether there exists a monadic formula ψ such that (...) for every Pα of order-type smaller than δ, ψ selects φ in . If so, we construct such a ψ.We introduce a criterion for a class of ordinals to have the property that every monadic formula φ has a selector over it. We deduce the existence of Sωω such that in the structure every formula has a selector.Given a monadic sentence π and a monadic formula φ, we decide whether φ has a selector over the class of countable ordinals satisfying π, and if so, construct one for it. (shrink)

We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C.