OctoInformBeta

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

Remark 5.6: Every subset of α\alpha is independent or spanning in the matroid whose bases are those of a basis system on α\alpha

The matroid of a basis system is uniform.

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 is uniform when every subset of its ground set is independent or spanning in MM.✦ Remark 5.6 is about the matroid MSM_S of a basis system SS, both defined below.

Basis Systems

A family ℬ\mathcal B of subsets of a set α\alpha satisfies 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 SS on a set α\alpha is a nonempty family of subsets of α\alpha, called its bases, that is an antichain under inclusion, satisfies the interval alternative (1), and is closed under complements and under single exchanges: for every basis BB, every e∈Be \in B and every f∈α\Bf \in \alpha \setminus B, α\B∈Sand(B\{e})∪{f}∈S.\alpha \setminus B \in S \qquad\text{and}\qquad (B \setminus \{e\}) \cup \{f\} \in S.(2)✦ A subset II of α\alpha is independent in a basis system SS on α\alpha when II is contained in some basis of SS.

The matroid MSM_S of a basis system SS on α\alpha is the matroid on all of α\alpha whose bases are the bases of SS.✦

The Claim

Theorem 1. Let SS be a basis system on a set α\alpha. Then the matroid MSM_S is uniform: for every subset XX of α\alpha, X is independent in MSorX is spanning in MS.X \text{ is independent in } M_S \quad\text{or}\quad X \text{ is spanning in } M_S.(3)✦

In the paper, the result reads: for the matroid QQ on the countable set E0E_0, every subset of E0E_0 is independent or spanning in QQ, QQ has infinite rank and infinite corank, every finite set is independent, E0E_0 is dependent, and QQ is neither finitary nor cofinitary. The theorem gives the first of these clauses for the matroid of every basis system, QQ among them.

What Is Checked

The claim is stated over a basis system SS on an arbitrary set α\alpha, a family of bases subject to the antichain condition, the interval alternative (1) and the closure conditions (2); over the matroid MSM_S on α\alpha with these bases; and over the notion of a uniform matroid.

The library proves that the bases of a basis system satisfy the base axioms of an infinite matroid. They have the basis exchange property: for bases BB and B′B' and an element e∈B\B′e \in B \setminus B', some f∈B′\Bf \in B' \setminus B makes (B\{e})∪{f}(B \setminus \{e\}) \cup \{f\} a basis.✦ And every set II that is independent in SS and contained in a set Y⊆αY \subseteq \alpha extends to a maximal independent subset of YY.✦