OctoInformBeta

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

Theorem 5.5: Independent non-bases extend by any element; for each rank model with ideal 𝒦\mathcal K, some basis system on E0E_0 has only admissible members

Basis systems are base families of self-dual matroids.

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 matroid MM on a set Ξ±\alpha is self-dual when M*=MM^*=M on the same labelled set, which holds exactly when the complement of every basis of MM is a basis of MM. Section 5 assembles a self-dual matroid on E0=LβŠ”R=DΓ—{false,true}E_0=L\sqcup R=D\times\{\mathrm{false},\mathrm{true}\}, two copies of the countable set DD of pairs (m,f)(m,f) with mβˆˆβ„•m\in\mathbb N and f:{0,1}mβ†’{0,1}f\colon\{0,1\}^m\to\{0,1\}, with LL the copy DΓ—{false}D\times\{\mathrm{false}\} and RR the copy DΓ—{true}D\times\{\mathrm{true}\}. Every basis of this matroid is to be admissible for a rank model, a condition comparing the ranks of the parts of the basis in LL and in RR.

A matroid on Ξ±\alpha can be given by its bases: a nonempty family of subsets of Ξ±\alpha with base exchange and the maximality axiom is the family of bases of exactly one matroid on Ξ±\alpha. Theorem 5.5 gives conditions on a family closed under complements under which both axioms hold and the matroid is self-dual, and it supplies a family on E0E_0 meeting them with every member admissible.

Basis Systems

A family ℬ\mathcal B of subsets of Ξ±\alpha has the interval alternative when, for all sets IβŠ†YβŠ†Ξ±I\subseteq Y\subseteq\alpha with Y\IY\setminus I infinite, some Bβˆˆβ„¬B\in\mathcal B satisfies BβŠ†IorIβŠ†BβŠ†YorYβŠ†B.B\subseteq I\quad\text{or}\quad I\subseteq B\subseteq Y\quad\text{or}\quad Y\subseteq B.(1)✦

A basis system ℬ\mathcal B on a set Ξ±\alpha is a nonempty family of subsets of Ξ±\alpha with the interval alternative, no member of which properly contains another, closed under complements and under exchanging one element of a member for one outside it: for all B,Cβˆˆβ„¬B,C\in\mathcal B, e∈Be\in B and f∈α\Bf\in\alpha\setminus B, BβŠ†C⟹B=C,Ξ±\Bβˆˆβ„¬,(B\{e})βˆͺ{f}βˆˆβ„¬.B\subseteq C\implies B=C,\qquad \alpha\setminus B\in\mathcal B,\qquad (B\setminus\{e\})\cup\{f\}\in\mathcal B.(2)✦

A subset II of Ξ±\alpha is independent for a basis system ℬ\mathcal B when it lies in some member of ℬ\mathcal B.✦

Ideals and Rank Models

An ideal on a set Ξ±\alpha is a family of subsets of Ξ±\alpha that contains βˆ…\emptyset, contains every subset of each of its members and the union of any two of its members, and does not contain Ξ±\alpha.✦ For an ideal ℐ\mathcal I and sets X,YβŠ†Ξ±X,Y\subseteq\alpha, we write XβŠ†β„YX\subseteq_{\mathcal I}Y when X\Yβˆˆβ„X\setminus Y\in\mathcal I.✦

A rank model RR on a set Ξ±\alpha consists of an ideal ℐ\mathcal I on Ξ±\alpha, an ultrafilter 𝒰\mathcal U on Ξ±\alpha containing no member of ℐ\mathcal I, and a rank ρ\rho assigning to each subset of Ξ±\alpha an ordinal below 𝔠\mathfrak c, the continuum taken as its initial ordinal.✦ The rank is antitone modulo ℐ\mathcal I on large sets, those in 𝒰\mathcal U, and admits rank-raising thinning: for all X,Yβˆˆπ’°X,Y\in\mathcal U, every sβŠ†Xs\subseteq X with sβˆ‰π’°s\notin\mathcal U and every Ξ³<𝔠\gamma<\mathfrak c, XβŠ†β„Y⟹ρ(Y)≀ρ(X),some uβˆˆπ’° has sβŠ†uβŠ†X and ρ(u)>Ξ³.X\subseteq_{\mathcal I}Y\implies\rho(Y)\le\rho(X),\qquad \text{some }u\in\mathcal U\text{ has }s\subseteq u\subseteq X\text{ and }\rho(u)>\gamma.(3)✦

The slices of a set XβŠ†E0X\subseteq E_0 are 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\}.✦ For a rank model RR on DD with ultrafilter 𝒰\mathcal U and rank ρ\rho, a set XβŠ†E0X\subseteq E_0 is admissible for RR when XLβˆˆπ’°,D\XRβˆˆπ’°,ρ(D\XR)<ρ(XL),orXLβˆ‰π’°,D\XRβˆ‰π’°,ρ(XR)<ρ(D\XL).\begin{aligned} &X_L\in\mathcal U,\quad D\setminus X_R\in\mathcal U,\quad \rho(D\setminus X_R)<\rho(X_L), \quad\text{or}\\ &X_L\notin\mathcal U,\quad D\setminus X_R\notin\mathcal U,\quad \rho(X_R)<\rho(D\setminus X_L). \end{aligned}(4)✦

Columns and Small Sets

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.✦ The density of a set XX in a finite set ss is |X∩s|/|s||X\cap s|/|s|✦, and Ξ΄m(X)=|X∩Dm|/wm\delta_m(X)=|X\cap D_m|/w_m is the density of XβŠ†DX\subseteq D in DmD_m✦. A subset XX of DD is density small when Ξ΄m(X)β†’0\delta_m(X)\to0 as mβ†’βˆžm\to\infty; the density small sets form the ideal π’₯\mathcal J.✦

Fix a bijection Ξ²\beta from the indices below 𝔠\mathfrak c onto the set {0,1}β„•\{0,1\}^{\mathbb N} of binary sequences.✦ 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\}✦, and its binary string is the sequence sΞΎ,is_{\xi,i} with sΞΎ,i(n)={1if n<2 and n=i,0if n<2 and nβ‰ i,Ξ²(ΞΎ)(nβˆ’2)if nβ‰₯2.s_{\xi,i}(n)=\begin{cases} 1 & \text{if } n<2 \text{ and } n=i,\\ 0 & \text{if } n<2 \text{ and } n\neq i,\\ \beta(\xi)(n-2) & \text{if } n\ge 2. \end{cases}(5)✦ The column of the tag (ΞΎ,i)(\xi,i) is the set of pairs (m,f)∈D(m,f)\in D for which ff takes the value 11 at sΞΎ,i|ms_{\xi,i}|m, the prefix of sΞΎ,is_{\xi,i} made of its first mm bits.✦ 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 meet AF=β‹‚t∈FAtA_F=\bigcap_{t\in F}A_t is the intersection of these columns, with Aβˆ…=DA_\emptyset=D✦.

The family 𝒦\mathcal K consists of the subsets XX of DD, called 𝒦\mathcal K-small, for which the part of XX inside some meet of finitely many columns is density small: Xβˆˆπ’¦β‡”X∩AF∈π’₯for some finite set F of indices below 𝔠.X\in\mathcal K\iff X\cap A_F\in\mathcal J\ \text{for some finite set } F \text{ of indices below } \mathfrak c.(6)✦

The Claim

Theorem 1. Let ℬ\mathcal B be a basis system on a set Ξ±\alpha. Then ℬ\mathcal B satisfies base exchange: for all B,Bβ€²βˆˆβ„¬B,B'\in\mathcal B and every e∈B\Bβ€²e\in B\setminus B' there is f∈Bβ€²\Bf\in B'\setminus B with (B\{e})βˆͺ{f}βˆˆβ„¬.(B\setminus\{e\})\cup\{f\}\in\mathcal B.(7)✦ It satisfies the maximality axiom: for every set II independent for ℬ\mathcal B and every YY with IβŠ†YβŠ†Ξ±I\subseteq Y\subseteq\alpha there is a set JJ with IβŠ†JβŠ†Y,J maximal among the subsets of Y independent for ℬ.I\subseteq J\subseteq Y,\qquad J \text{ maximal among the subsets of } Y \text{ independent for } \mathcal B.(8)✦ The matroid M(ℬ)M(\mathcal B) on Ξ±\alpha given by these bases has exactly the members of ℬ\mathcal B as its bases: for every BβŠ†Ξ±B\subseteq\alpha, B is a basis of M(ℬ)⇔Bβˆˆβ„¬.B \text{ is a basis of } M(\mathcal B)\iff B\in\mathcal B.(9)✦ This matroid is self-dual, M(ℬ)*=M(ℬ),M(\mathcal B)^*=M(\mathcal B),(10)✦ and if II is independent in M(ℬ)M(\mathcal B) but is not a basis of it, then for every e∈αe\in\alpha Iβˆͺ{e} is independent in M(ℬ).I\cup\{e\} \text{ is independent in } M(\mathcal B).(11)✦ For every rank model RR on DD whose ideal is 𝒦\mathcal K, there is a basis system ℬ\mathcal B on E0E_0 with B admissible for Rfor every Bβˆˆβ„¬.B \text{ admissible for } R \quad\text{for every } B\in\mathcal B.(12)✦

In the paper, the result reads: there is a matroid QQ on E0=LβŠ”RE_0=L\sqcup R whose bases are exactly the members of the family ℬ\mathcal B of Proposition 5.4, with Q=Q*Q=Q^* on the same labels and every basis admissible, so that in particular every basis BB with BLβˆˆπ’°B_L\in\mathcal U has D\BRβˆˆπ’°D\setminus B_R\in\mathcal U and ρ(BL)>ρ(D\BR)\rho(B_L)>\rho(D\setminus B_R), and every independent set of QQ that is not a basis extends by any element outside it. The matroid M(ℬ)M(\mathcal B) of a basis system ℬ\mathcal B as in (12) is such a matroid QQ.

What Is Checked

The claim is stated over basis systems (2) on an arbitrary set Ξ±\alpha, with the interval alternative (1), independence for ℬ\mathcal B and the matroid M(ℬ)M(\mathcal B) given by its bases, and, in (12), over rank models (3) on DD whose ideal is the family 𝒦\mathcal K of (6), with the admissible subsets (4) of E0E_0.

The library proves that 𝒦\mathcal K is an ideal on DD✦: the empty set is 𝒦\mathcal K-small, every subset of a 𝒦\mathcal K-small set✦ and the union of any two 𝒦\mathcal K-small sets are 𝒦\mathcal K-small✦, and DD is not 𝒦\mathcal K-small✦.