OctoInformBeta

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

Lemma 18: Between hereditarily ss-supported objects over two homogeneous structures, pairing objects that one set-builder form gives at tuples of the same type

A bijection that keeps assignments represented alike.

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 of binary relations, on finite sets of atoms AA and BB acted on by groups GG and HH. Fix a number ss. Hereditarily finite objects over the atoms are described by set-builder forms over an ss-tuple of atoms, each level collecting the objects described at all ss-tuples of a prescribed counting type over the current one. The question is whether, when tuples of the same type are conjugate under the group, the objects over AA and over BB hereditarily supported by ss atoms can be matched one to one, each matched pair described by one form at tuples of the same type. The matching is also wanted to respect assignments whose entries are already given by forms at tuples of the same type, so that adjoining a matched pair to them keeps them so.

Counting Types

A binary relational structure SS over a vocabulary RR with universe AA interprets every symbol of RR as a binary relation on AA.✦ The formulas of CIC^I over RR are those of first-order logic with equality, ∃\exists and the exact counting quantifiers ∃=n\exists^{=n}, built from ⊥\bot, equations x=yx = y and atoms r(x,y)r(x,y) for r∈Rr \in R, with variable names from a finite set II.✦ Satisfaction S⊨φ[v]S \models \varphi[v] under an assignment v:I→Av : I \to A is defined by recursion on φ\varphi, with ∃=nxφ\exists^{=n} x\, \varphi true when exactly nn values of xx satisfy φ\varphi✦, and free⁡(φ)\operatorname{free}(\varphi) is the set of variables of φ\varphi not bound by a quantifier.✦

The type of an assignment v:I→Av : I \to A relative to a finite set N⊆IN \subseteq I of names is the set of formulas of CIC^I whose free variables lie in NN and which SS satisfies under vv: tp⁡NS(v)={φ∈CI:free⁡(φ)⊆N,S⊨φ[v]}.\operatorname{tp}^S_N(v) = \{\varphi \in C^I : \operatorname{free}(\varphi) \subseteq N,\ S \models \varphi[v]\}.(1)✦ For an injection e:J→Ie : J \to I and a tuple a∈AJa \in A^J, with AA nonempty, the type tp⁡eS(a)\operatorname{tp}^S_e(a) of aa is the type (1), relative to the names e(J)e(J), of the assignment from aa, which gives each name e(j)e(j) the value aja_j and every other name one fixed atom.✦

Write [s]={0,…,s−1}[s] = \{0, \dots, s-1\}, and let PP be a finite set of parameter indices and VV a set of positions. Injections of PP, P⊔[s]P \sqcup [s], [s]⊔[s][s] \sqcup [s] and V×[s]V \times [s] into II are fixed; the type of a tuple indexed by one of these sets is taken with its injection and written tp⁡S\operatorname{tp}^S, and tp⁡S(p,a)\operatorname{tp}^S(p,a) is the type of the tuple that is pp on the first summand and aa on the second.

A structure SS on AA, with a group GG acting on AA, is homogeneous for tuples indexed by JJ when any two tuples of AJA^J with the same type are conjugate under GG: tp⁡S(a)=tp⁡S(b)⟹b=ga for some g∈G(a,b∈AJ).\operatorname{tp}^S(a) = \operatorname{tp}^S(b) \implies b = g a \text{ for some } g \in G \qquad (a, b \in A^J).(2)

Supported Objects and Forms

The group GG acts on HF(A)\mathrm{HF}(A), the hereditarily finite objects over the atoms AA. The pointwise stabilizer G(α)G_{(\alpha)} of a tuple α\alpha of atoms is the subgroup of the elements of GG that fix every entry of α\alpha. A tuple α\alpha of atoms supports an object xx of HF(A)\mathrm{HF}(A) when G(α)G_{(\alpha)} fixes xx.✦ An object xx of HF(A)\mathrm{HF}(A) is ss-supported when some tuple of ss atoms supports it✦, and hereditarily ss-supported when xx, its elements, their elements and so on down the membership relation are all ss-supported.✦ The domain D0D_0 of supported objects over AA is the set of hereditarily ss-supported objects of HF(A)\mathrm{HF}(A), and D1⊆HF(B)D_1 \subseteq \mathrm{HF}(B) is defined from the action of HH on BB in the same way.✦

A form over an index set JJ with labels in a set LL is a finite tree with two kinds of node: a leaf carrying an index j∈Jj \in J, and a set node with branches i<ni < n, each carrying a child form ψi\psi_i and a label λi∈L\lambda_i \in L.✦ Here J=[s]J = [s] and the labels are sets of formulas of CIC^I. The value φS(a)∈HF(A)\varphi^S(a) \in \mathrm{HF}(A) of a form φ\varphi at a tuple a∈A[s]a \in A^{[s]} is the atom aja_j when φ\varphi is a leaf carrying jj, and when φ\varphi is a set node it is φS(a)={ψiS(b):i<n,b∈A[s],tp⁡S(b,a)=λi},\varphi^S(a) = \{\psi_i^S(b) : i < n,\ b \in A^{[s]},\ \operatorname{tp}^S(b,a) = \lambda_i\},(3)✦ with bb on the first copy of [s][s] and aa on the second.

For p∈APp \in A^P and a set τ\tau of formulas, the molecules of τ\tau over pp in SS are the tuples a∈A[s]a \in A^{[s]} with tp⁡S(p,a)=τ\operatorname{tp}^S(p,a) = \tau.✦ The label values Val⁡pS(τ,φ)\operatorname{Val}^S_p(\tau,\varphi) of a form φ\varphi at τ\tau over pp form the set of its values (3) at these molecules: Val⁡pS(τ,φ)={φS(a):a∈A[s],tp⁡S(p,a)=τ}.\operatorname{Val}^S_p(\tau,\varphi) = \{\varphi^S(a) : a \in A^{[s]},\ \operatorname{tp}^S(p,a) = \tau\}.(4)✦

Two assignments v:V→D0v : V \to D_0 and w:V→D1w : V \to D_1 are represented alike when there are forms φi\varphi_i for i∈Vi \in V and tuples a∈AV×[s]a \in A^{V \times [s]} and b∈BV×[s]b \in B^{V \times [s]}, with rows ai=(ai,0,…,ai,s−1)a_i = (a_{i,0}, \dots, a_{i,s-1}) and bib_i likewise, such that φiS(ai)=vi,φiT(bi)=wi(i∈V),tp⁡S(a)=tp⁡T(b).\varphi_i^S(a_i) = v_i, \quad \varphi_i^T(b_i) = w_i \quad (i \in V), \qquad \operatorname{tp}^S(a) = \operatorname{tp}^T(b).(5)✦

The Claim

Theorem 1. Let SS and TT be binary relational structures over RR on finite nonempty sets of atoms AA and BB, with groups GG acting on AA and HH acting on BB, and let D0D_0 and D1D_1 be their domains of hereditarily ss-supported objects.

(a) Suppose GG acts by automorphisms of SS and SS is homogeneous for tuples indexed by P⊔[s]P \sqcup [s]. Then for any p∈APp \in A^P, set τ\tau of formulas, form φ\varphi and label values x,y∈Val⁡pS(τ,φ)x, y \in \operatorname{Val}^S_p(\tau,\varphi), y∈G(p)x.y \in G_{(p)}\, x.(6)✦

(b) Suppose in addition that HH acts by automorphisms of TT and TT is homogeneous for tuples indexed by P⊔[s]P \sqcup [s]. If p∈APp \in A^P, q∈BPq \in B^P and the set τ\tau of formulas has a molecule over pp in SS and a molecule over qq in TT, then for every form φ\varphi |Val⁡pS(τ,φ)|=|Val⁡qT(τ,φ)|.|\operatorname{Val}^S_p(\tau,\varphi)| = |\operatorname{Val}^T_q(\tau,\varphi)|.(7)✦

(c) Let s≥1s \ge 1, suppose SS and TT are homogeneous for tuples indexed by [s]⊔[s][s] \sqcup [s] and by P⊔[s]P \sqcup [s], and let p∈APp \in A^P and q∈BPq \in B^P have the same type. Then there is a bijection f:D0→D1f : D_0 \to D_1 such that every x∈D0x \in D_0 has a form φ\varphi and tuples a∈A[s]a \in A^{[s]} and b∈B[s]b \in B^{[s]} with x=φS(a),f(x)=φT(b),tp⁡S(p,a)=tp⁡T(q,b).x = \varphi^S(a), \qquad f(x) = \varphi^T(b), \qquad \operatorname{tp}^S(p,a) = \operatorname{tp}^T(q,b).(8)✦

(d) Let s≥1s \ge 1, suppose SS and TT are homogeneous for tuples indexed by [s]⊔[s][s] \sqcup [s] and by V×[s]V \times [s], let v:V→D0v : V \to D_0 and w:V→D1w : V \to D_1 be represented alike, let i∈Vi \in V, and for x∈D0x \in D_0 write v[i↦x]v[i \mapsto x] for vv with its entry at ii replaced by xx. Then there is a bijection f:D0→D1f : D_0 \to D_1 such that for every x∈D0x \in D_0 v[i↦x] and w[i↦f(x)] are represented alike.v[i \mapsto x] \text{ and } w[i \mapsto f(x)] \text{ are represented alike}.(9)✦

In the paper, the result reads: for represented-alike assignments under the paper’s bound r≤m−1r \le m - 1, in which rr and mm are the paper’s own parameters, there is a bijection f:D0→D1f : D_0 \to D_1 such that adjoining any pair x,f(x)x, f(x) gives represented-alike assignments, and in particular f(xj)=xj′f(x_j) = x'_j for the entries xjx_j and xj′x'_j of the two assignments at every position jj kept when the pair is adjoined.

What Is Checked

The library states (6), (7), (8) and (9) over binary relational structures on finite sets of atoms with groups acting on them, the formulas of CIC^I with their satisfaction and the counting types (1) of tuples, the hereditarily ss-supported objects of HF(A)\mathrm{HF}(A) and HF(B)\mathrm{HF}(B), set-builder forms and their values (3), the label values (4) at molecules, and assignments represented alike (5).