OctoInformBeta

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

Lemma 16: φ*α\varphi^*\alpha is supported by α\alpha; when s>0s>0 and counting types of 2s2s-tuples determine orbits, every hereditarily ss-supported object is such a value

Values of forms are hereditarily supported and equivariant.

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

Take a finite structure SS with binary relations on a set AA of atoms, and a group GG acting on AA by automorphisms of SS. A program of choiceless polynomial time over SS computes with hereditarily finite sets over AA, and GG moves these sets as it moves the atoms. The question is which of these sets have a support of ss atoms at every level of membership, and how each of them is named from ss atoms in counting logic. The answer is given by forms, set-builder terms over a tuple of ss atoms whose steps are guarded by counting types.

Counting Types

A binary relational structure SS over a vocabulary RR with universe AA interprets every symbol r∈Rr\in R as a binary relation rSr^S on AA.✦ A formula of counting logic over RR with variable names from a set II is ⊥\bot, an equation x=yx=y or an atom r(x,y)r(x,y) with x,y∈Ix,y\in I and r∈Rr\in R, or is built from formulas by negation, conjunction, existential quantification ∃x\exists x and the counting quantifiers ∃=nx\exists^{=n}x for n∈ℕn\in\mathbb{N}; for finite II these are the formulas of C|I|C^{|I|}.✦ Satisfaction S⊨ψ[v]S\models\psi[v] of a formula ψ\psi under an assignment v:I→Av\colon I\to A is the usual one, with ∃=nxψ\exists^{=n}x\,\psi true under vv when exactly nn elements a∈Aa\in A make ψ\psi true under v[x↦a]v[x\mapsto a].✦

The type of an assignment v:I→Av\colon I\to A in SS relative to a finite set N⊆IN\subseteq I of names is the set of formulas whose free variables lie in NN and which SS satisfies under vv: tp⁡NS(v)={ψ:free⁡(ψ)⊆N,S⊨ψ[v]}.\operatorname{tp}^S_N(v)=\{\psi : \operatorname{free}(\psi)\subseteq N,\ S\models\psi[v]\}.(1)✦ For an injection e:J→Ie\colon J\to I and a tuple a∈AJa\in A^J over a nonempty AA, the counting type tp⁡eS(a)\operatorname{tp}^S_e(a) of aa is the type, relative to the names e(J)e(J) of the tuple, of the assignment that sends e(j)e(j) to aja_j for each j∈Jj\in J and every other name to a fixed element of AA.✦

Fix s∈ℕs\in\mathbb{N} and an injection ee of two disjoint copies of {0,…,s−1}\{0,\dots,s-1\} into II. For tuples β,α∈As\beta,\alpha\in A^s, βα\beta\alpha is the 2s2s-tuple with β\beta on the first copy and α\alpha on the second, and tp⁡(βα)\operatorname{tp}(\beta\alpha) is its counting type under ee.

Hereditarily Finite Objects and Supports

The set HF(A)\mathrm{HF}(A) of hereditarily finite objects over a set AA of atoms is the smallest set that contains the atoms and every finite subset of itself.✦ A group GG acting on AA acts on HF(A)\mathrm{HF}(A) by g{x1,…,xk}={gx1,…,gxk}g\{x_1,\dots,x_k\}=\{gx_1,\dots,gx_k\} and on tuples of atoms entrywise.

A tuple α∈Ak\alpha\in A^k supports an object x∈HF(A)x\in\mathrm{HF}(A) when every element of GG that fixes each entry of α\alpha fixes xx: gα=α⇒gx=xfor all g∈G.g\alpha=\alpha\ \Longrightarrow\ gx=x\qquad\text{for all } g\in G.(2)✦ For s∈ℕs\in\mathbb{N}, an object x∈HF(A)x\in\mathrm{HF}(A) is ss-supported when some tuple α∈As\alpha\in A^s supports xx.✦ An object x∈HF(A)x\in\mathrm{HF}(A) is hereditarily ss-supported when xx, its elements, their elements and so on down the membership relation are all ss-supported; HFsG(A)\mathrm{HF}^G_s(A) is the set of these objects.✦

Forms and Their Values

A form over an index set JJ with labels in a set LL is a finite tree that is either an atom node carrying an index j∈Jj\in J or a set node with branches 0,…,n−10,\dots,n-1 for some n∈ℕn\in\mathbb{N}, branch ii carrying a form φi\varphi_i over JJ with labels in LL and a label Ti∈LT_i\in L.✦

Given SS and ee, the value φ*α∈HF(A)\varphi^*\alpha\in\mathrm{HF}(A) of a form φ\varphi over {0,…,s−1}\{0,\dots,s-1\} whose labels are sets of formulas of counting logic over RR with names from II, at a tuple α∈As\alpha\in A^s, is defined by recursion on φ\varphi. An atom node with index jj has as value the atom αj\alpha_j; a set node with branches (φi,Ti)i<n(\varphi_i,T_i)_{i<n} has as value φ*α={φi*β:i<n,β∈As,tp⁡(βα)=Ti}.\varphi^*\alpha=\{\varphi_i^*\beta : i<n,\ \beta\in A^s,\ \operatorname{tp}(\beta\alpha)=T_i\}.(3)✦

The Claim

Theorem 1. Let SS be a binary relational structure over RR on a finite nonempty set AA of atoms, let a group GG act on AA by automorphisms of SS, let s∈ℕs\in\mathbb{N}, and let ee place two disjoint copies of {0,…,s−1}\{0,\dots,s-1\} at distinct names of a finite set II. For every form φ\varphi and every tuple α∈As\alpha\in A^s, φ*α∈HFsG(A),\varphi^*\alpha\in\mathrm{HF}^G_s(A),(4)✦ every g∈Gg\in G with gα=αg\alpha=\alpha satisfies g(φ*α)=φ*α,g(\varphi^*\alpha)=\varphi^*\alpha,(5)✦ and every g∈Gg\in G satisfies g(φ*α)=φ*(gα).g(\varphi^*\alpha)=\varphi^*(g\alpha).(6)✦ Conversely, suppose that s>0s>0 and that any two 2s2s-tuples p,qp,q of atoms with the same counting type under ee satisfy gp=qgp=q for some g∈Gg\in G. Then for every x∈HFsG(A)x\in\mathrm{HF}^G_s(A) there are a form φ\varphi and a tuple α∈As\alpha\in A^s with x=φ*α.x=\varphi^*\alpha.(7)✦

In the paper, the result reads: every value φ*α\varphi^*\alpha belongs to DiD_i and is supported by α\alpha, every object of DiD_i has such a representation, and g(φ*α)=φ*(gα)g(\varphi^*\alpha)=\varphi^*(g\alpha) for every g∈Kig\in K_i, the paper’s DiD_i and KiK_i standing where the page has HFsG(A)\mathrm{HF}^G_s(A) and GG.

What Is Checked

The claim is stated over binary relational structures on a finite nonempty set of atoms with a group acting by automorphisms, the counting types of tuples of atoms in counting logic with names from a finite set, forms labelled by sets of formulas and their values in HF(A)\mathrm{HF}(A), and the supports, ss-supports and hereditary ss-supports of hereditarily finite objects.