6 found
Order:
  1.  97
    Definability and Undefinability with Real Order at the Background.Yuri Gurevich & Alexander Rabinovich - 2000 - Journal of Symbolic Logic 65 (2):946-958.
  2.  15
    The Full Binary Tree Cannot Be Interpreted in a Chain.Alexander Rabinovich - 2010 - Journal of Symbolic Logic 75 (4):1489-1498.
    We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  11
    Selection in the Monadic Theory of a Countable Ordinal.Alexander Rabinovich & Amit Shomrat - 2008 - Journal of Symbolic Logic 73 (3):783-816.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  36
    Selection Over Classes of Ordinals Expanded by Monadic Predicates.Alexander Rabinovich & Amit Shomrat - 2010 - Annals of Pure and Applied Logic 161 (8):1006-1023.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  5.  28
    Expressing Cardinality Quantifiers in Monadic Second-Order Logic Over Chains.Vince Bárány, Łukasz Kaiser & Alexander Rabinovich - 2011 - Journal of Symbolic Logic 76 (2):603 - 619.
    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 (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  6.  23
    On Countable Chains Having Decidable Monadic Theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
    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.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark