Universal graphs and functions on \(\omega_1\) (Q2033005)

An important question in model theory and, to some extent in set theory, is the following. If \(K\) is a class of structures axiomatized by a complete first-order theory, when does \(K\) have a universal model of cardinality \(\kappa\)? A structure \(A\) in \(K\) is universal in size \(\kappa\) when \(A\) has cardinality \(\kappa\) and any member of \(K\) of size \(\leq\kappa\) can be embedded in \(A\). It is known that the corresponding question for saturated models depends on stability and cardinal arithmetic. For universal models the situation is not clear. The notion of a universal structure depends on the class under study. If we consider models of a complete first-order theory, an embedding is an elementary embedding; in case of models of a universal theory, an embedding is an embedding as a substructure. A now classical result in model theory establishes that countably saturated models are universal for models of cardinality \(\aleph_1\). In the case of graphs, the existence of saturated models is equivalent to CH. In [\textit{A. H. Mekler}, J. Symb. Log. 55, No. 2, 466--477 (1990; Zbl 0702.03028)], it is shown that it is consistent with \(\neg \mathrm{CH}\) that every universal theory of relational structures with the JEP and strong amalgamation properties has a universal model of size \(\aleph_1\). In [\textit{S. Shelah}, Ann. Pure Appl. Logic 26, 75--87 (1984; Zbl 0551.03032); Isr. J. Math. 70, No. 1, 69--81 (1990; Zbl 0709.03039)], the consistency of the existence of a universal graph of power \(\lambda\) is proved, where \(\kappa=\kappa^{<\kappa}=\operatorname{cf}(\lambda)< 2^\kappa\) are arbitrary. The non-existence of a universal model in \(\lambda\), it is guaranteed by forcing. Indeed, by adding \(\aleph_2\) Cohen reals any non-\(\aleph_0\)-stable countable theory \(T\) lacks of universal model in \(\aleph_1\); if \(\lambda=\lambda^{<\lambda}\) and we add \(\mu\) Cohen subsets of \(\lambda\), no unstable theory \(T\) has a universal model in any cardinality \(\rho\in(\lambda,\mu)\). In the paper under review, the authors show that the existence of a universal graph on \(\aleph_1\) is consistent with several values of \(\mathfrak{b}\), \(\mathfrak{d}\) and \(2^{\aleph_1}\). A function \(U:X^2\to X\) is said to be (Sierpinśki) universal if for any \(G:X^2\to X\) there is an \(e:X\to X\) such that \(G(x,y)=U(e(x),e(y))\) for any \(x,y\in X\). Such a function \(e\) is called an embedding of \(G\) into \(U\). A function \(U:\kappa^2\to \lambda\) is weakly universal if for every \(f:\kappa^2\to\lambda\) there exist injective functions \(h:\kappa\to\kappa\) and \(k:\lambda\to\lambda\) such that \(k(f(\alpha,\beta))=U(h(\alpha),h(\beta))\) for all \(\alpha,\beta\in\kappa\). The pair \((h,k)\) is called a weak embedding. If \(U\) is Sierpiński universal, it is weakly universal. Furthermore, the notions Sierpiński universal and weakly universal are equivalent for maps into \(2\). It is also known that there is no difference between asking about the existence of universal graphs (i.e., symmetric, irreflexive functions from \(\omega_1^2\) to \(2\)) and non-symmetric functions from \(\omega_1^2\) to \(2\). In this paper, it is also proved that there is a Sierpiński universal function from \(\omega_1^2\) to \(2\) but not such kind of function from \(\omega_1^2\) to \(\omega\). Finally, the authors consider the question of universal set functions. The methods of proof rely on several well-known forcings (like Miller and Laver forcing) and also PID forcing which adds no new reals. The article is very well written, but difficult to follow.