OctoInformBeta

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

Proposition 5.4: For a rank model on DD with ideal 𝒦\mathcal K, and a good set of prototypes whose bases meet every interval of E0E_0

A basis system whose members are all admissible.

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) of a natural number mm and a function f:{0,1}mβ†’{0,1}f \colon \{0,1\}^m \to \{0,1\}✦, and let E0=LβŠ”R=DΓ—{false,true}E_0 = L \sqcup R = D \times \{\mathrm{false}, \mathrm{true}\} be the doubled ground set, with LL the copy of DD at false and RR the copy at true. The bases of a self-dual matroid on E0E_0 are closed under complements. A rank model on DD singles out the admissible subsets of E0E_0, and a basis system is a family of admissible subsets, closed under complements, with further exchange and interval properties. The candidate bases come from local rules attached to a set of prototypes, which is built up by a recursion of length 𝔠\mathfrak c, the continuum as an initial ordinal.

Columns and the Ideal 𝒦\mathcal K

Fix a bijection between the indices below 𝔠\mathfrak c and the binary sequences in {0,1}β„•\{0,1\}^{\mathbb N}.✦ A column tag is a pair (ΞΎ,i)(\xi, i) of an index ΞΎ<𝔠\xi < \mathfrak c and a label i∈{0,1,2}i \in \{0,1,2\}✦; its binary string is the sequence whose first two bits are 1010, 0101 or 0000 according as ii is 00, 11 or 22, and whose bit n+2n + 2 is bit nn of the sequence of ΞΎ\xi.✦ The column of a tag is the subset of DD consisting of the pairs (m,f)(m, f) for which ff takes the value 11 at the prefix of length mm of the tag’s binary string.✦ For t<𝔠t < \mathfrak c, the column AtA_t is the column of the tag (t,0)(t, 0)✦, and for a finite set FF of indices below 𝔠\mathfrak c, the set AF=β‹‚t∈FAtA_F = \bigcap_{t \in F} A_t is the meet of these columns, with Aβˆ…=DA_\emptyset = D.✦

The density of a set XX in a finite set ss is |X∩s|/|s||X \cap s| / |s|.✦ 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 π’₯\mathcal J is the family of subsets of DD whose density in DmD_m tends to 00 as mβ†’βˆžm \to \infty.✦ A subset XX of DD is 𝒦\mathcal K-small when X∩AF∈π’₯for some finite set F of indices below 𝔠,X \cap A_F \in \mathcal J \quad \text{for some finite set } F \text{ of indices below } \mathfrak c,(1)✦ and 𝒦\mathcal K is the family of 𝒦\mathcal K-small subsets of DD.✦

Rank Models and Admissible Sets

An ideal on a set Ξ±\alpha is a family 𝒩\mathcal N of subsets of Ξ±\alpha that contains the empty set, is closed under subsets and under unions of two members, and does not contain Ξ±\alpha.✦ A subset XX of Ξ±\alpha is contained in a subset YY modulo 𝒩\mathcal N, written XβŠ†π’©YX \subseteq_{\mathcal N} Y, when X\Yβˆˆπ’©X \setminus Y \in \mathcal N.✦

A rank model (𝒩,𝒰,ρ)(\mathcal N, \mathcal U, \rho) on Ξ±\alpha consists of an ideal 𝒩\mathcal N on Ξ±\alpha, an ultrafilter 𝒰\mathcal U on Ξ±\alpha containing no member of 𝒩\mathcal N, and a rank ρ\rho that assigns to each subset of Ξ±\alpha an ordinal below 𝔠\mathfrak c, subject to two conditions.✦ The rank is antitone modulo 𝒩\mathcal N on large sets: ρ(Y)≀ρ(X)\rho(Y) \le \rho(X) whenever XX and YY lie in 𝒰\mathcal U and XβŠ†π’©YX \subseteq_{\mathcal N} Y.✦ It admits rank-raising thinning: whenever Xβˆˆπ’°X \in \mathcal U and sβŠ†Xs \subseteq X with sβˆ‰π’°s \notin \mathcal U, for every Ξ³<𝔠\gamma < \mathfrak c there is uβˆˆπ’°u \in \mathcal U with sβŠ†uβŠ†Xs \subseteq u \subseteq X and ρ(u)>Ξ³\rho(u) > \gamma.✦

The left and right slices of a subset XX of E0E_0 are the subsets XL={d∈D:(d,false)∈X}X_L = \{d \in D : (d, \mathrm{false}) \in X\} and XR={d∈D:(d,true)∈X}X_R = \{d \in D : (d, \mathrm{true}) \in X\} of DD.✦ Given a rank model (𝒩,𝒰,ρ)(\mathcal N, \mathcal U, \rho) on DD, a subset XX of E0E_0 is admissible 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), \quad\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}(2)✦

Local Rules

The family π’₯0\mathcal J_0 consists of the subsets of E0E_0 whose density in the doubled block Wm=DmΓ—{L,R}W_m = D_m \times \{L, R\} tends to 00 as mβ†’βˆžm \to \infty.✦ Fix a subset TT of E0E_0, write Vn=W0βˆͺ…βˆͺWnβˆ’1V_n = W_0 \cup \dots \cup W_{n-1}✦ and cn=|Vn|c_n = |V_n|, and for XβŠ†E0X \subseteq E_0 let dm(X)d_m(X) be the density of XX in WmW_m minus that of TT✦, and pn(X)=|X∩Vn|βˆ’|T∩Vn|p_n(X) = |X \cap V_n| - |T \cap V_n|.✦ The probes of XX relative to TT and their lower limit in the extended reals are fn(X)=pn(X)+cn(supmβ‰₯ndm(X)+infmβ‰₯ndm(X)),β„“T(X)=liminfnβ†’βˆžfn(X).f_n(X) = p_n(X) + c_n \Bigl(\sup_{m \ge n} d_m(X) + \inf_{m \ge n} d_m(X)\Bigr), \qquad \ell_T(X) = \liminf_{n \to \infty} f_n(X).(3)

The local lower rule β„¬βˆ’(T)\mathcal B^-(T) and the local upper rule ℬ+(T)\mathcal B^+(T) at TT are the families β„¬βˆ’(T)={XβŠ†E0:Xβ–³T∈π’₯0,βˆ’1<β„“T(X)≀0},ℬ+(T)={XβŠ†E0:E0\Xβˆˆβ„¬βˆ’(E0\T)}.\mathcal B^-(T) = \{X \subseteq E_0 : X \mathbin{\triangle} T \in \mathcal J_0,\ -1 < \ell_T(X) \le 0\}, \qquad \mathcal B^+(T) = \{X \subseteq E_0 : E_0 \setminus X \in \mathcal B^-(E_0 \setminus T)\}.(4) For a rule Οƒ\sigma, a Boolean, ℬσ(T)\mathcal B^\sigma(T) is β„¬βˆ’(T)\mathcal B^-(T) when Οƒ\sigma is false and ℬ+(T)\mathcal B^+(T) when Οƒ\sigma is true.✦

Basis Systems

A basis system on a set Ξ±\alpha is a nonempty family ℬ\mathcal B of subsets of Ξ±\alpha that is an antichain under inclusion, is closed under complements, is closed under single swaps, so that (B\{e})βˆͺ{f}βˆˆβ„¬(B \setminus \{e\}) \cup \{f\} \in \mathcal B whenever Bβˆˆβ„¬B \in \mathcal B, e∈Be \in B and fβˆ‰Bf \notin B, and satisfies the interval alternative:✦ for all IβŠ†YβŠ†Ξ± with Y\I infinite there is Bβˆˆβ„¬ withBβŠ†I,orIβŠ†BβŠ†Y,orYβŠ†B.\begin{aligned} &\text{for all } I \subseteq Y \subseteq \alpha \text{ with } Y \setminus I \text{ infinite there is } B \in \mathcal B \text{ with}\\ &B \subseteq I, \quad\text{or}\quad I \subseteq B \subseteq Y, \quad\text{or}\quad Y \subseteq B. \end{aligned}(5)✦ For subsets II and YY of E0E_0, a set BβŠ†E0B \subseteq E_0 is an outcome against the interval [I,Y][I, Y] when it satisfies one of the three alternatives of (5)✦, and a family of subsets of E0E_0 meets [I,Y][I, Y] when one of its members is an outcome against it.✦

Prototypes and Their Assembly

A prototype is a pair (T,Οƒ)(T, \sigma) of a subset TT of E0E_0 and a rule Οƒ\sigma✦, and its flip is the prototype (E0\T,¬σ)(E_0 \setminus T, \neg\sigma).✦ The bases of a set PP of prototypes form the family ℬ(P)=⋃(T,Οƒ)∈Pℬσ(T).\mathcal B(P) = \bigcup_{(T, \sigma) \in P} \mathcal B^\sigma(T).(6)✦ Given a rank model on DD, a set PP of prototypes is good when TT is admissible for every (T,Οƒ)∈P(T, \sigma) \in P, PP contains the flip of each of its members, and PP is separated: T\Tβ€²βˆ‰π’₯0T \setminus T' \notin \mathcal J_0 whenever (T,Οƒ)(T, \sigma) and (Tβ€²,Οƒβ€²)(T', \sigma') are distinct members of PP.✦

The complementary pair of a subset BB of E0E_0 is the set {(B,false),(E0\B,true)}\{(B, \mathrm{false}), (E_0 \setminus B, \mathrm{true})\} of prototypes.✦ A stage is either blank or a subset BB of E0E_0; a blank stage has no prototypes, and the prototypes of a stage BB are the complementary pair of BB.✦ Given a rank model on DD with ideal 𝒦\mathcal K and a family (It,Yt)t<𝔠(I_t, Y_t)_{t < \mathfrak c} of pairs of subsets of E0E_0, the assembly is the sequence of stages (ot)t<𝔠(o_t)_{t < \mathfrak c} defined by transfinite recursion, each oto_t being determined from the family and the earlier stages oΞΎo_\xi, ΞΎ<t\xi < t, by the assembly step, which adds a complementary pair for the interval [It,Yt][I_t, Y_t] when that interval is not yet met.✦ The assembled prototypes form the set P𝔠P_{\mathfrak c} of the prototypes of all the stages oto_t.✦ When the prototypes of the earlier stages form a good set, the assembly step at tt chooses oto_t so that adding the prototypes of oto_t keeps the set good and, whenever ItβŠ†YtI_t \subseteq Y_t, makes the bases of the resulting prototypes meet [It,Yt][I_t, Y_t].

The Claim

Theorem 1. Let (𝒦,𝒰,ρ)(\mathcal K, \mathcal U, \rho) be a rank model on DD whose ideal is the family 𝒦\mathcal K of 𝒦\mathcal K-small sets. There is a family ℬ\mathcal B of subsets of E0E_0 such that ℬ is a basis system on E0 and every member of ℬ is admissible.\mathcal B \text{ is a basis system on } E_0 \text{ and every member of } \mathcal B \text{ is admissible.}(7)✦ There is a good set PP of prototypes such that ℬ(P) meets [I,Y] for all IβŠ†YβŠ†E0.\mathcal B(P) \text{ meets } [I, Y] \text{ for all } I \subseteq Y \subseteq E_0.(8)✦ For every family (It,Yt)t<𝔠(I_t, Y_t)_{t < \mathfrak c} of pairs of subsets of E0E_0, the assembled prototypes P𝔠P_{\mathfrak c} satisfy ℬ(P𝔠) meets [It,Yt] for every t<𝔠 with ItβŠ†Yt.\mathcal B(P_{\mathfrak c}) \text{ meets } [I_t, Y_t] \text{ for every } t < \mathfrak c \text{ with } I_t \subseteq Y_t.(9)✦ For every good set PP of fewer than 𝔠\mathfrak c prototypes and all subsets II and YY of E0E_0, there is a stage oo such that the union QQ of PP and the prototypes of oo is good and ℬ(Q) meets [I,Y] whenever IβŠ†Y.\mathcal B(Q) \text{ meets } [I, Y] \text{ whenever } I \subseteq Y.(10)✦ Let PP be a good set of prototypes, and let IβŠ†YβŠ†E0I \subseteq Y \subseteq E_0 be such that ℬ(P)\mathcal B(P) does not meet [I,Y][I, Y]. Then every (T,Οƒ)∈P(T, \sigma) \in P satisfies T\Iβˆ‰π’₯0andY\Tβˆ‰π’₯0,T \setminus I \notin \mathcal J_0 \quad\text{and}\quad Y \setminus T \notin \mathcal J_0,(11)✦ and if PP has fewer than 𝔠\mathfrak c members, there is a subset BB of E0E_0 such that the union QQ of PP and the complementary pair of BB satisfies Q is good and ℬ(Q) meets [I,Y].Q \text{ is good and } \mathcal B(Q) \text{ meets } [I, Y].(12)✦

In the paper, the result reads: there is a nonempty family ℬ\mathcal B of admissible subsets of E0E_0 that is an antichain closed under complements, is closed under the balanced finite swaps, that is, contains (B\F)βˆͺH(B \setminus F) \cup H for every Bβˆˆβ„¬B \in \mathcal B and all finite sets FF and HH with |F|=|H||F| = |H|, and for every IβŠ†YI \subseteq Y with Y\IY \setminus I infinite contains some BB with BβŠ†IB \subseteq I, or IβŠ†BβŠ†YI \subseteq B \subseteq Y, or YβŠ†BY \subseteq B.

What Is Checked

The claim is stated over the doubled ground set E0E_0 and its slices, a rank model (𝒦,𝒰,ρ)(\mathcal K, \mathcal U, \rho) on DD whose ideal is the family 𝒦\mathcal K of (1), the admissible sets of (2), the basis systems of (5), and the prototypes with their local rules (4), their bases (6) and their assembly. The library proves that 𝒦\mathcal K is an ideal on DD:✦ a subset of a member of 𝒦\mathcal K✦ and the union of two members are members✦, and DD is not.✦