5 found
Sort by:
  1. Shmuel Lifsches & Saharon Shelah (1999). Random Graphs in the Monadic Theory of Order. Archive for Mathematical Logic 38 (4-5):273-312.
    We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line).
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Shmuel Lifsches & Saharon Shelah (1998). Uniformization and Skolem Functions in the Class of Trees. Journal of Symbolic Logic 63 (1):103-127.
    The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have definable Skolem functions (by a monadic formula with parameters)? This continues [6] where the question was asked only with respect to choice functions. A natural subclass is defined and proved to be the class of trees with definable Skolem functions. Along the way we investigate the spectrum of definable well orderings (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  3. Shmuel Lifsches & Saharon Shelah (1997). Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders. Journal of Symbolic Logic 62 (3):848-872.
    Gurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. Shmuel Lifsches & Saharon Shelah (1996). Uniformization, Choice Functions and Well Orders in the Class of Trees. Journal of Symbolic Logic 61 (4):1206-1227.
    The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have a definable choice function (by a monadic formula with parameters)? A natural dichotomy arises where the trees that fall in the first class don't have a definable choice function and the trees in the second class have even a definable well ordering of their elements. This has a close connection to (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  5. Shmuel Lifsches & Saharon Shelah (1992). The Monadic Theory of (Ω 2, <) May Be Complicated. Archive for Mathematical Logic 31 (3):207-213.
    Assume ZFC is consistent then for everyB⫅ω there is a generic extension of the ground world whereB is recursive in the monadic theory ofω 2.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation