Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"

I was going through the text "Introduction to Algorithms" 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

The adjective "maximum-weight" 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.

"A maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$."

Note that "solution" is just a shorthand for "independent set". 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$

StackExchange Computer Science Q#128091, answer score: 4