Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property" I was going through the text &quot;Introduction to Algorithms&quot; by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

Let $M=(S,\ell)$ be a weighted matroid where $S$ is the ground set and $\ell$ is the family of subsets of $S$ called the independent subsets of $S$. Let $w:S\rightarrow\mathbb{R}$ be the corresponding weight function ($w$ is strictly positive).
Let us have an algorithm which finds an optimal subset of $M$ using greedy method as:

$\text{G}{\scriptstyle{\text{REEDY}}}(M,w):$
$1\quad A\leftarrow\phi$
$2\quad \text{sort $S[M]$ into monotonically decreasing order by weight $w$}$
$3\quad \text{for each $x\in S[M]$, taken in monotonically decreasing order by weight $w(x)$}$
$4\quad\quad \text{do if $A\cup\{x\} \in \ell[M]$}$
$5\quad\quad\quad\text{then $A\leftarrow A\cup \{x\}$}$
$6\quad \text{return $A$}$


I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)
Let $x$ be the first element of $S$ chosen by $\text{G}{\scriptstyle{\text{REEDY}}}$ for the weighted matroid $M = (S, \ell)$. The remaining problem of finding a maximum-weight independent subset containing $x$ reduces to finding a maximum-weight independent subset of the weighted matroid $M' = (S', \ell')$, where
$S' = \{y\in S:\{x,y\}\in \ell\}$ ,
$\ell' = \{В \subseteq S - \{x\} : В \cup \{x\} \in \ell\}$ ,
and the weight function for $M'$ is the weight function for $M$, restricted to $S'$. (We call $M'$ the contraction of $M$ by the element $x$.)

Proof:

If $A$ is any maximum-weight independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

Conversely, any independent subset $A'$ of $M'$ yields an independent subset $A = A'\cup\{x\}$ of $M$.

We have in both cases $w(A) = w(A') + w(x)$.

Since we have in both cases that $w(A) = w(A') + w(x)$, a maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$, and vice versa. ■





I could understand $(1),(2),(3)$. But I could not get how the line $(4)$ was arrived in the proof from $(1),(2),(3)$, especially the part in bold-italics. Could anyone please make it clear to me?
The adjective &quot;maximum-weight&quot; should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.
To be fully clear, item (1) should have been the following.

If $A$ is any independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

With item (1) corrected, item (4) follows naturally from item (1), (2) and (3). Here is more detail.

&quot;A maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$.&quot;
Note that &quot;solution&quot; is just a shorthand for &quot;independent set&quot;. Let us prove the proposition above.
Suppose $A$ is a maximum-weight solution in $M$. Then $A$ yields $A'=A-\{x\}$, which is a solution in $M'$ according to item (1). (The previous version of item (1) works as well.)
Given any solution $B'$ in $M'$, let $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).
Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ Since $A$ has maximum weight in $M$, we have $w(A)\ge w(B)$, i.e.,
$$w(A')+w(x)\ge w(B')+w(x).$$
Cancelling $w(x)$ from both sides, we obtain
$$w(A')\ge w(B'),$$
which says $A'$ is a maximum-weight solution in $M'$. $\checkmark$

A maximum-weight solution in $M'$ yields a maximum-weight solution in $M$ containing $x$.
The other direction, as stated above, can be proved similarly. Here is the proof.
Suppose $B'$ is a maximum-weight solution in $M'$. Then $B'$ yields $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).
Given any solution $A$ in $M$, let $A'=A-\{x\}$, which is a solution in $M'$ according to (the corrected version of) item (1).
Since $B'$ has maximum weight in $M'$, we have $w(B')\ge w(A')$. Adding $w(x)$ to both sides, we obtain,
$$w(B')+w(x)\ge w(A')+w(x).$$
Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$  So the inequality above is the same as
$$w(B)\ge w(A),$$
which says $B$ is a maximum-weight solution in $M$. $\checkmark$