OctoInformBeta

OpenAI preprint, September 2026 Β· Β§5. Assembling a self-dual matroid

Lemma 5.1: For a rank model with ideal 𝒦\mathcal K: Upper closed upward, Lower downward, each zone stable modulo 𝒦0\mathcal K_0, admissible sets π’₯0\mathcal J_0-positive

Upper, Lower and admissible zones partition the subsets of E0E_0..

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 DD be the countable set of pairs (m,f)(m,f) in which mm is a natural number and f:{0,1}mβ†’{0,1}f\colon\{0,1\}^m\to\{0,1\} is a Boolean function✦, and let E0=LβŠ”RE_0=L\sqcup R be two copies of DD, a left copy LL and a right copy RR.✦ The left slice XLX_L of a subset XX of E0E_0 is the set of points of DD whose copy in LL lies in XX, and its right slice XRX_R is the set of those whose copy in RR lies in XX.✦

In the assembling of a self-dual matroid, an ultrafilter on DD and an ordinal rank on the subsets of DD sort the subsets XX of E0E_0 into three zones, Upper, Lower and admissible, according to whether XLX_L and D\XRD\setminus X_R belong to the ultrafilter and how their ranks compare. The question is how the three zones divide the subsets of E0E_0: whether every subset falls in exactly one, and which changes to a set keep it in its zone.

Ideals and Densities

An ideal ℐ\mathcal I on a set Ξ±\alpha is a family of subsets of Ξ±\alpha that contains the empty set, every subset of each of its members and the union of any two of its members, and does not contain Ξ±\alpha.✦ For subsets XX and YY of Ξ±\alpha, XX is contained in YY modulo ℐ\mathcal I, written XβŠ†β„YX\subseteq_{\mathcal I}Y, when X\Yβˆˆβ„X\setminus Y\in\mathcal I; a subset of Ξ±\alpha outside ℐ\mathcal I is ℐ\mathcal I-positive.✦

The density of a set XX in a finite set ss is the proportion |X∩s|/|s||X\cap s|/|s| of the elements of ss that lie in XX.✦ For each natural number mm, the block Dm={m}Γ—{0,1}{0,1}mD_m=\{m\}\times\{0,1\}^{\{0,1\}^m} of DD has wm=22mw_m=2^{2^m} elements✦, and the doubled block Wm=DmΓ—{L,R}W_m=D_m\times\{L,R\} is its two copies in E0E_0.✦ The ideal π’₯\mathcal J on DD consists of the subsets of DD whose density in DmD_m tends to 00 as mβ†’βˆžm\to\infty✦, and the ideal π’₯0\mathcal J_0 on E0E_0 consists of the subsets of E0E_0 whose density in WmW_m tends to 00.✦

Columns and the Larger Ideals

The indices tt, ΞΎ\xi and Ξ³\gamma run over the ordinals below 𝔠\mathfrak c, the continuum taken as its initial ordinal✦, and Ξ²\beta is a bijection, fixed once and for all, from these ordinals onto the set {0,1}β„•\{0,1\}^{\mathbb N} of infinite binary sequences.✦ A column tag is a pair (ΞΎ,i)(\xi,i) of an index ΞΎ\xi and a label i∈{0,1,2}i\in\{0,1,2\}.✦ The binary string hΟ„h_\tau of a column tag Ο„=(ΞΎ,i)\tau=(\xi,i) is the sequence in {0,1}β„•\{0,1\}^{\mathbb N} whose bit nn is 11 exactly when n=in=i, for n<2n<2, and is bit nβˆ’2n-2 of Ξ²(ΞΎ)\beta(\xi), for nβ‰₯2n\ge 2.✦

The column CΟ„C_\tau of a column tag Ο„\tau is the subset of DD CΟ„={(m,f)∈D:f(hΟ„(0),…,hΟ„(mβˆ’1))=1}.C_\tau=\{(m,f)\in D : f\bigl(h_\tau(0),\dots,h_\tau(m-1)\bigr)=1\}.(1)✦ For an index tt, the column AtA_t is C(t,0)C_{(t,0)}✦; for a finite set FF of indices, AF=β‹‚t∈FAtA_F=\bigcap_{t\in F}A_t, which is DD when FF is empty.✦

A subset XX of DD is 𝒦\mathcal K-small when X∩AF∈π’₯for some finite set F of indices,X\cap A_F\in\mathcal J\quad\text{for some finite set $F$ of indices},(2)✦ and 𝒦\mathcal K is the family of 𝒦\mathcal K-small subsets of DD.✦ The family 𝒦0\mathcal K_0 consists of the subsets XX of E0E_0 whose slices XLX_L and XRX_R both lie in 𝒦\mathcal K.✦

Rank Models and the Three Zones

A rank model on a set Ξ±\alpha consists of an ideal ℐ\mathcal I on Ξ±\alpha, an ultrafilter 𝒰\mathcal U on Ξ±\alpha whose members, the large sets, all lie outside ℐ\mathcal I, and a rank ρ\rho that assigns to each subset of Ξ±\alpha an ordinal below 𝔠\mathfrak c, such that ρ\rho is antitone modulo ℐ\mathcal I on large sets, X,Yβˆˆπ’° and XβŠ†β„Y⟹ρ(Y)≀ρ(X),X,Y\in\mathcal U \text{ and } X\subseteq_{\mathcal I}Y \implies \rho(Y)\le\rho(X),(3)✦ and admits rank-raising thinning: whenever XX is large and a subset ss of XX is not, there is for each Ξ³<𝔠\gamma<\mathfrak c a large uu with sβŠ†uβŠ†Xs\subseteq u\subseteq X and ρ(u)>Ξ³\rho(u)>\gamma.

Fix a rank model on DD with ultrafilter 𝒰\mathcal U and rank ρ\rho. A subset XX of E0E_0 is Upper for the model when XLβˆˆπ’°andρ(XL)≀ρ(D\XR) if D\XRβˆˆπ’°,X_L\in\mathcal U \quad\text{and}\quad \rho(X_L)\le\rho(D\setminus X_R)\ \text{ if }\ D\setminus X_R\in\mathcal U,(4)✦ and Lower for the model when its complement E0\XE_0\setminus X is Upper.✦ A subset XX of E0E_0 is admissible for the model when XLβˆˆπ’°,D\XRβˆˆπ’° and ρ(D\XR)<ρ(XL), orXLβˆ‰π’°,D\XRβˆ‰π’° and ρ(XR)<ρ(D\XL).\begin{aligned} &X_L\in\mathcal U,\ D\setminus X_R\in\mathcal U \text{ and } \rho(D\setminus X_R)<\rho(X_L), \text{ or}\\ &X_L\notin\mathcal U,\ D\setminus X_R\notin\mathcal U \text{ and } \rho(X_R)<\rho(D\setminus X_L). \end{aligned}(5)✦

The Claim

Theorem 1. Let a rank model on DD have ideal 𝒦\mathcal K, and let XX and YY be subsets of E0E_0. Then X is admissible⇔X is neither Upper nor Lower,X \text{ is admissible} \iff X \text{ is neither Upper nor Lower},(6)✦ and if XX is Upper, then X is not Lower.X \text{ is not Lower}.(7)✦ If XX is Upper and XβŠ†YX\subseteq Y, then Y is Upper,Y \text{ is Upper},(8)✦ and if YY is Lower and XβŠ†YX\subseteq Y, then X is Lower.X \text{ is Lower}.(9)✦ If Xβ–³Yβˆˆπ’¦0X\mathbin{\triangle}Y\in\mathcal K_0, then X is Upper⇔Y is Upper,X is Lower⇔Y is Lower,X is admissible⇔Y is admissible.\begin{aligned} X \text{ is Upper} &\iff Y \text{ is Upper},\\ X \text{ is Lower} &\iff Y \text{ is Lower},\\ X \text{ is admissible} &\iff Y \text{ is admissible}. \end{aligned}(10)✦ If XX is admissible, then E0\X is admissible.E_0\setminus X \text{ is admissible}.(11)✦ Moreover βˆ… is Lower\emptyset \text{ is Lower}(12)✦ and E0 is Upper.E_0 \text{ is Upper}.(13)✦ Finally, if XX is admissible, then Xβˆ‰π’₯0.X\notin\mathcal J_0.(14)✦

In the paper, the result reads: the Upper zone, the Lower zone and the admissible sets partition 2E02^{E_0}; the Upper zone is upward closed and the Lower zone downward closed; all three are invariant under symmetric differences in 𝒦0\mathcal K_0; complementation exchanges the Upper and Lower zones and preserves admissibility; βˆ…\emptyset is Lower and E0E_0 is Upper; and every admissible set and its complement are π’₯0\mathcal J_0-positive.

The partition stands in the box as (6) and (7), and the exchange of Upper and Lower under complements is the definition of a Lower set.

What Is Checked

The claim is stated over a rank model on DD whose ideal is 𝒦\mathcal K, the Upper, Lower and admissible subsets of E0E_0 that its ultrafilter and rank define through the slices, the family 𝒦0\mathcal K_0 of subsets of E0E_0 with both slices in 𝒦\mathcal K, and the ideal π’₯0\mathcal J_0 of subsets of E0E_0 whose density in WmW_m tends to 00.

On these constructions the library proves that 𝒦\mathcal K is a proper ideal on DD✦: it contains the empty set, every subset of a 𝒦\mathcal K-small set✦ and the union of two 𝒦\mathcal K-small sets✦, and it does not contain DD.✦