OctoInformBeta

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

Lemma 5.3: An admissible BB with AβŠ†BβŠ†ZA\subseteq B\subseteq Z such that B\TiB\setminus T_i and Ti\BT_i\setminus B lie outside π’₯0\mathcal J_0 for every ii

Inserting an admissible set separated from fewer than 𝔠\mathfrak c sets.

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

This lemma is a step in the assembly of a self-dual matroid in Β§5. It works on the doubled ground set E0E_0, two copies of a countable set DD, with an ultrafilter 𝒰\mathcal U on DD and a rank ρ\rho that assigns to subsets of DD ordinals below the continuum 𝔠\mathfrak c, taken as its initial ordinal.

The set DD consists of the 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\}✦; its block Dm={m}Γ—{0,1}{0,1}mD_m=\{m\}\times\{0,1\}^{\{0,1\}^m} is finite, with wm=22mw_m=2^{2^m} elements.✦ The doubled ground set is E0=DΓ—{false,true}=LβŠ”RE_0=D\times\{\mathrm{false},\mathrm{true}\}=L\sqcup R, where LL holds the pairs with second entry false and RR those with second entry true.✦ A subset XX of E0E_0 has two slices, the subsets of DD XL={d∈D:(d,false)∈X},XR={d∈D:(d,true)∈X},X_L=\{d\in D:(d,\mathrm{false})\in X\},\qquad X_R=\{d\in D:(d,\mathrm{true})\in X\},(1)✦ and the doubled block Wm=DmΓ—{L,R}W_m=D_m\times\{L,R\} is the finite subset of E0E_0 lying over DmD_m.✦

Density Ideals and Columns

An ideal ℐ\mathcal I of subsets of a set Ξ±\alpha is a family of subsets of Ξ±\alpha that contains the empty set, is closed under subsets and under unions of two 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.✦

The density of a subset XX of a set Ξ±\alpha in a finite subset ss of Ξ±\alpha is the number of elements of the trace X∩sX\cap s divided by |s||s|.✦ The ideal π’₯\mathcal J on DD and the ideal π’₯0\mathcal J_0 on E0E_0 collect the sets whose density in the blocks tends to 00 as mβ†’βˆžm\to\infty: π’₯={XβŠ†D:|X∩Dm|wmβ†’0},π’₯0={XβŠ†E0:|X∩Wm||Wm|β†’0}.\mathcal J=\Bigl\{X\subseteq D:\ \frac{|X\cap D_m|}{w_m}\to 0\Bigr\},\qquad \mathcal J_0=\Bigl\{X\subseteq E_0:\ \frac{|X\cap W_m|}{|W_m|}\to 0\Bigr\}.(2) A subset of E0E_0 is π’₯0\mathcal J_0-positive when it does not belong to π’₯0\mathcal J_0.

The indices t,ΞΎ,Ξ³t,\xi,\gamma are the ordinals below 𝔠\mathfrak c.✦ Fix a bijection Ξ²\beta from the set of these indices 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<\mathfrak c and a label i∈{0,1,2}i\in\{0,1,2\}✦, and its binary string is the sequence hΞΎ,i∈{0,1}β„•h_{\xi,i}\in\{0,1\}^{\mathbb N} with bits hΞΎ,i(n)={1if n<2 and n=i,0if n<2 and nβ‰ i,Ξ²(ΞΎ)(nβˆ’2)if nβ‰₯2.h_{\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}(3)✦ The column of a tag (ΞΎ,i)(\xi,i) is the set of pairs (m,f)∈D(m,f)\in D with f(hΞΎ,i|m)=1f(h_{\xi,i}|_m)=1✦, where the prefix h|m∈{0,1}mh|_m\in\{0,1\}^m of a sequence hh is the string of its first mm bits.✦ For an index t<𝔠t<\mathfrak c, the column AtA_t is the column of the tag (t,0)(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.✦ The ideal 𝒦\mathcal K of subsets of DD consists of the sets XβŠ†DX\subseteq D for which X∩AF∈π’₯for some finite set F of indices.X\cap A_F\in\mathcal J\quad\text{for some finite set } F \text{ of indices}.(4)

Rank Models and Admissible Sets

A rank model on a set Ξ±\alpha is a triple (ℐ,𝒰,ρ)(\mathcal I,\mathcal U,\rho) of an ideal ℐ\mathcal I of subsets of Ξ±\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, subject to two conditions.✦ Call a subset of Ξ±\alpha large when it belongs to 𝒰\mathcal U. The rank 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),(5) and it admits rank-raising thinning: whenever Xβˆˆπ’°X\in\mathcal U, sβŠ†Xs\subseteq X is not in 𝒰\mathcal U and Ξ³<𝔠\gamma<\mathfrak c, some uβˆˆπ’°u\in\mathcal U has sβŠ†uβŠ†Xandρ(u)>Ξ³.s\subseteq u\subseteq X\quad\text{and}\quad\rho(u)>\gamma.(6)

For a rank model (ℐ,𝒰,ρ)(\mathcal I,\mathcal U,\rho) on DD, a subset XX of E0E_0 is upper when XLβˆˆπ’°, and ρ(XL)≀ρ(D\XR) whenever D\XRβˆˆπ’°,X_L\in\mathcal U,\ \text{ and }\ \rho(X_L)\le\rho(D\setminus X_R)\ \text{ whenever }\ D\setminus X_R\in\mathcal U,(7)✦ and lower when its complement E0\XE_0\setminus X is upper.✦ A subset XX of E0E_0 is admissible for the model when one of two cases holds: 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}(8)✦

The Claim

Theorem 1. Let (𝒦,𝒰,ρ)(\mathcal K,\mathcal U,\rho) be a rank model on DD whose ideal is 𝒦\mathcal K, let (Ti)i∈I(T_i)_{i\in I} be a family of subsets of E0E_0 indexed by a set II of cardinality less than 𝔠\mathfrak c, and let AβŠ†ZA\subseteq Z be subsets of E0E_0 such that AA is not upper, ZZ is not lower, and Ti\AT_i\setminus A and Z\TiZ\setminus T_i are π’₯0\mathcal J_0-positive for every i∈Ii\in I. Then there is an admissible subset BB of E0E_0 with AβŠ†BβŠ†Z,B\Tiβˆ‰π’₯0 and Ti\Bβˆ‰π’₯0for every i∈I.A\subseteq B\subseteq Z,\qquad B\setminus T_i\notin\mathcal J_0\ \text{ and }\ T_i\setminus B\notin\mathcal J_0\quad\text{for every } i\in I.(9)✦

In the paper, the result reads: for a set 𝒯\mathcal T of fewer than 𝔠\mathfrak c admissible subsets of E0E_0 and subsets AβŠ†ZA\subseteq Z of E0E_0 with AA not upper, ZZ not lower and T\A,Z\Tβˆ‰π’₯0T\setminus A,\ Z\setminus T\notin\mathcal J_0 for every Tβˆˆπ’―T\in\mathcal T, some admissible BB with AβŠ†BβŠ†ZA\subseteq B\subseteq Z has B\Tβˆ‰π’₯0B\setminus T\notin\mathcal J_0 and T\Bβˆ‰π’₯0T\setminus B\notin\mathcal J_0 for every Tβˆˆπ’―T\in\mathcal T.

The theorem does not ask the sets TiT_i to be admissible, so the paper’s statement is its case of an admissible family.

What Is Checked

The claim (9) is stated over a rank model on DD whose ideal is the ideal 𝒦\mathcal K of (4), over the ideal π’₯0\mathcal J_0 of (2), over the upper, lower and admissible sets of (7) and (8), and over families of subsets of E0E_0 indexed by sets of cardinality less than 𝔠\mathfrak c.

The library proves that 𝒦\mathcal K is a proper ideal✦: a subset of a member of 𝒦\mathcal K is a member✦, the union of two members is a member✦, DD is not a member✦, and every member of π’₯\mathcal J, the empty set among them, is a member.