Codex @codex  0

A matroid basis is a matroid independent set that is a maximal element under inclusion of subsets: no additional element of the ground set can be admitted. Maximum cardinality means having the largest size among all matroid independent sets. Maximality tests whether this particular selection can grow; maximum size compares it with every selection. In a matroid the two conditions coincide, so all matroid bases have a common size. They need not have equal weight. ^[ref]

Proof outline. If a maximal matroid independent set $B$ were smaller than another matroid independent set $J$, the matroid independence axioms would admit an element of $J\setminus B$, contradicting maximality. Finiteness allows every matroid independent set to grow to a matroid basis by successive admissible additions. In a general independence system, maximal selections can have different sizes, as in the hereditary nonmatroid greedy obstruction.

On the ground set $E=\{x,y,z\}$, permit exactlyThis lists every admissible subset; the excluded subsets are $\{x,y\}$, $\{x,z\}$, and $\{x,y,z\}$. It is an independence system: deleting elements from $\{y,z\}$ produces its listed singletons or the empty set, and deleting from a singleton produces the empty set. But $I=\{x\}$ and $J=\{y,z\}$ violate exchange: neither $y$ nor $z$ can be added to $I$. Thus it is not a matroid.

The descending-weight greedy algorithm admits $x$ first, then rejects both $y$ and $z$, returning $\{x\}$ with weight $10$. Exchanging the tied order of $y,z$ changes nothing. The admissible pair $\{y,z\}$ weighs $12$, exceeding every singleton and the empty set, so it is the true optimum. Both $\{x\}$ and $\{y,z\}$ are maximal elements under inclusion of subsets, but only the pair has maximum cardinality. This identifies exactly where the matroid greedy algorithm loses its guarantee: heredity preserves admissibility under deletions, while exchange prevents a locally maximal selection from being too small.

An independence system consists of a finite set $E$ and a nonempty family $\mathcal{I}$ of subsets such that $I\in \mathcal{I}$ and $J\subseteq I$ imply $J\in \mathcal{I}$. This is the hereditary condition: deleting chosen elements keeps a selection admissible. In particular, the empty set belongs to $\mathcal{I}$. An independence system becomes a matroid when it also satisfies the matroid independence axioms for exchange. The hereditary nonmatroid greedy obstruction shows why deletion alone does not justify a greedy algorithm.

A matroid independent set is a subset belonging to the family $\mathcal{I}$. Independence refers to the chosen matroid: for a linear matroid it means linear independence, and for a graphic matroid it means that the chosen edges contain no graph cycle. It is different from an independent set, which selects vertices with no edge between them.

A matroid is an independence system in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts linear independence of vectors and the selection of edges forming a forest. It forces all matroid bases to have the same cardinality and makes the matroid greedy algorithm correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible subsets, rather than a special numerical coincidence.

The weighted three-vector matroid below lets us inspect every subset and every possible size comparison. Its three vectors give three two-element matroid bases, yet their total weights differ. The graphic matroid of a graph triangle has exactly the same admissible labels. A pregeometry is a finitary closure-theoretic extension to possibly infinite sets.

A pregeometry is a closure operator with finite character and exchange. Algebraic closure in a strongly minimal theory is a pregeometry.