6 MIRNA DZAMONJAˇ 3.1. Graphs. The goal of this section is to present a consistency result show- ing that it is possible to force over a model of GCH to obtain a model with a large continuum and a small universal family of graphs at ℵ1. In fact, we shall demon- strate that the theory of graphs is amenable at ℵ1, in the sense of Definition 3.1. The earliest theorem to this extent is in Shelah’s [13], but unfortunately there is an error, which was noted and corrected by Shelah in [14]. The same year Mekler [9] found a different proof using, unlike [14], a ccc forcing. We shall present Mekler’s proof. Let T in this section stand for the model completion of the theory of graphs, so T is a complete model complete theory and we shall show that it is consistent that CH fails and there is a universal model of T of size ℵ1. To start with let V be a model of GCH and let us fix a sequence Aα : α ω1 of subsets of ω1 with pairwise intersections countable. Let χ be a large enough cardinal and we shall work with with elementary substructures of H(χ), ∈, . . .). The forcing will be an iteration Pα, Qβ ˜ : α ≤ ω2, β ω2 with finite supports such that each Pα is ccc. The first coordinate will have a special role: it will add a generic graph G∗ on ω1 by finite conditions. Note that G∗ is a model of T . We define the other coordinates by induction on α. For α ≥ 1, if Pα has been defined and is ccc, suppose that a bookkeeping gives us a name τ ˜ α , which is a Pα-name of a model of T . We first define Qα. ˜ In V we fix a continuous sequence ¯ α = Niα : i ω1 of countable elementary submodels of H(χ), ∈, . . . with Niα ∈ Niα +1 and Pβ, Qβ ˜ : β α , Pα ∈ N0 α (so α ∈ N0 α ). For η ω1 let i(η) denote the first i such that η ∈ N α i . Then Qα consists of pairs q = (Xq, fq) such that X = Xq is a finite subset of ω1 and f = fq is finite function from ω1 to Aα whose range is disjoint from X and which satisfies η ∈ dom(f) =⇒ f(η) ∈ N α i(η)+1 \ N α i(η) . The idea is that Qα adds an embedding of τα into G∗. To say this precisely, we define Pα+1 to consists of elements in Pα ∗ Qα ˜ such that p α decides the τ ˜ α structure of dom(fp(α)), ran(fp(α)) ⊆ p(0) and fp(α) is an embedding of the τ ˜ α structure of dom(fp(α)) into p(0). Easy density arguments show that the P = Pω 2 adds an embedding of each τα into G∗ and that if the forcing is indeed ccc, we can do the bookkeeping so to cover all models of T of size ℵ1 in the extension. The main point of the proof is to show that the forcing has ccc. The proof uses a certain amalgamation property that is present in the theory of graphs, but not for example in the theory of triangle-free graphs or the theory of linear orders. We shall describe this amalgamation property at the point of the proof where we use it. We need to pass to a dense set of conditions. Say that for 1 ≤ α ≤ ω2, p ∈ Pα is complete if for every β α and i ω1 : (i) p β∩N β i is a condition and it determines the τβ-structure ˜ of dom(fp(β)) and : (ii) if r ∈ Niβ extends p β ∩ Niβ and 1 ≤ γ β then ran(fr(γ)) ∩ p(0) ⊆ ran(fp(γ)). It can be proved that the set of complete conditions in Pα is dense, for all α. Both this and the fact that the forcing is ccc are essentially implied by the following Lemma 3.2, which is the main point of the argument. Let N = ¯ α : α ω2 . For the Lemma we need to note that if p ∈ Pα is a complete condition and N ≺ (H(χ), ∈, N , . . .) countable with α ∈ N, then p ∩ N

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.