I am confused about a step in showing how the Farkas Lemma (really, Gale's theorem) can be used to prove strong duality in linear programming. Consider the following duality pair of LPs:
By weak duality, we only need to show that \begin{align} \exists(x,y) : \begin{cases} Ax\leq b,\; x\geq0\\ A^\top y \geq c,\; y\geq0\\ c^\top x\geq b^\top y. \end{cases} \tag{$*$} \end{align}
Then we have \begin{align*} &\iff \exists(x,y) : \begin{cases} Ax\leq b,\; x\geq0\\ A^\top y \geq c,\; y\geq0\\ c^\top x\geq b^\top y. \end{cases} &(\text{weak duality})\\ &\iff \exists(x,y) : \begin{cases} { \begin{bmatrix} A & 0\\ -I & 0\\ 0 & -A^\top\\ 0 & -I\\ -c^\top & b^\top \end{bmatrix} } {\begin{bmatrix} x\\y \end{bmatrix}} \leq {\begin{bmatrix} b\\0\\-c\\0\\0 \end{bmatrix}} \end{cases},\;\;x\geq0,\;\;y\geq0\\ &\iff \not\exists \begin{bmatrix} s\\ t\\ u\\ v\\ w \end{bmatrix} : \begin{cases} \begin{bmatrix} s\\t\\u\\v\\w \end{bmatrix}\geq0,\; \begin{bmatrix} s\\t\\u\\v\\w \end{bmatrix}^\top \begin{bmatrix} A & 0\\ -I & 0\\ 0 & -A^\top\\ 0 & -I\\ -c^\top & b^\top \end{bmatrix}=0,\; \begin{bmatrix} s\\t\\u\\v\\w \end{bmatrix}^\top \begin{bmatrix} b\\0\\-c\\0\\0 \end{bmatrix} < 0 \end{cases} & (\text{Farkas/Gale})\\ &\iff \not\exists \begin{bmatrix} s\\t\\u\\v\\w \end{bmatrix}\geq0 : \begin{cases} s^\top A - t^\top -w c^\top = 0_n^\top &\iff s^\top A -w c^\top \geq 0_n^\top\\ -u^\top A^\top - v^\top +wb^\top = 0_m^\top &\iff -u^\top A^\top +wb^\top \geq 0_m^\top\\ s^\top b -u^\top c < 0 &\iff b^\top s < c^\top u \end{cases}\\ &\iff \not\exists \begin{bmatrix} s\\u\\w \end{bmatrix}\geq0 : \begin{cases} A^\top s \geq wc\\ A u \leq wb\\ b^\top s < c^\top u \end{cases}\\ &\color{red}{\iff} \not\exists \begin{bmatrix} s\\u \end{bmatrix}\geq0 : \begin{cases} A^\top s \geq 0\\ A u \leq 0\\ b^\top s < c^\top u \end{cases} &(\text{weak duality})\tag{$**$}\\ &\iff \left\{ \left\{A^\top s\geq 0,\; Au\leq 0,\; s\geq0,\;u\geq0 \right\} \implies b^\top s \geq c^\top u \right\} \end{align*} and finally $(***)$, assuming that $Au\leq0,A^\top s\geq0, s\geq0, u\geq0$ we have \begin{align*} b^\top s - c^\top u \geq (Ax)^\top s - (A^\top y)^\top u = x^\top A^\top s - y^\top Au \geq 0-0=0 \end{align*}
The proof is taken from p.17 of these notes. I don't understand how $(**)$ and $(***)$ are used. Can someone please explain?
Inspiration from these notes.
For $(**)$, we can take $w=0$ or $w>0$. If $w>0$, then we can scale $s'=s/w$, $x'=x/w$ so that we have the condition to prove is equivalent to \begin{align} \exists(x',y')\geq0: \begin{cases} A^\top s'\geq c\\Ax' \leq b\\ b^\top y' < c^\top x' \end{cases} \end{align} which by weak duality on the ``prime'' system (e.g., $b^\top y'\geq c^\top x'$) gives a contradiction. Hence $w\equiv0$.
For $(***)$, we just have to show that when $w\equiv0$, we can always find $s,u\geq0$ such that $b^\top s\geq c^\top u$. Assuming that the feasible regions of the LPs P and D are nonempty, we know by weak duality that there's an original feasible pair $(x^*,y^*)$ such that the last line holds, meaning that $c^\top x^*\geq b^\top y^*$, and we're done.