SOME POSITIVE RESULTS IN THE CONTEXT OF UNIVERSAL MODELS 9 with them. So assume that A is a maximal antichain of complete conditions and let N be a rich enough countable elementary submodel with A ∈ N. We claim A = A ∩ N, so A is countable. For this we have to show that A ∩ N is a maximal antichain. Let p be any complete condition. By elementarity there is r ∈ N ∩ A which extends p ∩ N. By Lemma 3.2 there is a common extension of p and r. This proves the statement we claimed. We remark that the above result, as it involves ccc forcing iteration, can be easily generalised to cardinals of the form λ+ for some λ satisfying λλ = λ, as Mekler does in Theorem 8 of [9]. Therefore the theory of random graphs is amenable in the sense of Definition 3.1. 3.2. Triangle-free Graphs. Having established that the theory of graphs is amenable the next natural question to ask to what extent the amalgamation condition (∗) was necessary for this conclusion. A very good example to consider is that of the model completion of the theory of triangle-free graphs. In the sense of model-theoretic complexity, this theory provides a prototypical example of a non-simple ’simple enough’ theory, but also because this theory fails the a.c (∗). Namely Example 3.5. Let Cl be a graph consisting of the edge (cl, cl+1/mod3), for l 3, let A = C0 and B = C1. These structures satisfy the premises of the condition a.c (∗) but any graph extending C0, C1 and C2 contains the triangle {c0, c1, c2}. Therefore methods of [9] do not apply to triangle-free graphs. Dˇ zamonja and Shelah proved in [3] that the theory of the model completion of triangle-free graphs is nevertheless amenable. We explain the main ideas of this proof. Let us first concentrate on ℵ1. In the final extension we shall have 2ℵ0 = 2ℵ1 = ℵ3 and the universality number of the class of the triangle free graphs of size ℵ1 will be ℵ2. The values ℵ2 and ℵ3 are rather flexible, but we concentrate on these for concreteness. We consider the class K all finite triangle-free graphs G whose universe is a subset of ω1 and that have the property that for every non-zero limit δ ω1, G δ is a ‘reflection’ of G in the sense that for every pair a0, a1 ∈ G δ, if there is c with alRc for l 2, then there is such c in G δ. We can order this class by the relation of being an induced subgraph. Let us call this partially ordered class the approximation family. A petition on the approximation family is a directed subset of it of size ℵ1. Notice that if we are given a petition Γ then its union is a graph of size ℵ1, and by directedness, this graph is triangle-free. We call this graph MΓ. Notice that by reenumerating, every triangle free graph of size ℵ1 is isomorphic to one whose family of finite subgraphs forms a petition on the approximation family. We shall be interested in quorumed petitions, which are those petitions that contain an isomorphic copy of every finite triangle-free graph on ω1 through an isomorphism which moves every ordinal α to an ordinal β of finite distance with α. The existence of such quorumed petitions is not something we prove in ZFC, but we force them. Let us now describe the forcing. We start with a model of GCH an in it we denote by T the tree ω1 ω1. We first add ℵ3 many Cohen subsets of ω1 by countable conditions. Notice that this introduces ℵ3 many branches to T . Call the resulting universe V . We follow this with an iteration Pα, Qα ˜ : α ω2 in which each step Qα ˜ is itself an iteration of ω3 steps, of ccc forcing, which we shall call a block. In each block we shall have a preliminary forcing and an iteration of

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.