CUBO A Mathematical Journal Vol.21, No¯ 03, (09–27). December 2019 http: // dx. doi. org/ 10. 4067/ S0719-06462019000300009 Naturality and definability II Wilfrid Hodges1 and Saharon Shelah2 1Herons Brook, Sticklepath, Devon EX20 2PY, England. wilfrid.hodges@btinternet.com 2Institute of Mathematics, Hebrew University, Jerusalem, Israel. shelah@math.huji.ac.il ABSTRACT We regard an algebraic construction as a set-theoretically defined map taking struc- tures A to structures B which have A as a distinguished part, in such a way that any isomorphism from A to A′ lifts to an isomorphism from B to B′. In general the con- struction defines B up to isomorphism over A. A construction is uniformisable if the set-theoretic definition can be given in a form such that for each A the corresponding B is determined uniquely. A construction is natural if restriction from B to its part A always determines a map from the automorphism group of B to that of A which is a split surjective group homomorphism. We prove that there is no transitive model of ZFC (Zermelo-Fraenkel set theory with Choice) in which the uniformisable construc- tions are exactly the natural ones. We construct a transitive model of ZFC in which every uniformisable construction (with a restriction on the parameters in the formulas defining the construction) is ‘weakly’ natural. Corollaries are that the construction of algebraic closures of fields and the construction of divisible hulls of abelian groups have no uniformisations definable in ZFC without parameters. http://dx.doi.org/10.4067/S0719-06462019000300009 10 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) RESUMEN Consideramos una construcción algebraica como una aplicación conjuntista tomando estructuras A a estructuras B que tienen a A como parte distinguida, de manera tal que cualquier isomorfismo de A a A′ se levanta a un isomorfismo de B a B′. En general la construcción define B salvo isomorfismo sobre A. Una construcción es uniformizable si la definición conjuntista puede darse de forma tal que para cada A el B correspon- diente está determinado únicamente. Una construcción es natural si la restricción de B a su parte A siempre determina una aplicación desde el grupo de automorfismos de B al correspondiente de A que es un homomorfismo de grupos sobreyectivo que escinde. Probamos que no existe un modelo transitivo de ZFC (teoŕıa de conjuntos de Zermelo-Fraenkel con Axioma de Elección) en el cual las construcciones uniformizables sean exactamente las naturales. Construimos un modelo transitivo de ZFC en el cual toda construcción uniformizable (con una restricción en los parámetros de las fórmulas definiendo la construcción) es ‘débilmente’ natural. Como corolarios obtenemos que la construcción de clausuras algebraicas de cuerpos y la construcción de cápsulas divisibles de grupos abelianos no tienen uniformizaciones definibles en ZFC sin parámetros. Keywords and Phrases: Naturality, uniformisability, transitive models, ZFC set theory 2010 AMS Mathematics Subject Classification: 08A35, 03E35 CUBO 21, 3 (2019) Naturality and definability II 11 1 Introduction In two papers [4] and [6] we noted that in common practice many algebraic constructions are defined only ‘up to isomorphism’ rather than explicitly. We mentioned some questions raised by this fact, and we gave some partial answers. The present paper provides much fuller answers, though some questions remain open. Our main result, Theorem 5.1, implies at once that there is a transitive model of Zermelo-Fraenkel set theory with Choice (ZFC) in which every construction explicitly definable without parameters is ‘weakly natural’ (a weakening of the notion of a natural transformation). A corollary is that there are models of ZFC in which some well-known construc- tions, such as algebraic closure of fields, are not explicitly definable without parameters; some of these consequences were reported in [5]. We also show (Theorem 4.3) that there is no transitive model of ZFC in which the constructions explicitly definable (with parameters) are precisely the natural ones. The main questions left open are to extend Theorem 5.1 to constructions definable with parameters, and to determine whether Theorem 5.1 holds without the word ‘weakly’. Most of this work was done when the second author visited the first at Queen Mary, London University under SERC Visiting Fellowship grant GR/E9/639 in summer 1989, and later when the two authors took part in the Mathematical Logic year at the Mittag-Leffler Institute in Djursholm in September 2000. The first author had made a conjecture relating uniformisability to naturality. The second author proposed the approach of section 4 on the first occasion and the idea behind the proof of Theorem 5.1 on the second. Between 1975 and 2000 the authors (separately or together) had given some six or seven false proofs of versions of Theorem 5.1 or its negation. The authors thank Ian Hodkinson for his invaluable help (while research assistant to Hodges under SERC grant GR/D/33298) in unpicking some of the earlier false proofs. The first author also thanks the second author for his willingness to persist for several decades with these highly elusive problems. 2 Constructions up to isomorphism To make this paper self-contained, we repeat or paraphrase some definitions from [6]. Definition 2.1. Let M be a transitive model of ZFC. By a construction (in M) we mean a triple C = 〈φ1,φ2,φ3〉 where (1) φ1(x), φ2(x) and φ3(x) are formulas of the language of set theory, possibly with parameters from M; (2) φ1 and φ2 respectively define first-order languages L and L − in M; every symbol of L− is a symbol of L, and the symbols of L \ L− include a 1-ary relation symbol P; (3) the class {a : M |= φ3(a)} is in M a class of L-structures, called the graph of C; 12 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) (4) if B is in the graph of C then PB, the set of elements of B satisfying Px, forms the domain of an L−-structure B− inside B; thus if Q is a relation symbol of L− then QB − = QB ↾ PB, and similarly for function symbols; the class of all structures B− as B ranges over the graph of C is called the domain of C; (5) the domain of C is closed under isomorphism; and if A,B are in the graph of C then every isomorphism from A− onto B− extends to an isomorphism from A onto B. A typical example is the construction whose domain is the class of fields, and the structures B in the graph are the algebraic closures of B−, with B− picked out by the relation symbol P . The algebraic closure of a field is determined only up to isomorphism over the field; in the terminology below, algebraic closures are ‘representable’ but not known to be ‘uniformisable’. (What we called ‘definable’ in [6], and ‘explicitly definable’ in the introduction above, we now call ‘uniformisable’; the new term agrees better with the common mathematical use of these words.) Definition 2.2. (1) We say that the construction C is X-representable (in M) if X is a set in M and all the parameters of φ1, φ2, φ3 lie in X. We say that C is small if the domain of C (and hence also its graph) contains only a set of isomorphism types of structures. (2) An important special case is where the domain of C contains exactly one isomorphism type of structure; in this case we say C is unitype. The map B− 7→ B on the domain of a construction C is in general not single-valued; but by clause (5) it is single-valued up to isomorphism over B−. Definition 2.3. (1) We say that C is uniformisable (in M) if its graph can be uniformised, i.e. there is a formula φ4(x,y) of set theory (the uniformising formula) such that for each A in the domain of C there is a unique B such that M |= φ4(A,B), and this B is an L-structure in the graph of C with A = B−. (2) We say that C is X-uniformisable (in M) if there is such a φ4 whose parameters lie in the set X. 3 Splitting, naturality and weak naturality Definition 3.1. Let ν : G → H be a surjective group homomorphism. (i) A splitting of ν is a group homomorphism s : H → G such that νs is the identity on H. We say that ν splits if it has a splitting. (ii) By a weak splitting of ν we mean a set-theoretic map s : H → G such that CUBO 21, 3 (2019) Naturality and definability II 13 (a) νs is the identity on H; (b) The composite map H s −→ G nat −→ G/Z(G) is a homomorphism, where Z(G) is the centre of G and nat is the natural homomor- phism. In particular every splitting is a weak splitting. (iii) We say that ν weakly splits if it has a weak splitting. Definition 3.2. Let C be a construction. If B is in the graph of C and A = B−, then by (4) in section 2, restriction from B to A induces a homomorphism ν : Aut(B) → Aut(A), and by (5) this homomorphism is surjective. We say that C is natural if for every such B the homomorphism ν splits. We say that C is weakly natural if for every such B the homomorphism ν weakly splits. Note that if C is not (weakly) natural, then some structure B in the graph of C witnesses this, so by restricting C to the isomorphism type of B we get a unitype construction which is not (weakly) natural. Example One. The construction of algebraic closures of fields is not weakly natural. The construction of divisible hulls of abelian groups is not weakly natural. Both these facts are proved in [5], using cohomology of finite abelian groups and (for the fields) some Galois theory. So they hold in any model of ZFC. Example Two. There are constructions that are weakly natural but not natural. The simplest is as follows. The structures B in the graph have six elements a,b,c,d,e,f and the positive diagram Pa,Pb,Rac,Rae,Rbd,Rbf,Scd,Sde,Sef,Sfc. The signature of B consists of the relation symbols P,R,S, and the signature of A = B− is empty. Then Aut(B) = Z/4Z, Aut(A) = Z/2Z and ν : Aut(B) → Aut(A) is the natural surjection. There is no splitting, because the automorphism of A of order 2 lifts only to automorphisms of B of order 4. But the construction is weakly natural because Aut(A) is abelian and hence is its own centre. In [6] we conjectured that there are models of set theory in which each representable construc- tion is uniformisable if and only if it is natural. Section 4 will show that no reasonable version of this conjecture is true. Sections 5 and 6 will show that there are models in which uniformisability implies weak naturality. Section 7 solves some of the problems raised in [4] and [6], and notes some connections with other things in the literature. 14 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) 4 Uniformisability Definition 4.1. A structure B is said to be rigid if it has no nontrivial automorphisms. We will say that a construction C is rigid-based if for every structure B in the graph of C, B− has no nontrivial automorphisms. A rigid-based construction is trivially natural. Let M be a transitive model of set theory. We will use a device that takes any construction C in M to a construction Cr, called its rigidification. The device exploits the fact that if X is any nonempty set and TC(X) is the transitive closure of X, then the structure (TC(X),ǫ) is rigid, thanks to the axiom of Foundation. Suppose B is in the graph of C. Then without affecting any of the relevant isomorphisms, we can assume that none of the elements of B outside PB lie in TC(PB). For example we can make a set-theoretic replacement of each element b outside PB by the ordered pair 〈b,TC(PB)〉. To form Cr, each structure B− in the domain of C is replaced by a two-part structure Br−, where the first part is B− and the second part consists of the set TC(PB) with a membership relation ε copying that in M. Now the structure Br is defined to be the amalgam of B and Br−, so that Br− is (Br)−. Then Cr is the closure of the class {Br : B in the graph of C} under isomorphism in M. It is clear that Cr and the map B 7→ Br are definable in M using no parameters beyond those in the formulas representing C. Lemma 4.2. If C is any construction, then Cr is rigid-based, natural and not small. Proof. If B− is in the domain of C, then Br− is rigid because its set of elements is transitively closed; so Cr is rigid-based. Naturality follows at once. Since the domain of C is closed under isomorphism, the relevant transitive closures are arbitrarily large. � Theorem 4.3. There is no transitive model M of ZFC in which both the following are true: (a) Every rigid-based construction in M is uniformisable. (b) Every unitype uniformisable construction in M is weakly natural. In particular there is no transitive model of ZFC in which the natural constructions are exactly the uniformisable ones. Proof. Suppose M is a counterexample. By Example One in section 3 there are some non- weakly-natural constructions in M. So by restricting to a single isomorphism type we can find a CUBO 21, 3 (2019) Naturality and definability II 15 unitype non-weakly-natural construction C in M. Then Cr is rigid-based and hence uniformisable by assumption. But we can use the uniformising formula of Cr to uniformise C with the same parameters. So by the assumption on M again, C is weakly natural; contradiction. � The next result gives some finer information about small constructions. Theorem 4.4. Let M be a transitive model of ZFC, Y a set in M and c̄ a well-ordering of Y in M. Assume: In M, if X is any set, then every unitype X-representable rigid-based construction is X ∪ Y -uniformisable. Then In M, every small ∅-representable construction is {c̄}-uniformisable, and hence there are unitype {c̄}-uniformisable constructions that are not weakly natural. Proof. Let γ be the length of c̄. Write v̄ for the sequence of variables (vi : i < γ). In M we can well-order (definably, with no parameters) the class of pairs 〈j,ψ〉 where j is an ordinal and ψ(x,y,z, v̄) is a formula of set theory. We write Hj for the set of sets hereditarily of cardinality less than ℵj in M. Let C be a small ∅-representable construction in M. Then Cr is an ∅-representable rigid-based construction. It is not small; but if B is any structure in the graph of C, let CB be the construction got from Cr by restricting the graph to structures isomorphic to Br. Then CB is a unitype and {B}-representable rigid-based construction, so by assumption it is {B} ∪ Y -uniformisable, say by a formula ψB(−,−,B, c̄) where B,c̄ are the parameters. By the reflection principle in M there is an ordinal j such that M |= ∃C(C ∈ CB∧C − = Br−∧C is the unique set such that “Hj |= ψB(B r−,C,B, c̄)”). Hence in M there is a first pair 〈jB,ψB〉, definable from B, such that M |= ∃C(C ∈ CB∧C − = Br−∧C is the unique set such that “HjB |= ψB(B r−,C,B, c̄)”). Since all of this is uniform in B, it follows that the construction C is {c̄}-uniformisable in M by the formula φ(x,y, c̄) which says y = C|L where Hjx |= ψx(x r−,C,x, c̄). The last clause of the theorem follows by choosing C suitably, for example using Example One of section 3. � 16 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) 5 The set theory Theorem 5.1. Let M be a countable transitive model of ZFC and GCH, and λ a transfinite cardinal in M. Then there is a forcing extension N of M with the following property. If C is a uniformisable unitype construction defined in N with parameters in M, whose graph contains a structure B in M with B and Aut(B) both of cardinality 6 λ, then C is weakly natural in N. The proof of this theorem will occupy this and the next section. The idea is to consider any unitype construction C whose parameters lie in M, and introduce a very homogeneous generic structure B⋆ into the graph of C. The homogeneity of B⋆ will make it impossible to uniformise without some form of naturality. This is a novel argument. At present we can apply it simultane- ously for all unitype constructions satisfying the stated restriction to a fixed λ. We expect that a similar proof by class forcing will eliminate this restriction, but this is delayed. Our notation for forcing mainly follows Jech [7]. We define P to be the notion of forcing in M that consists of all partial maps from λ++ × λ++ × λ++ to 2 which have domain of cardinality at most λ. We abbreviate λ++ × λ++ × λ++ to (λ++)3. Lemma 5.2. The notion of forcing P is λ+-closed and satisfies the λ++-chain condition. � For definiteness we take MP, the class of P-names, to be the smallest class of elements of M such that if X is any subset of MP and for each y ∈ X, Iy is a non-empty antichain in P, then {(p,y) : y ∈ X,p ∈ Iy} is a P-name in M P; the domain of this P-name is X. Then for every P-generic G the interpretation of the name ẋ = {(p,y) : y ∈ X,p ∈ Iy} is the set ẋ[G] = {y[G] : ∃p ∈ G,(p,y) ∈ ẋ}. We write ẋ for P-names, and x̌ for the canonical P-name of the element x ∈ M. We take a P-generic set G over M and we put N = M[G]. We will prove Theorem 5.1 for this N. In M we fix a unitype construction C, a structure B in the graph of C, and a uniformising formula φ(x,y). We write A for B−. Definition 5.3. In M we define two homomorphisms, I from the group of permutations of (λ++)3 to the group of automorphisms of P as ordered set; and J from the group of automorphisms of P to the group of permutations of MP. Thus: (a) Let α be a permutation of (λ++)3 and p ∈ P. Then we define αI(p) by (αI(p))(α(i,j,k)) = p(i,j,k) for all i,j,k < λ++. CUBO 21, 3 (2019) Naturality and definability II 17 (b) Let γ be an automorphism of P. Then γJ is defined on MP by induction on rank: γJẋ = {(γp,γJẏ) : (p, ẏ) ∈ ẋ}. The maps I and J are clearly homomorphisms. Lemma 5.4. Let γ be an automorphism of P which is in M. Then: (a) If G is a P-generic set over M, then γG is P-generic over M, and for every P-name ẋ we have (γJẋ)[γG] = ẋ[G] (where γG = {γp : p ∈ G}). (b) If ẋ is a P-name then (α) ⇒ (β), where we write (α): for every pair (p, ẏ), (p, ẏ) ∈ ẋ if and only if (γp,γJẏ) ∈ ẋ. (β): γJ(ẋ) = ẋ. Proof. . For (a), by induction on the rank of ẋ, ẋ[G] = {ẏ[G] : ∃p ∈ G,(p, ẏ) ∈ ẋ} = {γJẏ[γG] : ∃γp ∈ γG,(γp,γJẏ) ∈ γJẋ} = {ż[γG] : ∃q ∈ γG,(q, ż) ∈ γJẋ} = (γJẋ)[γG]. Part (b) is immediate from the definition of γJ. � Since G is P-generic, ⋃ G is a total map from (λ++)3 to 2. For each i < λ++ and j < λ++, we define aij = {k < λ ++ : ⋃ G(i,j,k) = 1} and a′i = {aij : j < λ +}, so that a′i is a set of λ ++ independently generic subsets of λ++. If a and b are (in N) sets of subsets of λ++, we put a ≡ b iff the symmetric difference of a and b has cardinality 6 λ. We write ai for the equivalence class (a′i) ≡. The P-names ȧij, ȧ ′ i, ȧi can be chosen in M P independently of the choice of G. Consider again the structures A and B in M. Without loss we can suppose that dom(A) is an initial segment of λ. In M[G] there is a map e which takes each element i of A to the corresponding set ai = ȧi[G]; by means of e we can define a copy A ⋆ of A whose elements are the sets ai (i ∈ dom(A)). Lemma 5.5. The P-names Ȧ⋆, ė can be chosen to be independent of the choice of G. Also we can take the boolean names ȧij and ȧ ′ i to be ȧij = {(((i,j,k) 7→ 1), ǩ) : (i,j,k) ∈ (λ ++)3}, ȧ′i = {(1, ȧij) : j < λ ++}. 18 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) � A notion of forcing Q in M is said to be homogeneous if for any two conditions p,q ∈ P there is an automorphism α of Q in M such that p and αq are compatible. Lemma 5.6. P is homogeneous. � By this lemma and the fact that A,B and the parameters of the uniformising formula φ lie in M, the statement “φ uniformises a construction on the class of structures isomorphic to A, which takes A to B” is true in N independently of the choice of G. In particular there are P-names Ḃ⋆, ε̇ such that ||Ḃ is the unique structure such that φ(Ȧ⋆, Ḃ∗) holds, (5.1) ė : Ǎ → Ȧ∗ is the isomorphism such that ė(̌ı) = ȧi for each i ∈ dom(Ǎ), and ε̇ : B̌ → Ḃ∗ is an isomorphism which extends ė||P = 1. Lemma 5.7. Let G be P-generic over M. Then: (a) Aut(A)M = Aut(A)M[G]. (b) Aut(B)M = Aut(B)M[G]. (c) The set of maps from Aut(A) to Aut(B) is the same in M as it is in M[G]. Proof. . P is λ+-closed by Lemma 5.2. Hence no new permutations of A or B are added since |A| ≤ |B| ≤ λ in M; this proves (a), (b). Likewise (c) holds since |Aut(A)| ≤ |Aut(B)| ≤ λ in M. � We regard Aut(A) as a permutation group on λ++ by letting it fix all the elements of λ++ which are not in dom(A). We write Π for the cartesian product ∏ λ++ Aut(A) of λ++ copies of the group Aut(A), in the sense of M. Then each element α of Π can be regarded as a map α : λ++ → Aut(A) in M. We write N for the subgroup of Π consisting of those α such that for some finite sequence of ordinals 0 = i0 < i1 < ... < in < in+1 = λ ++ the map α is constant on each interval [ik, ik+1) (0 6 k 6 n). The elements of N will be called neat maps. We write π for the map from N to Aut(A) which takes each neat map to its eventual value. We write N − for the set of all neat maps α with π(α) = 1. For each ordinal i < λ++ we write Ni for the set of neat maps α such that α(j) = 1 for all j < i. We write N − i for N − ∩ Ni. CUBO 21, 3 (2019) Naturality and definability II 19 Lemma 5.8. As a subset of the group Π, N forms a group with subgroups N −, Ni (i < λ ++). The map π : N → Aut(A) is a surjective group homomorphism. Proof. . From the definitions. � The neat map α ∈ Π determines a permutation αK of the set (λ++)3 by αK(i,j,k) = (α(j)(i),j,k). Hence α induces an automorphism αKIJ of MP. Lemma 5.9. Suppose α : λ++ → Aut(A) is neat. Then αKIJ setwise fixes the set {ȧi : i ∈ dom(A)} of canonical names of the elements of Ȧ∗[G], and it acts on this set in the way induced by π(α) and the map i 7→ ȧi. Thus α KIJ(ȧi) = ȧπ(α)(i). Proof. . We use the boolean names in Lemma 5.5. For ȧij, αKIJȧij = {(α KI((i,j,k) 7→ 1),αKIJ(ǩ)) : (i,j,k) ∈ (λ++)3} = {((αK(i,j,k) 7→ 1), ǩ) : (i,j,k) ∈ (λ++)3} = {(α(j)(i),j,k) 7→ 1), ǩ) : (i,j,k) ∈ (λ++)3} = ȧα(j)i,j. Then for ȧ′i, αKIJȧ′i = {(α KI(1, ȧij) : j < λ ++} = {(1, ȧα(j)i,j) : j < λ ++}. We claim that with boolean value 1, {(1, ȧα(j)i,j) : j < λ ++} ≡ ȧ′ πα(i). For this, first note that ȧ′πα(i) = {(1, ȧπ(α)i,j) : j < λ ++}. Since α is neat, there is j0 < λ ++ such that α(j) = πα whenever j > j0. So for any generic G, {(1, ȧα(j)i,j) : j < λ ++}[G] and ȧ′ πα(i) [G] differ in at most |j0| elements. The lemma follows. � Lemma 5.10. For each element i of A and each neat map α, ȧπ(α)(i)[αG] = ȧi[G]. In particular Ȧ⋆[αG] = Ȧ⋆[G]. Proof. By Lemma 5.9, ȧπ(α)(i)[αG] = (αȧi)[αG]. Then by Lemma 5.4 and the fact that αȧi lies in MP, (αȧi)[αG] = ȧi[G]. This shows that Ȧ⋆[αG] = Ȧ⋆[G]. 20 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) We write ε̇−1 for a P-name such that ε̇−1[G] = (ε̇[G])−1 for all generic G. Lemma 5.11. Suppose α is a neat map and G is P-generic over M. Then Ḃ∗[α−1G] = Ḃ∗[G], and the map (ε̇−1 ◦ αε̇)[G] is an automorphism of B which extends π(α). Proof. Since M[α−1G] = M[G] and Ȧ∗[α−1G] = Ȧ∗[G], statement (5.1) (before Lemma 5.7) tells us that ė[α−1G](i) = ȧi[α −1G] for each i ∈ dom(A), and that Ḃ∗[α−1G] = Ḃ∗[G] and ε̇[G]−1◦ε̇[α−1G] extends ė[G]−1 ◦ ė[α−1G]. Now using Lemma 5.10, ė[G]−1 ◦ ė[α−1G](i) = ė[G]−1(ȧi[α −1G]) = ė[G]−1(ȧπ(α)(i)[G]) = π(α)(i). Lemma 5.12. For every neat map α and all p ∈ P there are p′ 6 p and g ∈ AutB extending π(α), such that p′ ⊢P ε̇ −1 ◦ α(ε̇) = ǧ. Proof. Let f be π(α). By Lemma 5.11 we have 1 = ||ε̇−1 ◦ αε̇ is an automorphism of B extending f̌||P = ∑ g ||ε̇−1 ◦ αε̇ = ǧ||P where g ranges over the automorphisms of B that extend f. Definition 5.13. (a) For each p ∈ P and each i < λ++, define tp,i to be the set of all pairs (f,g), with f ∈ Aut(A) and g ∈ Aut(B), such that for some α ∈ Ni, π(α) = f and p ⊢P ε̇ −1 ◦ αε̇ = ǧ. (b) Clearly if p′ 6 p then tp′,i ⊇ tp,i. The number of possible values for f and g is 6 λ by choice of λ, and P is λ+-closed; so there is pi such that for all p ′ 6 pi, tp′,i = tpi,i. We fix a choice of pi for each i, and we write ti for the resulting value tpi,i. (c) For each i and each (f,g) in ti we choose α in Ni with π(α) = f so that pi ⊢P ε̇ −1 ◦ αε̇ = ǧ. We write αif,g for this α. CUBO 21, 3 (2019) Naturality and definability II 21 Lemma 5.14. For each i < λ++, ti is a subset of Aut(A) × Aut(B) such that (a) for each (f,g) in ti, g|A = f; (b) for each f in Aut(A) there is g with (f,g) in ti. (So ti(−,−) is a first attempt at a lifting of the restriction map from Aut(B) to Aut(A).) Proof. By Lemma 5.12 and the surjectivity of π. Lemma 5.15. There is a stationary subset S of λ++ such that: (a) for each i ∈ S and j < i, the domain of pj is a subset of i × i × i; (b) for each i ∈ S and j < i, every map α j f,g : λ++ → Aut(A) is constant on [i,λ++); (c) for all i,j ∈ S, ti = tj; (d) there is a condition p⋆ ∈ P such that for all i ∈ S, pi ↾ (i × i × i) = p ⋆. Proof. First, there is a club C ⊆ λ++ on which (a) and (b) hold. Let Sη be {δ < λ ++ : cf(δ) = λ+}. Clearly Sν = Sη ∩ C is stationary; and for each i ∈ Sν, pi ↾ (i × i × i) has domain ⊆ j × j × j for some j = ji < i. Then by Fődor’s lemma there is a stationary subset S of Sν on which (c) and (d) hold. 6 The weak lifting Continuing Section 5, we use the notation S, p⋆ from Lemma 5.15. We write t for the constant value of ti (i ∈ S) from clause (c) of Lemma 5.15, and t − for the set of all g such that (1,g) ∈ t. We write ν : Aut(B) → Aut(A) for the restriction map. If X is a subset of Aut(B), we write 〈X〉 for the subgroup of Aut(B) generated by X. Lemma 6.1. The relation t is a subset of Aut(A) × Aut(B) that projects onto Aut(A), and if (f,g) is in t then ν(g) = f. Proof. This repeats Lemma 5.14 (a) and (b). Lemma 6.2. If (f1,g1) and (f2,g2) are both in t then (f1f2,g1g2) is in t. 22 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) Proof. Take any i,j ∈ S with i < j. Put α1 = α j f1,g1 , α2 = α i f2,g2 and α3 = α1α2. Note that α1α2 is in Ni since i < j. Trivially we have pj ⊢ ε̇ −1 ◦ α3(ε̇) = ε̇ −1 ◦ α1(ε̇) ◦ (α1(ε̇)) −1 ◦ α3(ε̇) and by assumption pj ⊢ ε̇ −1 ◦ α1(ε̇) = ǧ1. So pj ⊢ ε̇ −1 ◦ α3(ε̇) = ǧ1 ◦ (α1(ε̇)) −1 ◦ α1(α2ε̇). Also by assumption pi ⊢ ε̇ −1 ◦ α2(ε̇) = ǧ2. Acting on this last formula by α1 gives α1pi ⊢ α1ε̇ −1 ◦ α1α2ε̇ = α1ǧ2. Now α1ǧ2 = ǧ2. Also α1pi = pi since the support of pi lies entirely below j (by Lemma 5.15(a)), and α1 = α j f1,g1 is the identity in this region since it lies in Nj. So we have shown that pi ⊢ α1ε̇ −1 ◦ α1α2ε̇ = ǧ2. Now we note that pi ∪ pj is a condition in P, by (a), (d) of Lemma 5.15. Hence we have that pi ∪ pj ⊢ ε̇ −1 ◦ α3ε̇ = ǧ1ǧ2. Since α3 is in Ni, this shows that (f1f2,g1g2) ∈ tpi∪pj,i. Then by the maximality property of pi, (f1f2,g1g2) ∈ tpi,i so that (f1f2,g1g2) is in t. Corollary 6.3. If (f,g1) and (f,g2) are in t then g1g −1 2 is in 〈t −〉. CUBO 21, 3 (2019) Naturality and definability II 23 Proof. By Lemma 6.1 there is some g′ ∈ Aut(B) such that (f−1,g′) is in t. Then by Lemma 6.2, (1,g1g ′) and (1,g2g ′) are in t and so g1g ′, g2g ′ are in t−. Hence the element g1g −1 2 = (g1g ′)(g2g ′)−1 lies in 〈t−〉. Lemma 6.4. Every element of t− is central in Aut(B). Proof. Suppose g2 ∈ t −, so that (1,g2) ∈ t. Consider (f1,g2) ∈ t, and apply the notation of the proof of Lemma 6.2 with f2 = 1. In that notation, α1 is the identity below j and α2 is the identity below i (since i,j ∈ S). But also g2 lies in t −, so α2 is the identity on [j,λ +). In particular α1 commutes with α2. As in the proof of Lemma 6.2 we have pi ⊢ ε̇ −1 ◦ α3ε̇ = ε̇ −1 ◦ α2ε̇ ◦ α2ε̇ −1 ◦ α3ε̇. As before, we have that pi ⊢ ε̇ −1 ◦ α2ε̇ = ǧ2 and α2pj ⊢ α2ε̇ −1 ◦ α2α1ε̇ = α2ǧ1. Now the support of pj lies below i or within [j,λ +) × domA, and α2 is the identity in both these regions, and so α2(pj) = pj. Thus, since α1 commutes with α2, pj ⊢ α2ε̇ −1 ◦ α3ε̇ = ǧ1. So as before, pi ∪ pj ⊢ ε̇ −1 ◦ α3ε̇ = ǧ2ǧ1. Recalling that in the proof of Lemma 6.2 we showed that pi ∪ pj ⊢ ε̇ −1 ◦ α3(ε̇) = ǧ1ǧ2, we deduce that pi ∪ pj ⊢ ǧ1ǧ2 = ǧ2ǧ1. But the equation g1g2 = g2g1 is about the ground model, and hence it is true. 24 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) Now in M choose a map s : Aut(A) → Aut(B) so that for each f ∈ Aut(A), s(f) is some g with (f,g) ∈ t. This is possible by Lemma 6.1. Lemma 6.5. In M the map s is a weak splitting of ν : Aut(B) → Aut(A). Proof. Trivially νs is the identity on Aut(A). Write s′ : Aut(A) → Z(Aut(B)) for the composite of s and nat : Aut(B) → Z(Aut(B)). We show that s′ is a homomorphism as follows. Suppose f1f2 = f3 in Aut(A). Put gi = s(fi) for each i (1 6 i 6 3). Then by Lemma 6.2, (f3,g1g2) is in t, so by Corollary 6.3 and Lemma 6.4, g1g2g −1 3 is in 〈t −〉 ⊆ Z(Aut(B)). Then s′(f1)σ ′(f2) = g1Z(Aut(B)).g2Z(Aut(B)) = g1g2.Z(Aut(B)) = g3Z(Aut(B)) = s ′(f3) as required. � This completes the proof of Theorem 5.1. 7 Answers to questions The results above answer most of the problems stated in [6]. In that paper we showed: Theorem 3 of [6] If C is a small natural construction in a model of ZFC, then C is uniformisable with parameters. We asked (Problem A) whether it is possible to remove the restriction that C is small. The answer is No: Theorem 7.1. There is a transitive model of ZFC in which some ∅-representable construction is natural but not uniformisable (even with parameters). Proof. Let N be the model of Theorem 5.1. Let C be some construction ∅-representable in N which is not weakly natural (cf. Example One in section 3). Then by Theorem 5.1, C is not uniformisable. The rigidifying construction Cr of section 3 is ∅-representable, natural and not uniformisable. Problem B asked whether in Theorem 3 of [6] the formula defining C can be chosen so that it has only the same parameters as the formulas chosen to represent C. The answer is No: Theorem 7.2. There is a transitive model N of ZFC with the following property: CUBO 21, 3 (2019) Naturality and definability II 25 For every set Y there are a set X and a unitype rigid-based (hence small natural) X-representable construction that is not X ∪ Y -uniformisable. Proof. Take N to be the model given by Theorem 5.1. Let Y be any set in N. If N and Y are not as stated above, then for every set X and every unitype rigid-based X-representable construction in N, X is X∪Y -uniformisable. So the hypothesis of Theorem 4.4 holds, and by that theorem there is in N a small {c̄}-uniformisable construction that is not weakly natural. But this contradicts the choice of N. Problem C asked whether there are transitive models of ZFC in which every uniformisable construction is natural. Theorem 5.1 is the best answer we have for this; the problem remains open. In [4] one of us asked whether there can be models of ZFC in which the algebraic closure construction on fields is not uniformisable. Theorem 7.3. There are transitive models of ZFC in which: (a) no formula without parameters defines for each field a specific algebraic closure for that field, and (b) no formula without parameters defines for each abelian group a specific divisible hull of that group. Proof. Let the model N be as in Theorem 5.1. In N the constructions of Example One in section 3 are not uniformisable, since they are not weakly natural. So these two examples prove (a) and (b) respectively. We close with some remarks on related notions in other papers. One result in [4] was that there is no primitive recursive set function which takes each field to an algebraic closure of that field. This is an absolute result which applies to every transitive model of ZFC, and so it is not strictly comparable with the consistency results proved above. In this context we note that Garvin Melles showed [8] that there is no “recursive set-function” (he gives his own definition for this notion) which finds a representative for each isomorphism type of countable torsion-free abelian group. The paper [1] of Adámek et al. gives a simple universal algebraic sufficient condition for injective hull constructions not to be natural, and notes that two of their examples are also in 26 Wilfrid Hodges and Saharon Shelah CUBO 21, 3 (2019) [6]. The comparison between our notions and theirs is a little tricky. For both Adámek et al. and us, ‘natural’ is as in ‘natural transformation’ in the categorical sense. But we work in different categories. In this paper and [6], the relevant morphisms are isomorphisms; but for [1] they include embeddings. Hence the notion of naturality in [1] is stricter than ours. For example their condition implies that the MacNeille completion of posets, which embeds every poset in a lattice, is not natural. But it is natural in our sense, since isomorphisms between posets lift functorially to isomorphisms between their MacNeille completions. In fact this is clear from the standard definition of MacNeille completions ([2] p. 40ff), which also provides a uniformisation of this construction in any model of ZFC. It seems very unlikely that the condition in [1] adapts to give a sufficient condition for failure of weak naturality in the sense above. In a related context Harvey Friedman [3] used the term ‘naturalness’ in a weaker sense than ours. CUBO 21, 3 (2019) Naturality and definability II 27 References [1] Jiř́ı Adámek, Horst Herrlich, Jiř́ı Rosický and Walter Tholen, ‘Injective hulls are not natural’, Algebra Universalis 48 (2002) 379–388. [2] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge Uni- versity Press, Cambridge 1990. [3] H. Friedman, ‘On the naturalness of definable operations’, Houston J. Math. 5 (1979) 325– 330. [4] W. Hodges, ‘On the effectivity of some field constructions’, Proc. London Math. Soc. (3) 32 (1976) 133–162. [5] W. Hodges, ’Definability and automorphism groups’, in Proceedings of International Congress in Logic, Methodology and Philosophy of Science, Oviedo 2003, ed. Petr Hájek et al., King’s College Publications, London 2005, pp. 107–120; ISBN 1-904987-21-4. [6] W. Hodges and S. Shelah, ‘Naturality and definability I’, J. London Math. Soc. 33 (1986) 1–12. [7] T. Jech, Set theory (Academic Press, New York, 1978). [8] G. Melles, ‘Classification theory and generalized recursive functions’, D.Phil. dissertation, University of California at Irvine, 1989. Introduction Constructions up to isomorphism Splitting, naturality and weak naturality Uniformisability The set theory The weak lifting Answers to questions