OctoInformBeta

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

The hereditary encoding: Kuratowski pairs are injective, as are vertex codes over an injective map; they code the states of an interpretation program

Hereditarily finite codes for the states of interpretation programs.

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 𝔄\mathfrak A be a finite structure with universe AA. A computation by logical interpretations starts from 𝔄\mathfrak A and applies a two-dimensional interpretation again and again, so that each element of a state is a class of pairs of elements of the state before, and each element of the first state is a class of pairs of elements of AA. The item writes every element of every state as a hereditarily finite set over the atoms AA, the objects choiceless polynomial time computes with, built from the sets of the elements it comes from, and collects the sets built along a run into one family.

The set HF(A)\mathrm{HF}(A) of hereditarily finite sets over AA is the least set that contains the atoms of AA and every finite set of its own elements.✦ The von Neumann ordinal [j]∈HF(A)[j] \in \mathrm{HF}(A) of a natural number jj is defined by recursion: [0]=∅,[j+1]=[j]∪{[j]}.[0] = \emptyset, \qquad [j+1] = [j] \cup \{[j]\}.(1)✦

Interpretations and Programs

A finite structure 𝔖\mathfrak S over a set RR of binary relation symbols is a finite universe |𝔖||\mathfrak S| together with a binary relation r𝔖r^{\mathfrak S} on it for each r∈Rr \in R.✦ Formulas over RR are those of Härtig logic, first-order logic with equality and the Härtig quantifier: they are built from falsity, equations x=yx = y and atoms r(x,y)r(x, y) by negation, conjunction, existential quantification and the Härtig quantification 𝖧x(φ,ψ)\mathsf H x\,(\varphi, \psi) of two formulas in a new variable xx.✦ In 𝔖\mathfrak S under an assignment vv, the connectives and ∃\exists are read as usual, and 𝔖⊨𝖧x(φ,ψ)[v]⇔|{a∈|𝔖|:𝔖⊨φ[v,a/x]}|=|{a∈|𝔖|:𝔖⊨ψ[v,a/x]}|.\mathfrak S \models \mathsf H x\,(\varphi, \psi)[v] \iff \bigl|\{a \in |\mathfrak S| : \mathfrak S \models \varphi[v, a/x]\}\bigr| = \bigl|\{a \in |\mathfrak S| : \mathfrak S \models \psi[v, a/x]\}\bigr|.(2)✦

Let TT be a set of binary relation symbols. A two-dimensional interpretation II of structures over TT in structures over RR consists of Härtig formulas over RR: a domain formula δ(x1,x2)\delta(x_1, x_2), an identification formula ε(x1,x2,y1,y2)\varepsilon(x_1, x_2, y_1, y_2), and for each t∈Tt \in T a formula φt(x1,x2,y1,y2)\varphi_t(x_1, x_2, y_1, y_2) defining the relation tt between pairs.✦ On a finite structure 𝔖\mathfrak S over RR, its domain of pairs and its vertex set are DI(𝔖)={(s1,s2)∈|𝔖|2:𝔖⊨δ(s1,s2)},VI(𝔖)=DI(𝔖)/∼,D_I(\mathfrak S) = \{(s_1, s_2) \in |\mathfrak S|^2 : \mathfrak S \models \delta(s_1, s_2)\}, \qquad V_I(\mathfrak S) = D_I(\mathfrak S)/{\sim},(3) where ∼\sim is the equivalence relation on DI(𝔖)D_I(\mathfrak S) generated by linking (s1,s2)(s_1, s_2) to (s1′,s2′)(s'_1, s'_2) whenever 𝔖⊨ε(s1,s2,s1′,s2′)\mathfrak S \models \varepsilon(s_1, s_2, s'_1, s'_2). The structure I(𝔖)I(\mathfrak S) over TT that II defines in 𝔖\mathfrak S has universe VI(𝔖)V_I(\mathfrak S), and its elements are the vertices.

An interpretation program PP over a set RR of binary relation symbols consists of a finite set SS of binary relation symbols, the state symbols, an initial interpretation I0I_0 of structures over SS in structures over RR, a step interpretation IsI_s of structures over SS in structures over SS, and two Härtig sentences over SS, the halting condition and the output condition.✦ On a finite structure 𝔄\mathfrak A over RR, its state after jj steps is the structure 𝔖j\mathfrak S_j over the state symbols given by 𝔖0=I0(𝔄),𝔖j+1=Is(𝔖j).\mathfrak S_0 = I_0(\mathfrak A), \qquad \mathfrak S_{j+1} = I_s(\mathfrak S_j).(4)✦

The Claim

Definition 1. For a,b∈HF(A)a, b \in \mathrm{HF}(A), the Kuratowski pair of aa and bb is ⟨a,b⟩={{a},{a,b}},\langle a, b\rangle = \{\{a\}, \{a, b\}\},(5)✦ and it determines its components: for all a,b,c,d∈HF(A)a, b, c, d \in \mathrm{HF}(A), ⟨a,b⟩=⟨c,d⟩⟹a=c and b=d.\langle a, b\rangle = \langle c, d\rangle \implies a = c \text{ and } b = d.(6)✦ Let II be an interpretation of structures over TT in structures over RR, let 𝔖\mathfrak S be a finite structure over RR, and let e:|𝔖|→HF(A)e\colon |\mathfrak S| \to \mathrm{HF}(A). The payload of a vertex C∈VI(𝔖)C \in V_I(\mathfrak S) is the set of the pairs of images of the pairs in CC, SC={⟨e(s1),e(s2)⟩:(s1,s2)∈C}∈HF(A),S_C = \{\langle e(s_1), e(s_2)\rangle : (s_1, s_2) \in C\} \in \mathrm{HF}(A),(7)✦ The vertex code ej(C)e_j(C) of CC at level j∈ℕj \in \mathbb N is ej(C)=⟨[j],SC⟩.e_j(C) = \langle [j], S_C\rangle.(8) If ee is injective, then for every jj the vertex code is injective on VI(𝔖)V_I(\mathfrak S): for all C,C′∈VI(𝔖)C, C' \in V_I(\mathfrak S), ej(C)=ej(C′)⟹C=C′.e_j(C) = e_j(C') \implies C = C'.(9)✦ Let PP be an interpretation program over RR with initial interpretation I0I_0 and step interpretation IsI_s, let 𝔄\mathfrak A be a finite structure over RR with universe AA and states 𝔖j\mathfrak S_j, and let ι:A→HF(A)\iota\colon A \to \mathrm{HF}(A) send each element to itself as an atom. The codes of the states are the maps κj:|𝔖j|→HF(A)\kappa_j\colon |\mathfrak S_j| \to \mathrm{HF}(A) defined by recursion on jj: κ0(C)=⟨[1],{⟨ι(a1),ι(a2)⟩:(a1,a2)∈C}⟩,κj+1(C)=⟨[j+2],{⟨κj(s1),κj(s2)⟩:(s1,s2)∈C}⟩.\begin{aligned} \kappa_0(C) &= \bigl\langle [1], \{\langle \iota(a_1), \iota(a_2)\rangle : (a_1, a_2) \in C\}\bigr\rangle, \\ \kappa_{j+1}(C) &= \bigl\langle [j+2], \{\langle \kappa_j(s_1), \kappa_j(s_2)\rangle : (s_1, s_2) \in C\}\bigr\rangle. \end{aligned}(10)✦ For a bound B∈ℕB \in \mathbb N, the family of objects built from the codes is the sequence of finite subsets FjF_j of HF(A)\mathrm{HF}(A) given by F0=ℬB(𝔄),F1=F0∪𝒫(I0,𝔄,ι)∪𝒦1(I0,𝔄,ι),Fj+2=Fj+1∪𝒫(Is,𝔖j,κj)∪𝒦j+2(Is,𝔖j,κj),\begin{aligned} F_0 &= \mathcal B_B(\mathfrak A), \\ F_1 &= F_0 \cup \mathcal P(I_0, \mathfrak A, \iota) \cup \mathcal K_1(I_0, \mathfrak A, \iota), \\ F_{j+2} &= F_{j+1} \cup \mathcal P(I_s, \mathfrak S_j, \kappa_j) \cup \mathcal K_{j+2}(I_s, \mathfrak S_j, \kappa_j), \end{aligned}(11)✦ where ℬB(𝔄)\mathcal B_B(\mathfrak A) is the base family for the bound BB, and 𝒫(I,𝔖,e)\mathcal P(I, \mathfrak S, e) and 𝒦j(I,𝔖,e)\mathcal K_j(I, \mathfrak S, e) are the families of pair objects and of class objects at level jj that II builds on 𝔖\mathfrak S over ee.

What Is Checked

The definition is stated over the hereditarily finite sets over a set of atoms, with their singletons, doubletons and von Neumann ordinals, over finite structures with binary relations and the formulas of Härtig logic, and over two-dimensional interpretations, with their domains of pairs and vertex sets, and interpretation programs with their states.