4 found
Order:
  1.  85
    Uniformization, Choice Functions and Well Orders in the Class of Trees.Shmuel Lifsches & Saharon Shelah - 1996 - 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 (8 more)  
     
    Export citation  
     
    Bookmark  
  2.  28
    Random Graphs in the Monadic Theory of Order.Shmuel Lifsches & Saharon Shelah - 1999 - 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).
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  39
    Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders.Shmuel Lifsches & Saharon Shelah - 1997 - 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 (9 more)  
     
    Export citation  
     
    Bookmark  
  4.  14
    The Monadic Theory of (Ω 2, <) May Be Complicated.Shmuel Lifsches & Saharon Shelah - 1992 - 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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark