OctoInformBeta

OpenAI preprint, September 2026 · §3. The abstract elementary class

Lemma 3.10: The union lies ≤K\le_K-above each member and ≤K\le_K-below each common extension; direct limits of objects along strong maps are objects

Under the continuum hypothesis, the array class is closed under directed unions.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Under the continuum hypothesis (CH), the array class KK is a class of structures in a countable relational language, the array language, with a strong substructure relation ≤K\le_K. Take members of KK indexed by a nonempty directed preorder and increasing under ≤K\le_K along it. The question is whether their union is a member of KK lying ≤K\le_K-above each of them, and whether it lies ≤K\le_K-below every member of KK that lies ≤K\le_K-above them all: for chains, these are the Tarski-Vaught chain axioms of an abstract elementary class.

Both membership in KK and the relation ≤K\le_K are read off normal forms, which present structures in the array language, so the item also concerns directed systems of normal forms: their direct limit, the maps from the members of the system into it and the maps out of it.

Normal Forms and the Class KK

A relational structure VV in a vocabulary LL is a set, its universe, with an interpretation of each nn-ary relation symbol of LL as a set of nn-tuples of its elements.✦ A structure VV is a substructure of a structure WW, written V⊆WV \subseteq W, when the universe of VV is contained in that of WW and each relation of VV is the restriction of the corresponding relation of WW.✦ A structure UU is the union of a family (F(i))i∈J(F(i))_{i \in J} of structures indexed by a set JJ when every F(i)F(i) is a substructure of UU and every element of UU lies in some F(i)F(i).✦

A tuple from a set II is an injective map t:{0,…,n}→It : \{0, \dots, n\} \to I for some n∈ℕn \in \mathbb{N}, a sequence of n+1n + 1 distinct elements of II; its length is n+1n + 1.✦ For an injection ff of II into JJ the tuple ftf t is f∘tf \circ t✦, and a subsequence of tt is a composite t∘et \circ e with ee an order embedding of {0,…,m}\{0, \dots, m\} into {0,…,n}\{0, \dots, n\}.✦

A normal form M=(I,B,<,a)M = (I, B, <, a) consists of a nonempty index set II; a nonempty base set BB with a dense linear order << without endpoints, the base order, in which every closed interval [x,y][x, y] is countable; and a bit a(t,n,b)∈{0,1}a(t, n, b) \in \{0, 1\} for every tuple tt from II, every n∈ℕn \in \mathbb{N} and every b∈Bb \in B.✦ Its points are of six kinds: the index points i∈Ii \in I, the base points b∈Bb \in B, the finite subsets of BB, the finite subsets of ℕ\mathbb{N}, the rows (t,n,s)(t, n, s) with s⊆Bs \subseteq B finite, and the columns (t,b,v)(t, b, v) with v⊆ℕv \subseteq \mathbb{N} finite.✦ The bit of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) over the same tuple is a(t,n,b)+1b∈s+1n∈vmod⁡2.a(t, n, b) + 1_{b \in s} + 1_{n \in v} \bmod 2.(1)✦

On its points, MM is a structure in the array language. The unary symbols of the array language hold of the index points, of the base points, of the finite subsets of BB, of the finite subsets of ℕ\mathbb{N}, of the rows (t,n,s)(t, n, s) with tt of length k+1k + 1, for each kk and nn, and of the columns (t,b,v)(t, b, v) with tt of length k+1k + 1, for each kk; and for each finite subset vv of ℕ\mathbb{N} there is a unary symbol true of vv alone. The other symbols are the projections of a row onto the entries of its tuple and of a column onto its base point and the entries of its tuple, the order of the base points, the incidence of a base point in a finite subset of BB, the bit relation, true of a row and a column over the same tuple when their bit (1) is 11, the symmetric differences of finite subsets of BB and of ℕ\mathbb{N}, and the actions by symmetric difference of the finite subsets of BB on rows and of the finite subsets of ℕ\mathbb{N} on columns. The order, the incidence and the bit relation are binary symbols, the symmetric differences and the two actions are ternary, the projection of a row with a tuple of length k+1k + 1 has k+2k + 2 places, and the projection of a column with a tuple of length k+1k + 1 has k+3k + 3 places.

A label on a set AA of positions is a pair (J,i)(J, i) in which JJ is a nonempty finite subset of AA and i∈ℕi \in \mathbb{N}.✦ The root of a position aa is the label ({a},0)(\{a\}, 0).✦ A diagram on a set AA of positions is a triple (E,R,ρ)(E, R, \rho) in which EE and RR are binary relations on the labels on AA and ρ\rho assigns to each label a tag in ω1\omega_1✦; tags are compared as ordinals.✦ The restriction D↾eD \restriction e of a diagram DD on BB along an injection ee of AA into BB is the diagram on AA in which two labels are EE-related, or RR-related, exactly when their images under ee are so related in DD, and the tag of a label is the tag in DD of its image✦; the image of a label (J,i)(J, i) under ee is (e[J],i)(e[J], i).✦

The palette of colors S=2ω/=*S = 2^\omega/{=^*} is the set of binary sequences a:ℕ→{0,1}a : \mathbb{N} \to \{0, 1\} modulo equality outside a finite set✦, two sequences being identified when they differ at only finitely many places✦; [a][a] is the color of the sequence aa.✦

A diagram (E,R,ρ)(E, R, \rho) on a set of positions is valid when EE is an equivalence relation on its labels that RR and ρ\rho respect, ρ(x)<ρ(y)\rho(x) < \rho(y) whenever xRyx \mathrel{R} y, labels with the same RR-predecessors are EE-equivalent, and positions with EE-equivalent roots are equal.✦ Under CH, the code is a fixed injection of the set of diagrams on the sets {0,…,m}\{0, \dots, m\}, m∈ℕm \in \mathbb{N}, into SS.✦ A coloring cc of the tuples from a set II is a map assigning a color c(s)∈Sc(s) \in S to each tuple ss from II; it passes the test of a tuple tt of length n+1n + 1 when there is a diagram dd on {0,…,n}\{0, \dots, n\} such that, for every order embedding e:{0,…,m}→{0,…,n}e : \{0, \dots, m\} \to \{0, \dots, n\}, the restriction d↾ed \restriction e is valid and has code c(t∘e)c(t \circ e).✦

The color of a tuple tt at b∈Bb \in B is ct(b)=[a(t,⋅,b)]∈Sc_t(b) = [a(t, \cdot, b)] \in S.✦ Under CH, a normal form MM is an object when, for every tuple tt from II, {b∈B:the coloring s↦cs(b) fails the test of t} is countable.\{\, b \in B : \text{the coloring } s \mapsto c_s(b) \text{ fails the test of } t \,\} \text{ is countable}.(2)✦

A map f:M→Nf : M \to N of normal forms consists of an embedding of IMI_M into INI_N and an order embedding of BMB_M into BNB_N, both written ff, with a row shift u(t,n)u(t, n), a finite subset of BNB_N, and a column shift w(t,b)w(t, b), a finite subset of ℕ\mathbb{N}, for each tuple tt from IMI_M, each n∈ℕn \in \mathbb{N} and each b∈BMb \in B_M, such that the bits agree: aN(ft,n,fb)+1fb∈u(t,n)+1n∈w(t,b)≡aM(t,n,b)(mod⁡2).a_N(f t, n, f b) + 1_{f b \in u(t, n)} + 1_{n \in w(t, b)} \equiv a_M(t, n, b) \pmod 2.(3) The map ff acts on points: index and base points go to their images, a finite subset of BMB_M to its image, a finite subset of ℕ\mathbb{N} to itself, a row (t,n,s)(t, n, s) to (ft,n,u(t,n)△f[s])(f t, n, u(t, n) \mathbin{\triangle} f[s]) and a column (t,b,v)(t, b, v) to (ft,fb,w(t,b)△v)(f t, f b, w(t, b) \mathbin{\triangle} v).✦ Maps compose: for maps f:M→Nf : M \to N and g:N→Lg : N \to L with shifts uf,wfu_f, w_f and ug,wgu_g, w_g, the map g∘fg \circ f composes the embeddings, its row shift at (t,n)(t, n) is ug(ft,n)△g[uf(t,n)]u_g(f t, n) \mathbin{\triangle} g[u_f(t, n)] and its column shift at (t,b)(t, b) is wg(ft,fb)△wf(t,b)w_g(f t, f b) \mathbin{\triangle} w_f(t, b); the identity map has empty shifts✦.

Along a map f:M→Nf : M \to N, the color of a tuple ss from IMI_M at b∈BNb \in B_N is csf(b)=[n↦aN(fs,n,b)+1b∈u(s,n)mod⁡2].c^f_s(b) = \bigl[\, n \mapsto a_N(f s, n, b) + 1_{b \in u(s, n)} \bmod 2 \,\bigr].(4)✦ Under CH, a map f:M→Nf : M \to N of normal forms is strong when f[BM]f[B_M] is an order-convex subset of BNB_N and every b∈BNb \in B_N outside f[BM]f[B_M] passes the tests: for every tuple tt from IMI_M, the coloring s↦csf(b)s \mapsto c^f_s(b) passes the test of tt.

A presentation of a structure VV in the array language is a normal form PP together with a bijection from the points of PP onto the universe of VV under which each relation of VV corresponds to the relation of PP with the same symbol.✦ Under CH, KK is the class of structures with a presentation by an object, its members being the objects of KK, and its strong substructure relation has V≤KWV \le_K W when VV and WW have presentations by objects PP and QQ joined by a strong map f:P→Qf : P \to Q that induces the inclusion of VV in WW: each point xx of PP and its image f(x)f(x) present the same element.✦

Directed Systems of Normal Forms

Let JJ be a nonempty directed preorder. A directed system of normal forms over JJ is a family of normal forms Mi=(Ii,Bi,<,ai)M_i = (I_i, B_i, <, a_i), i∈Ji \in J, called the stages of the system, with maps fij:Mi→Mjf_{ij} : M_i \to M_j for i≤ji \le j such that fiif_{ii} is the identity and fjk∘fij=fikf_{jk} \circ f_{ij} = f_{ik} whenever i≤j≤ki \le j \le k.✦ A directed system of normal forms over JJ has convex maps when each fij[Bi]f_{ij}[B_i], for i≤ji \le j, is an order-convex subset of BjB_j.

For such a system with convex maps, I∞I_\infty is the direct limit of the index sets IiI_i✦ and B∞B_\infty the direct limit of the base orders BiB_i✦, with canonical embeddings ιi\iota_i of IiI_i and of BiB_i into them; two elements of B∞B_\infty compare as their representatives in a common BiB_i✦. The limit of the system is the normal form M∞=(I∞,B∞,<,a∞)M_\infty = (I_\infty, B_\infty, <, a_\infty) whose bits are read in the direct limit of the sets of points of the MiM_i: there a row over (t,n)(t, n) and a column over (t,b)(t, b) are fixed for each tuple tt from I∞I_\infty, each n∈ℕn \in \mathbb{N} and each b∈B∞b \in B_\infty, and a∞(t,n,b)a_\infty(t, n, b) is their bit (1) at a stage that holds both.✦

The stage map ιi:Mi→M∞\iota_i : M_i \to M_\infty is the map of normal forms with the embeddings ιi\iota_i of IiI_i and BiB_i and with the row and column shifts by which the images of the rows (t,n,∅)(t, n, \emptyset) and the columns (t,b,∅)(t, b, \emptyset) of MiM_i differ from the fixed ones.✦ For a normal form NN and a compatible family of maps qi:Mi→Nq_i : M_i \to N, that is, maps with qj∘fij=qiq_j \circ f_{ij} = q_i whenever i≤ji \le j, the induced map q:M∞→Nq : M_\infty \to N is the map of normal forms that sends ιi(x)\iota_i(x) to qi(x)q_i(x) for every i∈Ji \in J and every point xx of MiM_i.✦

The Claim

Theorem 1. Let JJ be a nonempty directed preorder, and let (Mi,fij)(M_i, f_{ij}) be a directed system of normal forms over JJ with convex maps, limit M∞M_\infty and stage maps ιi\iota_i. Then, for all x,y∈B∞x, y \in B_\infty and every i∈Ji \in J, the closed interval [x,y] of B∞ is countable,\text{the closed interval } [x, y] \text{ of } B_\infty \text{ is countable},(5)✦ ιi[Bi] is an order-convex subset of B∞.\iota_i[B_i] \text{ is an order-convex subset of } B_\infty.(6)✦

Assume CH from here on. If every fijf_{ij} is strong, then for every i∈Ji \in J the stage map ιi:Mi→M∞ is strong,\text{the stage map } \iota_i : M_i \to M_\infty \text{ is strong},(7)✦ and if moreover every MiM_i is an object, then M∞ is an object.M_\infty \text{ is an object}.(8)✦ If NN is a normal form and qi:Mi→Nq_i : M_i \to N, i∈Ji \in J, are strong maps with qj∘fij=qiq_j \circ f_{ij} = q_i whenever i≤ji \le j, then the induced map q:M∞→N is strong.\text{the induced map } q : M_\infty \to N \text{ is strong}.(9)✦

Let (F(i))i∈J(F(i))_{i \in J} be a family of objects of KK with F(i)≤KF(j)F(i) \le_K F(j) whenever i≤ji \le j. Then the family has a union UU that is an object of KK, and F(i)≤KU(i∈J),U≤KW(W∈K,F(i)≤KW for all i∈J).F(i) \le_K U \quad (i \in J), \qquad U \le_K W \quad (W \in K,\ F(i) \le_K W \text{ for all } i \in J).(10)✦

In the paper, the result reads: for a nonempty family (F(i))i∈J(F(i))_{i \in J} of objects of KK indexed by a set and directed under ≤K\le_K, the union UU is an object of KK with F(i)≤KUF(i) \le_K U for every ii, and if F(i)≤KWF(i) \le_K W for every ii, then U≤KWU \le_K W.

What Is Checked

The claims are stated over relational structures in the array language and their unions, over the class KK and its relation ≤K\le_K, defined under CH through presentations by normal forms, objects and strong maps, and over a directed system of normal forms with convex maps over a nonempty directed preorder, with its limit M∞M_\infty, its stage maps ιi\iota_i and the map induced by a compatible family of maps.

About these constructions the library proves that every map of normal forms is injective on points✦, that each ιi\iota_i is an order embedding of BiB_i into B∞B_\infty, that the stage maps together carry the direct limit of the sets of points of the MiM_i bijectively onto the points of M∞M_\infty✦, and that the map induced by a compatible family is injective on points✦.