OctoInformBeta

OpenAI preprint, September 2026 Β· Β§6. Encoding complete choiceless computations

Lemma 20: On transitive domains of hereditarily finite objects, CmC^m formulas define codes and relations of states, and sentences of scoped width below mm transfer

Counting logic defines coded program states below a step bound.

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

An interpretation program runs a choiceless computation on a finite structure 𝔄\mathfrak A: one interpretation of first-order logic with the HΓ€rtig quantifier builds the first state from 𝔄\mathfrak A, another builds each state from the one before, and a halting sentence and an output sentence are read on the states. Each element of a state is a class of pairs from the previous state, and it is coded by a hereditarily finite object over the elements of 𝔄\mathfrak A as atoms, built from its stage and the codes of the members of its class. The item shows that counting logic with mm variables defines these codes on a domain of hereditarily finite objects, by formulas that do not depend on the input, and that sentences about the states become sentences of counting logic about the domain.

Counting Logic and Uniform Definitions

A binary relational structure β„­\mathfrak C over a vocabulary Ξ›\Lambda with universe CC interprets every symbol of Ξ›\Lambda as a binary relation on CC.✦ The formulas of counting logic over Ξ›\Lambda with variable names from a set II are built from βŠ₯\bot, equations x=yx=y and atoms Ξ»(x,y)\lambda(x,y), for names x,y∈Ix,y\in I and symbols Ξ»βˆˆΞ›\lambda\in\Lambda, by negation, conjunction, existential quantification βˆƒxΟ†\exists x\,\varphi and, for each natural number nn, the counting quantifier βˆƒ=nxΟ†\exists^{=n}x\,\varphi; CmC^m is counting logic with the mm names x1,…,xmx_1,\dots,x_m.✦ Satisfaction β„­βŠ¨Ο†[v]\mathfrak C\models\varphi[v] under an assignment vv of elements of CC to the names is the usual one, with βˆƒ=nxΟ†\exists^{=n}x\,\varphi true when exactly nn elements aa of CC satisfy Ο†\varphi once xx is sent to aa.✦ The free variables of Ο†\varphi are the names that occur in it outside the scope of a quantifier binding them.✦

Let ΞΉ\iota be an index set and (β„­i)i∈ι(\mathfrak C_i)_{i\in\iota} a family of binary relational structures over Ξ›\Lambda with universes CiC_i. A family of pp-ary relations WiβŠ†CipW_i\subseteq C_i^p is uniformly definable in CmC^m when for every map Ξ±:{1,…,p}β†’{1,…,m}\alpha\colon\{1,\dots,p\}\to\{1,\dots,m\}, placing the arguments on names, there is one formula Ο†\varphi of CmC^m with free variables among xΞ±(1),…,xΞ±(p)x_{\alpha(1)},\dots,x_{\alpha(p)} such that for every i∈ιi\in\iota and every assignment vv β„­iβŠ¨Ο†[v]⇔(v(xΞ±(1)),…,v(xΞ±(p)))∈Wi.\mathfrak C_i\models\varphi[v]\iff \bigl(v(x_{\alpha(1)}),\dots,v(x_{\alpha(p)})\bigr)\in W_i .(1)✦

Hereditarily Finite Codes

The set HF(A)\mathrm{HF}(A) of hereditarily finite objects over a set AA of atoms is the least set that contains every atom of AA, as an object with no elements, and every finite set of its own members.✦ The set predicate holds of the sets of HF(A)\mathrm{HF}(A) and fails at the atoms.✦ In HF(A)\mathrm{HF}(A) one forms the singleton {a}\{a\}, the doubleton {a,b}\{a,b\}, the Kuratowski pair ⟨a,b⟩={{a},{a,b}}\langle a,b\rangle=\{\{a\},\{a,b\}\} and the von Neumann ordinals, with [0]=βˆ…[0]=\emptyset and [k+1]=[k]βˆͺ{[k]}[k+1]=[k]\cup\{[k]\}. A coding domain over AA is a set π’ŸβŠ†HF(A)\mathcal D\subseteq\mathrm{HF}(A) taken as the universe of a binary relational structure; it is transitive when every element of a set in π’Ÿ\mathcal D lies in π’Ÿ\mathcal D.✦

Interpretation Programs

A finite structure 𝔅\mathfrak B over a set Οƒ\sigma of binary relation symbols is a finite universe V(𝔅)V(\mathfrak B) with a binary relation r𝔅r^{\mathfrak B} on it for each rβˆˆΟƒr\in\sigma.✦ The formulas of FO+𝖧\mathrm{FO}+\mathsf H over Οƒ\sigma in nn variables are built from βŠ₯\bot, equations xi=xjx_i=x_j and atoms r(xi,xj)r(x_i,x_j) by negation, conjunction, βˆƒyΟ†\exists y\,\varphi and the HΓ€rtig quantifier 𝖧y(Ο†,ψ)\mathsf Hy\,(\varphi,\psi), for Ο†\varphi and ψ\psi in the n+1n+1 variables y,x1,…,xny,x_1,\dots,x_n; 𝖧y(Ο†,ψ)\mathsf Hy\,(\varphi,\psi) holds when as many elements satisfy Ο†\varphi as satisfy ψ\psi.✦ A sentence ψ\psi, a formula in no variables, holds in 𝔅\mathfrak B, written π”…βŠ¨Οˆ\mathfrak B\models\psi, when it is satisfied under the empty assignment.✦ The scoped width of a formula is the largest number of variables in scope at an atom or an occurrence of βŠ₯\bot in it.✦

A two-dimensional interpretation ℐ\mathcal I of structures over a set Οƒβ€²\sigma' of binary relation symbols in structures over Οƒ\sigma consists of formulas of FO+𝖧\mathrm{FO}+\mathsf H over Οƒ\sigma: a domain formula Ξ΄(x1,x2)\delta(x_1,x_2), an equivalence formula Ξ·(xβ€Ύ,yβ€Ύ)\eta(\bar x,\bar y) and, for each tβˆˆΟƒβ€²t\in\sigma', a relation formula ρt(xβ€Ύ,yβ€Ύ)\rho_t(\bar x,\bar y), where xβ€Ύ\bar x and yβ€Ύ\bar y are pairs of variables.✦ On a finite structure 𝔅\mathfrak B over Οƒ\sigma, its domain Dℐ(𝔅)D_{\mathcal I}(\mathfrak B) is the set of pairs aβ€Ύ\bar a with π”…βŠ¨Ξ΄[aβ€Ύ]\mathfrak B\models\delta[\bar a]; two pairs aβ€Ύ,bβ€Ύ\bar a,\bar b of the domain are linked when π”…βŠ¨Ξ·[aβ€Ύ,bβ€Ύ]\mathfrak B\models\eta[\bar a,\bar b], and β‰ˆ\approx is the equivalence relation on Dℐ(𝔅)D_{\mathcal I}(\mathfrak B) generated by the links. The classes [aβ€Ύ][\bar a] are the vertices of ℐ\mathcal I on 𝔅\mathfrak B, and the quotient Dℐ(𝔅)/β‰ˆD_{\mathcal I}(\mathfrak B)/{\approx} is the universe of the interpreted structure ℐ(𝔅)\mathcal I(\mathfrak B).✦

For a binary relation rr on a set XX, reachability in tt rounds is the binary relation β†’rt\to^t_r on XX defined by recursion on tt: aβ†’r0ba\to^0_r b when aa and bb are joined by one step of rr, and aβ†’rt+1ba\to^{t+1}_r b when aβ†’rtba\to^t_r b, or aβ†’rtda\to^t_r d for some dd joined to bb by one step of rr.✦

An interpretation program PP over a vocabulary RR consists of a finite set Οƒ\sigma of binary state symbols, an interpretation ℐinit\mathcal I_{\mathrm{init}} of structures over Οƒ\sigma in structures over RR, an interpretation ℐstep\mathcal I_{\mathrm{step}} of structures over Οƒ\sigma in structures over Οƒ\sigma, and two sentences of FO+𝖧\mathrm{FO}+\mathsf H over Οƒ\sigma, the halting condition ψhalt\psi_{\mathrm{halt}} and the output condition ψout\psi_{\mathrm{out}}.✦ The state 𝔄j\mathfrak A_j of PP after jj steps on a finite structure 𝔄\mathfrak A over RR is the structure over Οƒ\sigma with 𝔄0=ℐinit(𝔄)\mathfrak A_0=\mathcal I_{\mathrm{init}}(\mathfrak A) and 𝔄j+1=ℐstep(𝔄j)\mathfrak A_{j+1}=\mathcal I_{\mathrm{step}}(\mathfrak A_j).✦

Coding the States

Let ℐ\mathcal I be an interpretation, 𝔅\mathfrak B a finite structure and e:V(𝔅)β†’HF(A)e\colon V(\mathfrak B)\to\mathrm{HF}(A) a map coding its elements. The payload of a vertex cc of ℐ\mathcal I on 𝔅\mathfrak B and its code at stage jj are the objects ple(c)={⟨e(a1),e(a2)⟩:(a1,a2)∈c},vce,j(c)=⟨[j],ple(c)⟩.\mathrm{pl}_e(c)=\bigl\{\langle e(a_1),e(a_2)\rangle : (a_1,a_2)\in c\bigr\},\qquad \mathrm{vc}_{e,j}(c)=\bigl\langle[j],\mathrm{pl}_e(c)\bigr\rangle .(2)

The code Ξ³j\gamma_j of a program PP at step jj on 𝔄\mathfrak A maps V(𝔄j)V(\mathfrak A_j) into HF(V(𝔄))\mathrm{HF}(V(\mathfrak A)): Ξ³0\gamma_0 is the code at stage 11 for ℐinit\mathcal I_{\mathrm{init}} on 𝔄\mathfrak A, each element of 𝔄\mathfrak A coded by itself as an atom, and Ξ³j+1\gamma_{j+1} is the code at stage j+2j+2 for ℐstep\mathcal I_{\mathrm{step}} on 𝔄j\mathfrak A_j, the elements of 𝔄j\mathfrak A_j coded by Ξ³j\gamma_j.✦ For a bound BB, the trace family of PP on 𝔄\mathfrak A is the increasing sequence β„±0βŠ†β„±1βŠ†β‹―\mathcal F_0\subseteq\mathcal F_1\subseteq\cdots of finite subsets of HF(V(𝔄))\mathrm{HF}(V(\mathfrak A)) in which β„±0\mathcal F_0 is a base family fixed by BB and β„±j+1\mathcal F_{j+1} adds to β„±j\mathcal F_j the pairs of codes and the vertex codes that arise in building Ξ³j\gamma_j.✦

Now let (β„­i)i∈ι(\mathfrak C_i)_{i\in\iota} be binary relational structures over Ξ›\Lambda on coding domains π’Ÿi\mathcal D_i, and let 𝔅i\mathfrak B_i be finite structures over Οƒ\sigma with maps ei:V(𝔅i)β†’π’Ÿie_i\colon V(\mathfrak B_i)\to\mathcal D_i. The family (𝔅i,ei)i∈ι(\mathfrak B_i,e_i)_{i\in\iota} is state-definable in CmC^m when the images ei(V(𝔅i))e_i(V(\mathfrak B_i)) and, for each rβˆˆΟƒr\in\sigma, the relations {(ei(a),ei(b)):r𝔅i(a,b)}\bigl\{(e_i(a),e_i(b)) : r^{\mathfrak B_i}(a,b)\bigr\}(3)✦ are uniformly definable in CmC^m. Let ℐ\mathcal I be an interpretation in structures over Οƒ\sigma. The encoded domain of ℐ\mathcal I on 𝔅i\mathfrak B_i is the set of pairs (ei(a1),ei(a2))(e_i(a_1),e_i(a_2)) with (a1,a2)∈Dℐ(𝔅i)(a_1,a_2)\in D_{\mathcal I}(\mathfrak B_i), and the encoded equivalence of ℐ\mathcal I on 𝔅i\mathfrak B_i is the set of quadruples (ei(a1),ei(a2),ei(b1),ei(b2))(e_i(a_1),e_i(a_2),e_i(b_1),e_i(b_2)) with aβ€Ύβ‰ˆbβ€Ύ\bar a\approx\bar b in Dℐ(𝔅i)D_{\mathcal I}(\mathfrak B_i).

The Claim

Theorem 1. Let PP be an interpretation program over RR with state symbols Οƒ\sigma, let (𝔄i)i∈ι(\mathfrak A_i)_{i\in\iota} be finite structures over RR, and let BB, KK and mm be natural numbers. For each ii, let π’ŸiβŠ†HF(V(𝔄i))\mathcal D_i\subseteq\mathrm{HF}(V(\mathfrak A_i)) be a transitive coding domain that contains every ordinal [k][k] and the trace family β„±K\mathcal F_K of PP on 𝔄i\mathfrak A_i for the bound BB, with a structure β„­i\mathfrak C_i in which membership and the set predicate are uniformly definable in CmC^m. Then, with 𝔄i,j\mathfrak A_{i,j} the state of PP after jj steps on 𝔄i\mathfrak A_i and Ξ³j\gamma_j its code, (𝔄i,j,Ξ³j)i∈ιis state-definable in Cm for every j<K.(\mathfrak A_{i,j},\gamma_j)_{i\in\iota}\ \text{is state-definable in } C^m \text{ for every } j<K .(4)✦ If finite structures 𝔅i\mathfrak B_i over Οƒ\sigma with injective maps ei:V(𝔅i)β†’π’Ÿie_i\colon V(\mathfrak B_i)\to\mathcal D_i form a family state-definable in CmC^m, each 𝔅i\mathfrak B_i has at most BB elements, and ψ\psi is a sentence of FO+𝖧\mathrm{FO}+\mathsf H over Οƒ\sigma of scoped width less than mm, then there is a sentence Ο†\varphi of CmC^m with β„­iβŠ¨Ο†β‡”π”…i⊨ψfor every i∈ι.\mathfrak C_i\models\varphi\iff\mathfrak B_i\models\psi\qquad\text{for every } i\in\iota .(5)✦ For such 𝔅i\mathfrak B_i and eie_i, an interpretation ℐ\mathcal I in structures over Οƒ\sigma, and all kk and jj, the following relations on π’Ÿi\mathcal D_i are uniformly definable in CmC^m: {(z,x,y):z=⟨x,y⟩},\bigl\{(z,x,y) : z=\langle x,y\rangle\bigr\},(6)✦ {z:z=[k]},\bigl\{z : z=[k]\bigr\},(7)✦ {(z,ei(a1),ei(a2)):aβ€ΎβˆˆDℐ(𝔅i),z=plei([aβ€Ύ])},\bigl\{(z,e_i(a_1),e_i(a_2)) : \bar a\in D_{\mathcal I}(\mathfrak B_i),\ z=\mathrm{pl}_{e_i}([\bar a])\bigr\},(8) {(z,ei(a1),ei(a2)):aβ€ΎβˆˆDℐ(𝔅i),z=vcei,j([aβ€Ύ])}.\bigl\{(z,e_i(a_1),e_i(a_2)) : \bar a\in D_{\mathcal I}(\mathfrak B_i),\ z=\mathrm{vc}_{e_i,j}([\bar a])\bigr\}.(9) For a binary relation rr on a finite set with at most β„“\ell elements, generating the equivalence relation ≑r\equiv_r, a≑rb⇔aβ†’rβ„“b,a\equiv_r b\iff a\to^{\ell}_r b ,(10)✦ and for finite sets XX and YY in bijection with sets UU and VV, with |X|≀ℓ|X|\le\ell, |U|=|V|=sfor some s≀ℓ⇔|X|=|Y|.|U|=|V|=s\ \text{for some } s\le\ell\iff|X|=|Y| .(11)✦

In the paper, the result reads: at every stage through halt, a formula UjU_j of CmC^m selects exactly the vertex codes of the state 𝔄j\mathfrak A_j and each formula RjR_j defines exactly its corresponding binary state relation, and the translated halt and output sentences are exact at every stage jβ‰₯1j\ge1 through halt.

The box gives the selection of the vertex codes and the definition of the state relations for every step j<Kj<K, and the exactness of the halt and output sentences from (5) with ψ\psi the halting or the output condition.

What Is Checked

The claim is stated over counting logic CmC^m with its satisfaction and free variables, uniform definability (1), the hereditarily finite objects with their pairs, ordinals and set predicate, coding domains, the logic FO+𝖧\mathrm{FO}+\mathsf H with scoped width, two-dimensional interpretations with the equivalence generated by their links, reachability in tt rounds, interpretation programs and their states, payloads and vertex codes (2), the codes Ξ³j\gamma_j, the trace family and state-definability (3). Under the hypotheses of the box, the library proves that every element of 𝔄i\mathfrak A_i, as an atom, lies in π’Ÿi\mathcal D_i✦, and that for j<Kj<K every code Ξ³j(c)\gamma_j(c) of an element cc of 𝔄i,j\mathfrak A_{i,j} lies in π’Ÿi\mathcal D_i✦.