3 citations · 5 across the 5 of their papers we have counts for
5 papers · 1 filter
Random graphs in the monadic theory of order
Shmuel Lifsches, Saharon Shelah
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 mona…
Distorted sums of models
Shmuel Lifsches, Saharon Shelah
Distorted sums of models were introduced and discussed in [Sh:463]. This notion generalizes the notion of disjoint (or direct) sums of models by letting the summands overlap. In th…
Uniformization and Skolem functions in the class of trees
Shmuel Lifsches, Saharon Shelah
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…
Uniformization, choice functions and well orders in the class of trees
Shmuel Lifsches, Saharon Shelah
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…
Peano Arithmetic may not be interpretable in the monadic theory of orders
Shmuel Lifsches, Saharon Shelah
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…