[proofplan] Use basis exchange to prove greedy optimality for matroids for every nonincreasing order. Conversely, if exchange fails, choose two independent sets witnessing the failure and put weights on them so one allowed nonincreasing order forces greedy to keep the smaller set while the larger one extends to a heavier basis. [/proofplan] [step:Compare greedy with an optimal basis by exchange] Assume first that $(E,\mathcal I)$ is a matroid. Let $G=\{g_1,\ldots,g_r\}$ be the basis selected by the greedy algorithm, listed in the order in which its elements are chosen. Let $B$ be a maximum-weight basis. It is enough to show that $w(G)\ge w(B)$, since $B$ was chosen with maximum possible weight among bases. [guided] Start with an arbitrary maximum-weight basis $B$ and the greedy basis $G=\{g_1,\ldots,g_r\}$. The goal is to replace $B$ one element at a time until it contains $g_1,\ldots,g_r$, never lowering its weight. After $k-1$ replacements, suppose the current maximum-weight basis is $B_{k-1}$ and contains $g_1,\ldots,g_{k-1}$. If $g_k$ is already in $B_{k-1}$, no replacement is needed. If $g_k\notin B_{k-1}$, basis exchange gives some $b\in B_{k-1}\setminus\{g_1,\ldots,g_{k-1}\}$ such that \begin{align*} (B_{k-1}\setminus\{b\})\cup\{g_k\} \end{align*} is again a basis. The set $\{g_1,\ldots,g_{k-1},b\}$ is independent because it is contained in $B_{k-1}$. Thus, if $b$ had appeared before $g_k$ in the chosen nonincreasing order, greedy would have accepted $b$ before selecting $g_k$. Hence $g_k$ appears no later than $b$, and $w(g_k)\ge w(b)$. Therefore replacing $b$ by $g_k$ gives a basis $B_k$ with $w(B_k)\ge w(B_{k-1})$. Inducting over $k$ yields $B_r=G$ and $w(G)\ge w(B)$. [/guided] For each $k$ with $0\le k\le r$, we construct a maximum-weight basis $B_k$ such that $\{g_1,\ldots,g_k\}\subset B_k$. Take $B_0=B$. Suppose $B_{k-1}$ has been constructed. If $g_k\in B_{k-1}$, set $B_k=B_{k-1}$. Otherwise, the basis exchange axiom gives an element $b\in B_{k-1}\setminus \{g_1,\ldots,g_{k-1}\}$ such that \begin{align*} B_k=(B_{k-1}\setminus\{b\})\cup\{g_k\} \end{align*} is a basis. The set $\{g_1,\ldots,g_{k-1},b\}$ is independent because it is contained in $B_{k-1}$. Therefore, if $b$ had appeared before $g_k$ in the chosen nonincreasing order, greedy would have accepted $b$ before it selected $g_k$. Hence $g_k$ appears no later than $b$ in that order, so $w(g_k)\ge w(b)$. It follows that $w(B_k)\ge w(B_{k-1})$. By induction, $B_r=G$ is a basis and $w(G)=w(B_r)\ge w(B_0)=w(B)$. Thus greedy returns a maximum-weight basis for every nonnegative weight function and every nonincreasing order. [/step] [step:Force a greedy failure when exchange fails] Conversely, suppose $(E,\mathcal I)$ is not a matroid. Since $\mathcal I$ is nonempty and hereditary, failure of the matroid axiom means that there are independent sets $I,J\in\mathcal I$ with $|I|<|J|$ such that \begin{align*} I\cup\{e\}\notin\mathcal I \end{align*} for every $e\in J\setminus I$. Define $w:E\to\mathbb R_{\ge 0}$ by setting $w(x)=1+\varepsilon$ for $x\in I$, setting $w(x)=1$ for $x\in J\setminus I$, and setting $w(x)=0$ otherwise, where $\varepsilon>0$ is chosen so that $(1+\varepsilon)|I|<|J|$. If $I=\varnothing$, choose any $\varepsilon$ with $0<\varepsilon<|J|$. Use a nonincreasing order in which the elements of $I$ are considered before all elements of $J\setminus I$; this is allowed because elements of $I$ have weight $1+\varepsilon$ and elements of $J\setminus I$ have weight $1$. The greedy algorithm accepts every element of $I$, because every subset of $I$ lies in $\mathcal I$ by heredity. After all elements of $I$ have been accepted, each element of $J\setminus I$ is rejected by the displayed exchange failure. Therefore the greedy output has weight at most $(1+\varepsilon)|I|$; any later accepted elements have weight $0$. Since $E$ is finite, extend the independent set $J$ to a maximal independent set $B_J$, so $B_J$ is a basis of the hereditary family. All weights are nonnegative, and each element of $J$ has weight at least $1$, so \begin{align*} w(B_J)\ge w(J)\ge |J|>(1+\varepsilon)|I|. \end{align*} Thus there is a basis $B_J$ with strictly larger weight than the greedy output. Greedy does not return a maximum-weight basis for this nonnegative weight function. [/step] [step:Conclude the equivalence] The first step proves that every matroid has the asserted greedy optimality property for every allowed nonincreasing order. The second step proves the contrapositive of the converse: if the hereditary family is not a matroid, then some nonnegative weight function and some allowed nonincreasing order make greedy non-optimal. The two statements together give the desired if and only if. [/step]