OctoInformBeta

OpenAI preprint, September 2026 · §5. From atom types to hereditarily finite sets · §5

Molecules and forms: Atomic forms cjc_j, set forms listing labelled pairs (ψ,ρ)(\psi,\rho), and the value φ*α\varphi*\alpha of a form at a molecule α\alpha

Forms turn types of atom tuples into hereditarily finite sets.

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

A program of choiceless polynomial time computes over a finite structure by building hereditarily finite sets over its atoms. Forms describe such sets from a short tuple of atoms, a molecule, through the counting types of tuples alone: a form is a finite labelled tree, and its value at a molecule α\alpha is a hereditarily finite set over the atoms. With molecules of length one, a form can send an atom aa to the set of atoms bb for which the pair (b,a)(b,a) has a prescribed type ρ\rho, and deeper forms give sets of such sets.

Counting Types and Hereditarily Finite Sets

A binary relational structure 𝔄\mathfrak A over a vocabulary RR with universe AA interprets every symbol r∈Rr\in R as a binary relation r𝔄r^{\mathfrak A} on AA; the elements of AA are its atoms.✦

A formula of the counting logic over RR with variable names from a set II is falsity, an equation x=yx=y or a relational atom r(x,y)r(x,y) between names, or is built from formulas by negation, conjunction, existential quantification and exact counting quantification: θ::=⊥∣x=y∣r(x,y)∣¬θ∣θ∧χ∣∃xθ∣∃=nxθ,\theta\;::=\;\bot\mid x=y\mid r(x,y)\mid\neg\theta\mid\theta\wedge\chi\mid\exists x\,\theta \mid\exists^{=n}x\,\theta,(1)✦ with x,y∈Ix,y\in I, r∈Rr\in R and n∈ℕn\in\mathbb N, where ∃=nxθ\exists^{=n}x\,\theta says that exactly nn values of xx satisfy θ\theta. The counting logic ChC^h over RR consists of the formulas (1) whose variable names come from a set II of hh names.

Fix a finite set JJ of positions. A molecule of 𝔄\mathfrak A is a tuple α∈AJ\alpha\in A^J of atoms, one at each position; for J={1,…,s}J=\{1,\dots,s\} it is a tuple of ss atoms. Fix also an injective map e:J×{1,2}→Ie\colon J\times\{1,2\}\to I, naming two copies of the positions. The type tp⁡(β,α)\operatorname{tp}(\beta,\alpha) of two molecules β\beta and α\alpha is the set of formulas (1) that hold in 𝔄\mathfrak A when each name e(j,1)e(j,1) denotes βj\beta_j and each name e(j,2)e(j,2) denotes αj\alpha_j.

The set HF(A)\mathrm{HF}(A) of hereditarily finite sets over the atoms AA is the least set that contains every atom of AA and every finite set of its own elements.✦

The Definition

Definition 1. Let JJ be a set of positions, not necessarily finite, and LL a set of labels. The set of forms over JJ with labels in LL is the least set that contains an atomic form cjc_j for each position j∈Jj\in J and, for every n∈ℕn\in\mathbb N, forms ψ1,…,ψn\psi_1,\dots,\psi_n and labels ρ1,…,ρn∈L\rho_1,\dots,\rho_n\in L, the set form listing the pairs (ψi,ρi)(\psi_i,\rho_i): φ::=cj∣[(ψ1,ρ1),…,(ψn,ρn)].\varphi\;::=\;c_j\;\mid\;[(\psi_1,\rho_1),\dots,(\psi_n,\rho_n)].(2)✦ Now let JJ be finite, let 𝔄\mathfrak A be a finite binary relational structure over RR with universe AA, let ee be as above, and let the labels be sets of counting formulas over RR and II. The value φ*α∈HF(A)\varphi*\alpha\in\mathrm{HF}(A) of a form φ\varphi at a molecule α∈AJ\alpha\in A^J is defined by recursion on φ\varphi: cj*α=αj,[(ψ1,ρ1),…,(ψn,ρn)]*α=⋃i=1n{ψi*β:β∈AJ,tp⁡(β,α)=ρi}.c_j*\alpha=\alpha_j,\qquad [(\psi_1,\rho_1),\dots,(\psi_n,\rho_n)]*\alpha =\bigcup_{i=1}^{n}\{\psi_i*\beta:\beta\in A^J,\ \operatorname{tp}(\beta,\alpha)=\rho_i\}.(3)✦

In the paper, the result reads: a molecule is a tuple α∈Ais\alpha\in A_i^s of ss atoms, the forms are the atomic forms c1,…,csc_1,\dots,c_s and the set forms, finite sets of pairs (ψ,ρ)(\psi,\rho) with ψ\psi a form and ρ\rho a realized CMC^M type of length 2s2s, and cj*α=αjc_j*\alpha=\alpha_j and φ*α={ψ*β:(ψ,ρ)∈φ,tp⁡M(β,α)=ρ}\varphi*\alpha=\{\psi*\beta:(\psi,\rho)\in\varphi,\ \operatorname{tp}_M(\beta,\alpha)=\rho\}, where AiA_i is the universe AA, J={1,…,s}J=\{1,\dots,s\}, CMC^M is the logic ChC^h with h=Mh=M, and tp⁡M\operatorname{tp}_M is the type in CMC^M.

What Is Checked

The forms (2) are defined over any set of positions and any set of labels, and their value (3) over a finite binary relational structure 𝔄\mathfrak A with universe AA, a finite set JJ of positions, an injective naming ee of two copies of JJ by variable names of the counting logic, and labels that are sets of counting formulas.