OctoInformBeta

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

Proof of Theorem 14: induction on formulas: For s≥1s \geq 1, in hereditarily ss-supported sets, when tuples of one counting type lie in one orbit

Assignments represented alike satisfy the same counting formulas.

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 SS and TT be structures over one vocabulary RR of binary relation symbols, on sets of atoms AA and BB, and let a group GG act on AA and a group HH on BB. Over AA lie the hereditarily finite sets in which choiceless polynomial time computes. Fix a number s≥1s \geq 1. A hereditarily ss-supported set over AA is a set that, like each of its members at every depth, is fixed by every element of GG that fixes some ss atoms chosen for it; read these sets as a structure with membership, and over BB, with HH, do the same. The question is when a formula of counting logic holds in the first of these structures at an assignment of sets over AA exactly when it holds in the second at an assignment of sets over BB. The comparison goes through the atoms: a set is described by a set-builder form over a tuple of atoms, and tuples of atoms are compared by their counting types.

Counting Types

A binary relational structure SS over RR with universe AA interprets each symbol r∈Rr \in R as a binary relation rSr^S on AA.✦ The counting formulas over RR with variable names from a set II are built from ⊥\bot, equations x=yx = y and atoms r(x,y)r(x, y), for x,y∈Ix, y \in I and r∈Rr \in R, by negation, conjunction, existential quantification ∃x\exists x and exact counting quantification ∃=nx\exists^{=n} x for n∈ℕn \in \mathbb{N}; with hh names, they are the formulas of ChC^h.✦ Satisfaction S⊨φ[v]S \models \varphi[v] under an assignment v:I→Av \colon I \to A is defined by recursion on φ\varphi, the formula ∃=nxφ\exists^{=n} x\, \varphi holding when exactly nn elements cc of AA satisfy φ\varphi under vv changed to send xx to cc.✦ The free variables of φ\varphi are the names occurring in it outside the scope of a quantifier binding them.✦

The type in SS of an assignment v:I→Av \colon I \to A, relative to a finite set N⊆IN \subseteq I of names, is the set of counting formulas with free variables in NN that hold in SS under vv.✦ For a tuple a=(aj)j∈Ja = (a_j)_{j \in J} of elements of AA, with JJ finite, and an injection e:J→Ie \colon J \to I placing its entries at names, the counting type of aa is the type of the assignment sending each e(j)e(j) to aja_j, relative to the image e(J)e(J): tp⁡eS(a)={φ∣free⁡(φ)⊆e(J) and S⊨φ[aj/e(j)]j∈J}.\operatorname{tp}^S_e(a) = \{\varphi \mid \operatorname{free}(\varphi) \subseteq e(J) \text{ and } S \models \varphi[a_j / e(j)]_{j \in J}\}.(1)✦

With respect to GG, the structure SS is homogeneous for JJ-tuples placed by ee when tuples of one counting type lie in one orbit of GG: for all a,a′∈AJa, a' \in A^J, tp⁡eS(a)=tp⁡eS(a′)⟹there is g∈G with gaj=aj′ for all j∈J.\operatorname{tp}^S_e(a) = \operatorname{tp}^S_e(a') \implies \text{there is } g \in G \text{ with } g a_j = a'_j \text{ for all } j \in J.(2)

Hereditarily Supported Sets

The hereditarily finite (HF) sets over AA form the collection HF(A)\mathrm{HF}(A) of the atoms of AA, each an urelement with no elements, and of the finite sets of members of HF(A)\mathrm{HF}(A), two sets being equal when they have the same elements; GG acts on HF(A)\mathrm{HF}(A) through the atoms.✦ A tuple α=(α0,…,αk−1)\alpha = (\alpha_0, \dots, \alpha_{k-1}) of atoms supports x∈HF(A)x \in \mathrm{HF}(A) when every g∈Gg \in G that fixes each αi\alpha_i fixes xx.✦ An object xx of HF(A)\mathrm{HF}(A) is ss-supported when some ss-tuple of atoms supports it✦, and hereditarily ss-supported when xx and every object reached from it by finitely many steps down the membership relation are ss-supported.✦ The set HFsG(A)\mathrm{HF}^G_s(A) is the set of all hereditarily ss-supported objects of HF(A)\mathrm{HF}(A) with respect to GG.

The HF vocabulary over RR has a membership symbol ∈\in, an atom symbol At\mathrm{At} and a copy of each symbol of RR.✦ The HF structure HFsG(S)\mathrm{HF}^G_s(S) of SS is the structure over the HF vocabulary with universe HFsG(A)\mathrm{HF}^G_s(A) in which ∈\in is membership, At(x,y)\mathrm{At}(x, y) holds when xx is an atom, and r(x,y)r(x, y) holds when xx and yy are atoms cc and dd with rS(c,d)r^S(c, d).✦ Over TT and HH the same construction gives HFsH(B)\mathrm{HF}^H_s(B) and HFsH(T)\mathrm{HF}^H_s(T).

Set-builder Forms

A set-builder form over the indices j<sj < s with labels in a set LL is a finite tree: either a leaf carrying an index j<sj < s, or a set node with branches i<ni < n, for some n∈ℕn \in \mathbb{N}, each branch carrying a child form πi\pi_i and a label θi∈L\theta_i \in L.✦ The forms used here are labelled by sets of counting formulas over RR in the names II. Fix an injection e2e_2 placing two copies of {0,…,s−1}\{0, \dots, s-1\} at names in II. The value πS(a)∈HF(A)\pi^S(a) \in \mathrm{HF}(A) of a form π\pi at an ss-tuple aa of atoms of AA is the atom aja_j when π\pi is a leaf with index jj, and, when π\pi is a set node with children πi\pi_i and labels θi\theta_i for i<ni < n, the set πS(a)={πiS(b)∣i<n,b∈As,tp⁡e2S(b,a)=θi},\pi^S(a) = \{\pi_i^S(b) \mid i < n,\ b \in A^s,\ \operatorname{tp}^S_{e_2}(b, a) = \theta_i\},(3)✦ where (b,a)(b, a) is the 2s2s-tuple with bb on the first copy and aa on the second.

Let VV be a finite set of variable names and eVe_V an injection of V×{0,…,s−1}V \times \{0, \dots, s-1\} into II. Assignments v:V→HFsG(A)v \colon V \to \mathrm{HF}^G_s(A) and w:V→HFsH(B)w \colon V \to \mathrm{HF}^H_s(B) are represented alike when there are forms πx\pi_x, for x∈Vx \in V, and parameter tuples a=(ax,j)a = (a_{x,j}) of atoms of AA and b=(bx,j)b = (b_{x,j}) of atoms of BB, indexed by x∈Vx \in V and j<sj < s, with πxS(ax)=v(x) and πxT(bx)=w(x) for all x∈V,tp⁡eVS(a)=tp⁡eVT(b),\pi_x^S(a_x) = v(x) \text{ and } \pi_x^T(b_x) = w(x) \text{ for all } x \in V, \qquad \operatorname{tp}^S_{e_V}(a) = \operatorname{tp}^T_{e_V}(b),(4)✦ where axa_x is the ss-tuple (ax,j)j<s(a_{x,j})_{j < s} and bxb_x likewise.

The Claim

Theorem 1. Let s≥1s \geq 1. Let SS and TT be binary relational structures over RR on sets of atoms AA and BB, with a group GG acting on AA and a group HH acting on BB; let II be a set of variable names, VV a finite set of variable names, and e2e_2 and eVe_V injections of two copies of {0,…,s−1}\{0, \dots, s-1\} and of V×{0,…,s−1}V \times \{0, \dots, s-1\} into II. Suppose that SS, with respect to GG, and TT, with respect to HH, are homogeneous (2) both for 2s2s-tuples placed by e2e_2 and for parameter tuples, indexed by V×{0,…,s−1}V \times \{0, \dots, s-1\} and placed by eVe_V. Let v:V→HFsG(A)v \colon V \to \mathrm{HF}^G_s(A) and w:V→HFsH(B)w \colon V \to \mathrm{HF}^H_s(B) be assignments represented alike (4). Then every counting formula φ\varphi over the HF vocabulary with variable names from VV satisfies HFsG(S)⊨φ[v]⇔HFsH(T)⊨φ[w].\mathrm{HF}^G_s(S) \models \varphi[v] \iff \mathrm{HF}^H_s(T) \models \varphi[w].(5)✦

What Is Checked

The claim is stated over counting formulas and their satisfaction, the counting types (1) and homogeneity (2), the hereditarily ss-supported sets with their HF structure, the values (3) of set-builder forms, and assignments represented alike (4).