Random graphs in the monadic theory of order

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). Received: 18 July 1996     

There are no infinite order polynomially complete lattices, after all

If L is a lattice with the interpolation property whose cardinality is a strong limit cardinal of uncountable cofinality, then some finite power has an antichain of size . Hence there are no infinite opc lattices. However, the existence of strongly amorphous sets implies (in ZF) the existence of infinite opc lattices. Received November 2, 1998; accepted in final form March 19, 1999.     

Categoricity of an abstract elementary class in two successive cardinals

We investigate categoricity of abstract elementary classes without any remnants of compactness (like non-definability of well ordering, existence of E.M. models, or existence of large cardinals). We prove (assuming a weak version of GCH around λ) that if ℜ is categorical in λ, λ⁺,LS(ℜ) ≤ λ and has intermediate number of models in λ⁺⁺,then ℜ has a model in λ⁺⁺⁺. Partially supported by the United States-Israel Binational Science Foundation. I thank Alice Leonhardt for the excellent typing. Publication No. 576.     

More on the weak diamond

We prove that e.g., 2^?₁<2^?₂ does not imply the weak diamond for {δ<?₂:cf δ=?₀ (even if CH holds).     

Countably decomposable admissible sets

The known results about Σ₁-completeness, Σ₁-compactness, ordinal omitting etc. are given a unified treatment, which yields many new examples. It is shown that the unifying theorem is best possible in several ways, assuming V = L.     

A consistent counterexample in the theory of collectionwise Hausdorff spaces

It is shown to be consistent that there is a normal first countable locally countable space which is not collectionwise Hausdorff and in which there is a closed discrete non-G _δ set which provides the counterexample to collectionwise Hausdorffness. This answers a question of P. Nyikos. Publication 349, partially supported by the BSF.     

Karp complexity and classes with the independence property

A class K of structures is controlled if for all cardinals λ, the relation of L_∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that no pseudo-elementary class with the independence property is controlled. By contrast, there is a pseudo-elementary class with the strict order property that is controlled (see Arch. Math. Logic 40 (2001) 69–88).     

Almost isometric embedding between metric spaces

We investigate the relations ofalmost isometric embedding and ofalmost isometry between metric spaces. These relations have several appealing features. For example, all isomorphism types of countable dense subsets of ∝ form exactly one almostisometry class, and similarly with countable dense subsets of Uryson's universal separable metric spaceU. We investigate geometric, set-theoretic and model-theoretic aspects of almost isometry and of almost isometric embedding. The main results show that almost isometric embeddability behaves in the category ofseparable metric spaces differently than in the category of general metric spaces. While in the category of general metric spaces the behavior of universality resembles that in the category of linear orderings —namely, no universal structure can exist on a regular λ > ℵ₁ below the continuum—in the category of separable metric spaces universality behaves more like that in the category of graphs, that is, a small number of metric separable metric spaces on an uncountable regular λ<2^ℵ ₀ may consistently almost isometrically embed all separable metric spaces on λ. Research of the first author was supported by an Israeli Science foundation grant no. 177/01. Research of the second author was supported by the United States-Israel Binational Science Foundation. Publication 827.