OctoInformBeta

OpenAI preprint, September 2026 ยท ยง5. From atom types to hereditarily finite sets

Lemma 15: In two finite structures, while the extended tuple fits into the MM variables, through a type-preserving bijection; equal types pass to subtuples

Equal CMC^M types have equally many extensions of each type.

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 aโ€พ\bar a be a tuple in a finite structure ๐”„\mathfrak A and bโ€พ\bar b a tuple of the same length in a finite structure ๐”…\mathfrak B, and suppose the two have the same type in the counting logic CMC^M with MM variables. Extend each by further entries indexed by a finite set DD, so that the longer tuples have at most MM entries. Does every type of the longer tuples occur as often among the extensions of aโ€พ\bar a as among those of bโ€พ\bar b?

Two companion questions come with it: whether equal types stay equal on subtuples, taken in any order, and whether a single formula defines a given type in both structures at once.

Counting Logic and Types

A ฯƒ\sigma-structure ๐”„\mathfrak A, for a vocabulary ฯƒ\sigma of binary relation symbols, is a set AA, its universe, with a binary relation r๐”„โІAร—Ar^{\mathfrak A}\subseteq A\times A for each symbol rโˆˆฯƒr\in\sigma.โœฆ

Fix a finite set II of MM variable names. The formulas of the counting logic CMC^M over ฯƒ\sigma are falsity, equations and relational atoms between names, and the formulas built from them by negation, conjunction, existential quantification and exact counting quantification: ฯ†::=โŠฅโˆฃx=yโˆฃr(x,y)โˆฃยฌฯ†โˆฃฯ†โˆงฯˆโˆฃโˆƒxฯ†โˆฃโˆƒ=nxฯ†,x,yโˆˆI,rโˆˆฯƒ,nโˆˆโ„•.\varphi \;::=\; \bot \mid x = y \mid r(x,y) \mid \neg\varphi \mid \varphi\wedge\psi \mid \exists x\,\varphi \mid \exists^{=n}x\,\varphi, \qquad x,y\in I,\ r\in\sigma,\ n\in\mathbb N.(1)โœฆ The free variables free⁡(ฯ†)โІI\operatorname{free}(\varphi)\subseteq I of a formula ฯ†\varphi are the names occurring in it outside the scope of a quantifier that binds them; both โˆƒx\exists x and โˆƒ=nx\exists^{=n}x bind xx.โœฆ

An assignment into ๐”„\mathfrak A is a map v:Iโ†’Av\colon I\to A, and v[xโ†ฆa]v[x\mapsto a] agrees with vv except that it sends xx to aa. Satisfaction ๐”„,vโŠจฯ†\mathfrak A,v\models\varphi is defined by the usual recursion: โŠฅ\bot never holds, x=yx=y and r(x,y)r(x,y) are read at the values v(x)v(x) and v(y)v(y), negation and conjunction are classical, and โˆƒxฯ†\exists x\,\varphi holds when ๐”„,v[xโ†ฆa]โŠจฯ†\mathfrak A,v[x\mapsto a]\models\varphi for some aโˆˆAa\in A; the counting quantifier asks for exactly nn such aa: ๐”„,vโŠจโˆƒ=nxฯ†โ‡”|{aโˆˆA:๐”„,v[xโ†ฆa]โŠจฯ†}|=n.\mathfrak A,v\models\exists^{=n}x\,\varphi \iff \bigl|\{a\in A : \mathfrak A,v[x\mapsto a]\models\varphi\}\bigr| = n.(2)โœฆ

The type of an assignment vv into ๐”„\mathfrak A on a set NโІIN\subseteq I of names is the set of formulas of CMC^M with free variables in NN that hold in ๐”„\mathfrak A under vv: tp⁡๐”„N(v)={ฯ†โˆˆCM:free⁡(ฯ†)โІN,๐”„,vโŠจฯ†}.\operatorname{tp}^N_{\mathfrak A}(v) = \{\varphi\in C^M : \operatorname{free}(\varphi)\subseteq N,\ \mathfrak A,v\models\varphi\}.(3)โœฆ

A tuple aโ€พโˆˆAJ\bar a\in A^J, indexed by a finite set JJ, is placed at the names by an injection e:Jโ†’Ie\colon J\to I; its names are the image e(J)e(J).โœฆ When AA is nonempty, the assignment ve,aโ€พv_{e,\bar a} of aโ€พ\bar a sends e(j)e(j) to aja_j for each jโˆˆJj\in J and every other name to a fixed default element of AAโœฆ, and the type of aโ€พ\bar a at ee is the type of this assignment on the names of aโ€พ\bar a: tp⁡๐”„e(aโ€พ)=tp⁡๐”„e(J)(ve,aโ€พ).\operatorname{tp}^e_{\mathfrak A}(\bar a) = \operatorname{tp}^{e(J)}_{\mathfrak A}(v_{e,\bar a}).(4)โœฆ

For a finite set DD and cโ€พโˆˆAD\bar c\in A^D, the extension aโ€พcโ€พโˆˆAJโŠ”D\bar a\bar c\in A^{J\sqcup D} agrees with aโ€พ\bar a on JJ and with cโ€พ\bar c on DD. For an injection u:Jโ€ฒโ†’Ju\colon J'\to J, the subtuple aโ€พโˆ˜u=(au(j))jโˆˆJโ€ฒ\bar a\circ u=(a_{u(j)})_{j\in J'} lists the entries of aโ€พ\bar a at u(Jโ€ฒ)u(J') in the order of Jโ€ฒJ'.

The Claim

Theorem 1. Let ๐”„\mathfrak A and ๐”…\mathfrak B be ฯƒ\sigma-structures with nonempty universes AA and BB, and in parts (a) to (c) let them be finite.

  1. Let JJ and DD be finite sets, let e:Jโ†’Ie\colon J\to I and E:JโŠ”Dโ†’IE\colon J\sqcup D\to I be injections, and let aโ€พโˆˆAJ\bar a\in A^J and bโ€พโˆˆBJ\bar b\in B^J have the same type, tp⁡๐”„e(aโ€พ)=tp⁡๐”…e(bโ€พ)\operatorname{tp}^e_{\mathfrak A}(\bar a)=\operatorname{tp}^e_{\mathfrak B}(\bar b). Then for every set ฯ\rho of formulas of CMC^M |{cโ€พโˆˆAD:tp⁡๐”„E(aโ€พcโ€พ)=ฯ}|=|{dโ€พโˆˆBD:tp⁡๐”…E(bโ€พdโ€พ)=ฯ}|,\bigl|\{\bar c\in A^D : \operatorname{tp}^E_{\mathfrak A}(\bar a\bar c)=\rho\}\bigr| = \bigl|\{\bar d\in B^D : \operatorname{tp}^E_{\mathfrak B}(\bar b\bar d)=\rho\}\bigr|,(5)โœฆ and there is a bijection f:ADโ†’BDf\colon A^D\to B^D with tp⁡๐”„E(aโ€พcโ€พ)=tp⁡๐”…E(bโ€พf(cโ€พ))for every cโ€พโˆˆAD.\operatorname{tp}^E_{\mathfrak A}(\bar a\bar c) = \operatorname{tp}^E_{\mathfrak B}(\bar b\,f(\bar c)) \quad\text{for every } \bar c\in A^D.(6)โœฆ

  2. Let NโІIN\subseteq I and iโˆˆI\Ni\in I\setminus N, put Nโ€ฒ=Nโˆช{i}N'=N\cup\{i\}, and let v:Iโ†’Av\colon I\to A and w:Iโ†’Bw\colon I\to B be assignments with tp⁡๐”„N(v)=tp⁡๐”…N(w)\operatorname{tp}^N_{\mathfrak A}(v)=\operatorname{tp}^N_{\mathfrak B}(w). Then for every type ฯ=tp⁡๐”„Nโ€ฒ(v0)\rho=\operatorname{tp}^{N'}_{\mathfrak A}(v_0) of an assignment v0:Iโ†’Av_0\colon I\to A |{aโˆˆA:tp⁡๐”„Nโ€ฒ(v[iโ†ฆa])=ฯ}|=|{bโˆˆB:tp⁡๐”…Nโ€ฒ(w[iโ†ฆb])=ฯ}|.\bigl|\{a\in A : \operatorname{tp}^{N'}_{\mathfrak A}(v[i\mapsto a])=\rho\}\bigr| = \bigl|\{b\in B : \operatorname{tp}^{N'}_{\mathfrak B}(w[i\mapsto b])=\rho\}\bigr|.(7)โœฆ

  3. For every NโІIN\subseteq I and every assignment v0:Iโ†’Av_0\colon I\to A there is a formula ฮธ\theta of CMC^M with free⁡(ฮธ)โІN\operatorname{free}(\theta)\subseteq N such that for all assignments v:Iโ†’Av\colon I\to A and w:Iโ†’Bw\colon I\to B ๐”„,vโŠจฮธโ‡”tp⁡๐”„N(v)=tp⁡๐”„N(v0),๐”…,wโŠจฮธโ‡”tp⁡๐”…N(w)=tp⁡๐”„N(v0).\begin{aligned} \mathfrak A,v\models\theta &\iff \operatorname{tp}^N_{\mathfrak A}(v)=\operatorname{tp}^N_{\mathfrak A}(v_0),\\ \mathfrak B,w\models\theta &\iff \operatorname{tp}^N_{\mathfrak B}(w)=\operatorname{tp}^N_{\mathfrak A}(v_0). \end{aligned}(8)โœฆ

  4. Let JJ and Jโ€ฒJ' be finite sets, let e:Jโ†’Ie\colon J\to I, eโ€ฒ:Jโ€ฒโ†’Ie'\colon J'\to I and u:Jโ€ฒโ†’Ju\colon J'\to J be injections, and let aโ€พโˆˆAJ\bar a\in A^J and bโ€พโˆˆBJ\bar b\in B^J satisfy tp⁡๐”„e(aโ€พ)=tp⁡๐”…e(bโ€พ)\operatorname{tp}^e_{\mathfrak A}(\bar a)=\operatorname{tp}^e_{\mathfrak B}(\bar b). Then tp⁡๐”„eโ€ฒ(aโ€พโˆ˜u)=tp⁡๐”…eโ€ฒ(bโ€พโˆ˜u).\operatorname{tp}^{e'}_{\mathfrak A}(\bar a\circ u) = \operatorname{tp}^{e'}_{\mathfrak B}(\bar b\circ u).(9)โœฆ

In the paper, the result reads: if tuples aโ€พ\bar a and bโ€พ\bar b have the same CMC^M type in two structures chosen from the grid structures ๐‘จb0\mathbf A_{b^0} and ๐‘จb1\mathbf A_{b^1} of the two charges b0b^0 and b1b^1, and |J|+|D|โ‰คM|J|+|D|\le M, then for every realized type ฯ\rho of length |J|+|D||J|+|D| the number of tuples cโ€พ\bar c indexed by DD with aโ€พcโ€พ\bar a\bar c of type ฯ\rho equals the number of tuples dโ€พ\bar d indexed by DD with bโ€พdโ€พ\bar b\bar d of type ฯ\rho, and tuples of equal type have equal types on every projected or reordered subtuple.

In (5) and (6) the bound |J|+|D|โ‰คM|J|+|D|\le M is the injection EE of JโŠ”DJ\sqcup D into the MM names.

What Is Checked

The claim is stated over ฯƒ\sigma-structures and the formulas (1) of CMC^M with their free variables and satisfaction (2), through the types of assignments (3) and of tuples (4).