OctoInformBeta

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

Lemma 17: Pairs of tuples of equal counting type give form values agreeing on equality and membership; tuples represented alike agree on atomhood and base relations

Counting types determine the atomic facts of form values.

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 choiceless computation on a structure works with hereditarily finite sets over its atoms, and lower bounds for choiceless polynomial time compare the sets built over two structures that counting logic does not distinguish. Here such a set is described by a form: a finite tree whose leaves name entries of a tuple α\alpha of atoms and whose set nodes collect the values of their children at every tuple β\beta for which the pair (β,α)(\beta, \alpha) has a prescribed type in counting logic.

The question is how much of these sets the types of the parameters fix. Take pairs of tuples (α,β)(\alpha, \beta) and (α′,β′)(\alpha', \beta'), possibly over two different structures, of the same counting type, and two forms φ\varphi and ψ\psi. Is the value of φ\varphi at α\alpha equal to, or a member of, the value of ψ\psi at β\beta exactly when the same holds at α′\alpha' and β′\beta', and do sets defined alike agree on being atoms and on the base relations?

Counting Types

Throughout, RR is a vocabulary of binary relation symbols and II a finite set of variable names. A binary relational structure SS over RR with universe AA is a set AA together with a binary relation rSr^S on AA for every symbol r∈Rr \in R, the base relations of SS; the universes here are finite and nonempty, and their elements are the atoms.✦ The formulas of the counting logic CIC^I over RR, with variables from II, are generated by the following clauses, in which θ\theta and χ\chi stand for formulas: θ::=⊥∣x=y∣r(x,y)∣¬θ∣θ∧χ∣∃xθ∣∃=nxθ(x,y∈I,r∈R,n∈ℕ).\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 \qquad (x, y \in I,\ r \in R,\ n \in \mathbb{N}).(1)✦

The free variables free⁡(θ)\operatorname{free}(\theta) of θ\theta are the names occurring in it outside the scope of a quantifier that binds them.✦ Satisfaction S⊨θ[v]S \models \theta[v] under an assignment v:I→Av \colon I \to A is given by the usual recursion, in which ∃=nxθ\exists^{=n} x\, \theta holds when exactly nn elements a∈Aa \in A satisfy θ\theta under vv updated to send xx to aa.✦ The type of vv in SS relative to a finite set N⊆IN \subseteq I of names is tp⁡S(v∣N)={θ∈CI:free⁡(θ)⊆N and S⊨θ[v]}.\operatorname{tp}_S(v \mid N) = \{\theta \in C^I : \operatorname{free}(\theta) \subseteq N \text{ and } S \models \theta[v]\}.(2)✦

For a finite index set KK, a tuple α∈AK\alpha \in A^K and an injection e:K→Ie \colon K \to I, the type tp⁡Se(α)\operatorname{tp}^e_S(\alpha) of α\alpha is tp⁡S(v∣e(K))\operatorname{tp}_S(v \mid e(K)), where vv gives each name e(k)e(k) the value αk\alpha_k and every other name a fixed element of AA.✦ When ee is an injection of two disjoint copies J⊔JJ \sqcup J of a finite set JJ into II and α,β∈AJ\alpha, \beta \in A^J, tp⁡Se(α,β)\operatorname{tp}^e_S(\alpha, \beta) is the type of the tuple that is α\alpha on the first copy and β\beta on the second.

Forms and Their Values

The hereditarily finite sets over AA form the set HF(A)\mathrm{HF}(A): every atom a∈Aa \in A is an element of HF(A)\mathrm{HF}(A), an urelement with no elements, and every finite set of elements of HF(A)\mathrm{HF}(A) is again one.✦ Each element of HF(A)\mathrm{HF}(A) is either an atom or a set.✦

A form over JJ with labels in a set LL is either a leaf carrying an index j∈Jj \in J or a set node with nn branches, numbered i<ni < n, of which branch ii carries a form φi\varphi_i over JJ with labels in LL and a label τi∈L\tau_i \in L.✦ The forms here are labelled by sets of formulas of CIC^I.

The value φ*Sα∈HF(A)\varphi *_S \alpha \in \mathrm{HF}(A) of a form φ\varphi over JJ labelled by sets of formulas of CIC^I at a tuple α∈AJ\alpha \in A^J, taken with an injection ee of J⊔JJ \sqcup J into II, is defined by recursion on φ\varphi: a leaf with index jj has value the atom αj\alpha_j, and a set node has value φ*Sα={φi*Sβ:i<n,β∈AJ,tp⁡Se(β,α)=τi}.\varphi *_S \alpha = \{\varphi_i *_S \beta : i < n,\ \beta \in A^J,\ \operatorname{tp}^e_S(\beta, \alpha) = \tau_i\}.(3)✦

Supported Sets and Tuples Represented Alike

Let a group GG act on AA, and through the atoms on HF(A)\mathrm{HF}(A). A tuple of atoms supports an element xx of HF(A)\mathrm{HF}(A) when every g∈Gg \in G fixing each entry of the tuple fixes xx.✦ An element xx of HF(A)\mathrm{HF}(A) is ss-supported, for a natural number ss, when some tuple of ss atoms supports it✦, and hereditarily ss-supported when xx, its elements, their elements and so on are all ss-supported.✦ The set DsG(A)D^G_s(A) consists of the hereditarily ss-supported elements of HF(A)\mathrm{HF}(A).✦

The HF structure SHFS^{\mathrm{HF}} of SS is the structure with universe DsG(A)D^G_s(A) over the vocabulary of a membership symbol ∈\in, an atom symbol At\mathrm{At} and a copy of each r∈Rr \in R, in which x∈yx \in y holds when xx is an element of yy, At(x)\mathrm{At}(x) when xx is an atom, and r(x,y)r(x, y) when xx and yy are atoms aa and bb with rS(a,b)r^S(a, b).✦

Let TT be a second structure over RR, with finite nonempty universe BB on which a group HH acts. Fix a finite index set VV, an injection ff of V×{0,…,s−1}V \times \{0, \dots, s-1\} into II and an injection ee of two disjoint copies of {0,…,s−1}\{0, \dots, s-1\} into II, with which values of forms over {0,…,s−1}\{0, \dots, s-1\} are taken. Tuples v=(vi)i∈Vv = (v_i)_{i \in V} of elements of DsG(A)D^G_s(A) and w=(wi)i∈Vw = (w_i)_{i \in V} of elements of DsH(B)D^H_s(B) are represented alike when there are forms φi\varphi_i, for i∈Vi \in V, over {0,…,s−1}\{0, \dots, s-1\} labelled by sets of formulas of CIC^I, and families γ=(γij)\gamma = (\gamma_{ij}) of atoms of AA and δ=(δij)\delta = (\delta_{ij}) of atoms of BB, indexed by i∈Vi \in V and j<sj < s, such that vi=φi*Sγi and wi=φi*Tδi for every i∈V,tp⁡Sf(γ)=tp⁡Tf(δ),v_i = \varphi_i *_S \gamma_i \text{ and } w_i = \varphi_i *_T \delta_i \text{ for every } i \in V, \qquad \operatorname{tp}^f_S(\gamma) = \operatorname{tp}^f_T(\delta),(4)✦ where γi=(γij)j<s\gamma_i = (\gamma_{ij})_{j < s} and δi=(δij)j<s\delta_i = (\delta_{ij})_{j < s}.

The Claim

Theorem 1. Let SS and TT be binary relational structures over RR with finite nonempty universes AA and BB, let JJ be a finite set and ee an injection of J⊔JJ \sqcup J into II, and let φ\varphi and ψ\psi be forms over JJ labelled by sets of formulas of CIC^I. If tuples α,β∈AJ\alpha, \beta \in A^J and α′,β′∈BJ\alpha', \beta' \in B^J satisfy tp⁡Se(α,β)=tp⁡Te(α′,β′)\operatorname{tp}^e_S(\alpha, \beta) = \operatorname{tp}^e_T(\alpha', \beta'), then φ*Sα=ψ*Sβ⇔φ*Tα′=ψ*Tβ′,\varphi *_S \alpha = \psi *_S \beta \iff \varphi *_T \alpha' = \psi *_T \beta',(5)✦ φ*Sα∈ψ*Sβ⇔φ*Tα′∈ψ*Tβ′.\varphi *_S \alpha \in \psi *_S \beta \iff \varphi *_T \alpha' \in \psi *_T \beta'.(6)✦ Let moreover groups GG and HH act on AA and BB, let ss be a natural number and VV a finite index set, and let tuples vv of elements of DsG(A)D^G_s(A) and ww of elements of DsH(B)D^H_s(B), indexed by VV, be represented alike as in (4), for injections of V×{0,…,s−1}V \times \{0, \dots, s-1\} and of two disjoint copies of {0,…,s−1}\{0, \dots, s-1\} into II. Then for all i,k∈Vi, k \in V and r∈Rr \in R, vi is an atom⇔wi is an atom,v_i \text{ is an atom} \iff w_i \text{ is an atom},(7)✦ SHF⊨r(vi,vk)⇔THF⊨r(wi,wk).S^{\mathrm{HF}} \models r(v_i, v_k) \iff T^{\mathrm{HF}} \models r(w_i, w_k).(8)✦

In the paper, the result reads: for forms φ\varphi and ψ\psi, if (α,β)(\alpha, \beta) and (α′,β′)(\alpha', \beta') have the same CMC^M type, with MM the paper’s number of variables and SS and TT the same or different base structures, then φ*Sα=ψ*Sβ\varphi *_S \alpha = \psi *_S \beta if and only if φ*Tα′=ψ*Tβ′\varphi *_T \alpha' = \psi *_T \beta', and φ*Sα∈ψ*Sβ\varphi *_S \alpha \in \psi *_S \beta if and only if φ*Tα′∈ψ*Tβ′\varphi *_T \alpha' \in \psi *_T \beta'; the atom predicate and all base relations also agree on corresponding form values.

What Is Checked

The claim is stated over the types in CIC^I of tuples from binary relational structures and the values of forms labelled by sets of such formulas, and, for atoms and base relations, over the HF structure on hereditarily ss-supported sets and tuples represented alike.