Let $E$ be a finite set, and let $\mathcal I \subseteq 2^E$ be an independence system, meaning that $\varnothing \in \mathcal I$ and whenever $J \subseteq I \in \mathcal I$, one has $J \in \mathcal I$. For a weight function $w: E \to \mathbb R_{\geq 0}$ and a linear ordering of $E$ in nonincreasing order of weight, the greedy algorithm scans the elements in that order and adds an element exactly when doing so keeps the current set in $\mathcal I$.

Then the following are equivalent.

1. $(E,\mathcal I)$ is a matroid. 2. For every weight function $w: E \to \mathbb R_{\geq 0}$ and every tie-breaking order among elements of equal weight, the greedy algorithm returns a member $G \in \mathcal I$ such that

\begin{align*} \sum_{e \in G} w(e) = \max_{I \in \mathcal I} \sum_{e \in I} w(e). \end{align*}