OctoInformBeta

OpenAI preprint, September 2026 · §2. Countable diagrams and their tests

Definition 2.3: Under the continuum hypothesis, a coloring passes at a tuple tt when the colors of its subsequences code valid restrictions of one diagram

The full subsequence test for colorings of tuples.

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

Let II be a set of indices, and color the finite tuples of distinct elements of II. A color can code a diagram on a finite set of positions, the places of a tuple, a system of two binary relations and ordinal tags. The full subsequence test asks, at a tuple tt, whether the diagrams coded by the colors of the subsequences of tt are the parts of one diagram on the positions of tt.

Colors and Diagrams

A binary sequence is a map a:ℕ→{0,1}a \colon \mathbb{N} \to \{0, 1\}, and 2ω2^\omega is the set of binary sequences.✦ Binary sequences aa and bb are equal outside a finite set, written a=*ba =^* b, when they differ at finitely many places, and the palette SS of colors is the quotient of 2ω2^\omega by this relation: S=2ω/=*,a=*b⇔{k∈ℕ:a(k)≠b(k)} is finite.S = 2^\omega/{=^*}, \qquad a =^* b \iff \{k \in \mathbb{N} : a(k) \neq b(k)\} \text{ is finite}.(1)

Let AA be a set, whose elements are called positions. A label on AA is a pair (J,i)(J, i) in which JJ is a nonempty finite subset of AA and i∈ℕi \in \mathbb{N}✦, and the root of a position aa is the label ({a},0)(\{a\}, 0).✦ An injection e:A→Be \colon A \to B carries a label (J,i)(J, i) on AA to the label e*(J,i)=(e[J],i)e_*(J, i) = (e[J], i) on BB.✦ A diagram on AA is a triple D=(E,R,ρ)D = (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.✦

A diagram D=(E,R,ρ)D = (E, R, \rho) on AA is valid when EE is an equivalence relation and, for all labels x,x′,y,y′x, x', y, y' and all positions a,b∈Aa, b \in A, xEx′ and yEy′⟹(xRy⇔x′Ry′) and ρ(x)=ρ(x′),xRy⟹ρ(x)<ρ(y),(zRx⇔zRy for every label z)⟹xEy,({a},0)E({b},0)⟹a=b.\begin{gathered} x \mathrel{E} x' \text{ and } y \mathrel{E} y' \implies (x \mathrel{R} y \iff x' \mathrel{R} y') \text{ and } \rho(x) = \rho(x'), \\ x \mathrel{R} y \implies \rho(x) < \rho(y), \\ \bigl(z \mathrel{R} x \iff z \mathrel{R} y \text{ for every label } z\bigr) \implies x \mathrel{E} y, \\ (\{a\}, 0) \mathrel{E} (\{b\}, 0) \implies a = b. \end{gathered}(2)✦

For a diagram D=(E,R,ρ)D = (E, R, \rho) on BB and an injection e:A→Be \colon A \to B, the restriction D↾eD{\restriction}e of DD along ee is the diagram (Ee,Re,ρe)(E^e, R^e, \rho^e) on AA given by xEey⇔e*xEe*y,xRey⇔e*xRe*y,ρe(x)=ρ(e*x).x \mathrel{E^e} y \iff e_*x \mathrel{E} e_*y, \qquad x \mathrel{R^e} y \iff e_*x \mathrel{R} e_*y, \qquad \rho^e(x) = \rho(e_*x).(3)✦

Under the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0} = \aleph_1, the code ι\iota is an injection that assigns to each diagram DD on {0,…,m}\{0, \dots, m\}, for each m∈ℕm \in \mathbb{N}, a color ιm+1(D)∈S\iota_{m+1}(D) \in S, distinct diagrams, of equal or of different lengths, receiving distinct colors.

The Definition

Definition 1 (Full subsequence test). Let II be a set. A tuple from II is an injective map t:{0,…,n}→It \colon \{0, \dots, n\} \to I, for some n∈ℕn \in \mathbb{N}, of length n+1n + 1; the tuples from II form the set 𝒯(I)=⨆n∈ℕ{t:{0,…,n}→I:t injective}.\mathcal{T}(I) = \bigsqcup_{n \in \mathbb{N}} \{\, t \colon \{0, \dots, n\} \to I : t \text{ injective} \,\}.(4)✦ For a tuple tt of length n+1n + 1 and an order embedding e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\}, the subsequence of tt along ee is the tuple t∘et \circ e of length m+1m + 1, (t∘e)(j)=t(e(j))(0≤j≤m).(t \circ e)(j) = t(e(j)) \qquad (0 \le j \le m).(5)✦ Assume CH and let n∈ℕn \in \mathbb{N}. A family s=(se)es = (s_e)_e of colors in SS, indexed by the order embeddings e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\} for all m∈ℕm \in \mathbb{N}, passes when there is a diagram DD on {0,…,n}\{0, \dots, n\} such that D↾e is valid and ιm+1(D↾e)=sefor every order embedding e:{0,…,m}→{0,…,n}.D{\restriction}e \text{ is valid and } \iota_{m+1}(D{\restriction}e) = s_e \quad \text{for every order embedding } e \colon \{0, \dots, m\} \to \{0, \dots, n\}.(6)✦ A coloring c:𝒯(I)→Sc \colon \mathcal{T}(I) \to S passes the test at a tuple tt of length n+1n + 1 when the colors of the subsequences of tt form a family that passes: (c(t∘e))e passes,e ranging over the order embeddings {0,…,m}→{0,…,n}.\bigl(c(t \circ e)\bigr)_e \text{ passes}, \quad e \text{ ranging over the order embeddings } \{0, \dots, m\} \to \{0, \dots, n\}.(7)✦

In the paper, with [k][k] the set of positions of a tuple and JJ a nonempty subset of it, the definition reads: Tk((sJ)J)T_k((s_J)_J) holds when every sJs_J decodes under ι|J|\iota_{|J|} to a valid diagram DJD_J and DJ=D[k]↾JD_J = D_{[k]}{\restriction}J for every nonempty J⊆[k]J \subseteq [k], and colors attached to a tuple pass the test when this holds for the colors of its subsequences.

What Is Checked

The definition is stated over a set II with its tuples and their subsequences along order embeddings, the palette SS, the diagrams on {0,…,n}\{0, \dots, n\} with their restrictions and validity, and the code ι\iota under CH.

The library proves that equality outside a finite set is an equivalence relation on 2ω2^\omega✦.