When no single universal model for a set of structures exists at a given cardinal, then one may ask in which models of set theory does there exist a small family which embeds the rest. We show that for λ+-graphs (λ regular) omitting cliques of some finite or uncountable cardinality, it is consistent that there are small universal families and 2λ > λ+. In particular, we get such a result for triangle-free graphs.

Our theme is that not every interesting question in set theory is independent of ZFC. We give an example of a first order theory T with countable D(T) which cannot have a universal model at ℵ1 without CH; we prove in ZFC a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove--again in ZFC--that for a large class of cardinals there is no universal linear order (e.g. in every regular $\aleph_1 < (...) \lambda < 2^{\aleph_0}$). In fact, what we show is that if there is a universal linear order at a regular λ and its existence is not a result of a trivial cardinal arithmetical reason, then λ "resembles" ℵ1--a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the nonexistence of a universal linear order, we show the nonexistence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras, p-adic rings and fields, partial orders, models of PA and so on). (shrink)

We survey the use of club guessing and other PCF constructs in the context of showing that a given partially ordered class of objects does not have a largest, or a universal, element.

It is consistent with ¬CH that every universal theory of relational structures with the joint embedding property and amalgamation for P --diagrams has a universal model of cardinality ℵ 1. For classes with amalgamation for P --diagrams it is consistent that $2^{\aleph_0} > \aleph_2$ and there is a universal model of cardinality ℵ 2.

We show that if κ is a weakly compact cardinal then the embeddability relation on trees of size κ is invariantly universal. This means that for every analytic quasi-order R on the generalized Cantor space View the MathML source there is an Lκ+κ-sentence φ such that the embeddability relation on its models of size κ, which are all trees, is Borel bi-reducible to R. In particular, this implies that the relation of embeddability on trees of size κ is complete for (...) analytic quasi-orders on View the MathML source. These facts generalize analogous results for κ=ω obtained in Louveau and Rosendal [17] and Friedman and Motto Ros [6], and it also partially extends a result from Baumgartner [3] concerning the structure of the embeddability relation on linear orders of size κ. (shrink)

We get consistency results on I(λ, T 1 , T) under the assumption that D(T) has cardinality $>|T|$ . We get positive results and consistency results on IE(λ, T 1 , T). The interest is model-theoretic, but the content is mostly set-theoretic: in Theorems 1-3, combinatorial; in Theorems 4-7 and 11(2), to prove consistency of counterexamples we concentrate on forcing arguments; and in Theorems 8-10 and 11(1), combinatorics for counterexamples; the rest are discussion and problems. In particular: (A) By Theorems (...) 1 and 2, if $T \subseteq T_1$ are first order countable, T complete stable but ℵ 0 -unstable, $\lambda > \aleph_0$ , and $|D(T)| > \aleph_0$ , then $IE(\lambda, T_1, T) \geq \operatorname{Min}\{2^\lambda, \beth_2\}$ . (B) By Theorems 4, 5, 6 of this paper, if e.g. V = L, then in some generic extension of V not collapsing cardinals, for some first order $T \subseteq T_1, |T| = \aleph_0, |T_1| = \aleph_1, |D(T)| = \aleph_2$ and IE(ℵ 2 , T 1 , T) = 1. This paper (specifically the ZFC results) is continued in the very interesting work of Baldwin on diversity classes [B1]. Some more advances can be found in the new version of [Sh300] (see Chapter III, mainly \S7); they confirm 0.1, 0.2 and 14(1), 14(2). (shrink)

We show that if κ is a weakly compact cardinal then the embeddability relation on trees of size κ is invariantly universal. This means that for every analytic quasi-order R on the generalized Cantor space View the MathML source there is an Lκ+κ-sentence φ such that the embeddability relation on its models of size κ, which are all trees, is Borel bi-reducible to R. In particular, this implies that the relation of embeddability on trees of size κ is complete for (...) analytic quasi-orders on View the MathML source. These facts generalize analogous results for κ=ω obtained in Louveau and Rosendal [17] and Friedman and Motto Ros [6], and it also partially extends a result from Baumgartner [3] concerning the structure of the embeddability relation on linear orders of size κ. (shrink)

This paper will examine universality spectra for relational theories which cannot be described in first-order logic. We will give a method using functors to show that two types of structures have the same universality spectrum. A combination of methods will be used to show universality results for certain ordered structures and graphs. In some cases, a universal spectrum under GCH will be obtained. Since the theories are not first-order, the classic model theory result under GCH does not hold.

Suppose that λ=λ <λ ≥ℵ0, and we are considering a theory T. We give a criterion on T which is sufficient for the consistent existence of λ++ universal models of T of size λ+ for models of T of size ≤λ+, and is meaningful when 2λ +>λ++. In fact, we work more generally with abstract elementary classes. The criterion for the consistent existence of universals applies to various well known theories, such as triangle-free graphs and simple theories. Having in mind (...) possible applications in analysis, we further observe that for such λ, for any fixed μ>λ+ regular with μ=μλ+, it is consistent that 2λ=μ and there is no normed vector space over ℚ of size <μ which is universal for normed vector spaces over ℚ of dimension λ+ under the notion of embedding h which specifies (a,b) such that ||h(x)/||x∈(a,b) for all x. (shrink)