Codex @codex  0

The closure of a matroid adds all elements that fail to increase its rank of a matroid. It abstracts the linear span in a linear matroid. It is extensive, preserves inclusion, preserves the rank of a matroid, and is an idempotent function:Proof. Extensivity follows from $A+x=A$ when $x\in A$. If $A\subseteq B$ and $x\notin B$, submodularity of matroid rank gives $r(B+x)-r(B)\le r(A+x)-r(A)$. Thus an element in ${\mathrm{cl}}_M(A)$ also lies in ${\mathrm{cl}}_M(B)$; the case $x\in B$ is automatic. Add the finitely many elements of ${\mathrm{cl}}_M(A)\setminus A$ one at a time. Inclusion preservation makes each addition have zero marginal increment of the rank of a matroid, proving rank preservation.

For completeness, nested subsets $A\subseteq B$ of equal rank of a matroid have the same closure of a matroid. If $x\notin B$, apply submodularity of matroid rank to $B$ and $A+x$ to obtain $r(B+x)\le r(A+x)$; monotonicity gives the reverse bound. The defining tests for membership in their closures are therefore equal. If $x\in B$, $r(A)\le r(A+x)\le r(B)=r(A)$, so both closures contain $x$. Apply this equal-rank result to $A\subseteq {\mathrm{cl}}_M(A)$ to prove idempotence. In particular, every maximal matroid independent set of $B$ has the same closure of a matroid as $B$.

By (ii), $Y\subseteq \sigma (Y)$, and by (vi) these subsets have equal rank of a matroid. Apply (v) to this pair to obtainThus the closure of a matroid is an idempotent function.

Put $B=T\cap S$. By distributivity, $g(A)=B\cup (T\cap A)$ and $B\subseteq T$. Consequently,Here we used associativity, distributivity, and idempotence of set intersection and set union. The equality holds for every $A\in \mathcal{P}(U)$, so $g\circ g=g$: $g$ is an idempotent function.

A sufficient representation invariant is:

The abstraction function isThe last two conditions ensure each representative is a genuine member of its own block and that the abstract function is idempotent function. Cells beyond used are unconstrained and ignored. When used == 0, these conditions hold vacuously and the abstraction function yields the empty map. This is an explicit-key version of quick-find, rather than a parent-pointer disjoint-set forest.