All bases of a matroid have the same cardinality
ProvedFamousTheorems.matroid_bases_equal_card_7bAll bases of a matroid have the same cardinality. Let be a matroid on a ground set (possibly infinite). If and are bases of , then , where the cardinalities are taken in .
This is the matroid form of the invariance of dimension, and it makes the rank of a matroid well defined. For the matroid of linearly independent columns of a matrix it recovers the fact that all bases of a vector space have the same size. For the graphic matroid it says that all spanning forests of a graph have the same number of edges. The proof uses the basis exchange axiom.
Formalization note. Mathlib's Matroid.IsBase.encard_eq_encard_of_isBase. Set.encard is the cardinality of a set in ℕ∞, equal to for infinite sets, so the statement covers matroids of infinite rank only in the sense that both bases are infinite.
import Mathlib
namespace FamousTheorems
theorem matroid_bases_equal_card_7b {α : Type*} {M : Matroid α} {B₁ B₂ : Set α} (h₁ : M.IsBase B₁) (h₂ : M.IsBase B₂) :
B₁.encard = B₂.encard := by sorry
end FamousTheoremsConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.