Proof of the Riemann criterion $\textbf{Statement of Theorem:}$ Assume that $g$ is a monotone function. Then $f$ is integrable with respect to $g$ iff for every $\epsilon$ there exists a sufficiently fine partition such that $\sum_i (M_i -m_i)(g(x_i)-g(x_{i-1}) < \epsilon$, where $M_i=\sup\{f(x) \mid x \in [x_{i-1},x_i]\}$ and $m_i=\inf\{f(x) \mid x \in [x_{i-1},x_i]\}$.
My class is using lecture notes which are quite lacking in rigor and intuition. I am looking for some explanation regarding the parts of the proof I have indicated with stars. 
$\textbf{Proof of Theorem:}$ 
$(\Longrightarrow)$ Suppose $f$ is integrable with respect to $g$. Fix $\epsilon > 0$ an choose a partition fine enough for that $\epsilon$. 
$\star$ $\star$ Does there exists many partitions for which $f$ is integrable with respect to $g$? If so, I am assuming we are choosing a particular one of these many partitions. 
Fix selections $\{y_j\}$ and $\{z_j\}$ such that $f(y_j)+\epsilon > M_j$ and $f(z_j)-\epsilon < m_j$. 
$\star$ $\star$ So for each subinterval of our particular partition we are just choosing $y_j$ and $z_j$ such that $f(z_j)$ an $f(y_j)$ are very close to $M_j$ an $m_j$. 
Then
\begin{multline}
\sum_i ( M_i -m_i) (g(x_i)-g(x_{i-1}) \le \\
 \sum_i f(y_i)(g(x_i)-g(x_{i-1})-\sum_i f(z_i)(g(x_i)-g(x_{i-1}) + 2 \epsilon (g(b)-g(a)) \tag1
\end{multline}
Since the first two sums converge to the integral $\int_{a}^{b} f \, dg$, we have the result.
$\star$ $\star$  I can't really prove (1) to myself. First of all, I am not sure why the inequality holds and I don't see how this shows that  $\sum_i ( M_i -m_i) (g(x_i)-g(x_{i-1}) < \epsilon$. Also, where does the fact that $g$ is monotone ever come in to play??
Anyways, I would really appreciate a more detailed proof of this theorem. Links are welcome!
 A: Can you show when $g(x) = x$? It uses the exact same argument.
Let us start from the beginning,
By definition, $f$ is $R$-$S$ integrable w.r.t. $g$ on $[a,b]$ if for each $\epsilon > 0$ there exists a $\delta >0$ such that whenever $a=x_0<x_1<...<x_n = b$ with $\sup_{1\leq i\leq n} |x_{i}-x_{i-1}| \leq \delta$ and for any tag $x^*_i \in [x_{i},x_{i-1}]$ we have
$$\left|\sum_{i=1}^n f(x^*_i)(g(x_i)-g(x_{i-1})) - L\right| \leq \epsilon,$$
we often denote the real number $L =: \int_{[a,b]} f\;dg$.
And here to answer your 3 questions:


*

*Let $\epsilon$ be given (this is not the final $\epsilon$ we are proving in the theorem, you will need to modify it later), we know there exists a partition $P$ such that 
$$\left|\sum_{i=1}^n f(x^*_i)(g(x_i)-g(x_{i-1})) - L\right| \leq {\epsilon},$$
the above inequality holds for ANY tagged point $x^*_i\in [x_{i},x_{i-1}]$.

*Now the idea is  pick two sets of tagged points $\{y^*_i\}$ and $\{z^*_i\}$ so that  $f(y^*_i)$ is close to $M_i$ and $f(z^*_i)$ is close to $m_i$, say $f(y^*_i) + \epsilon \geq M_i$ and $f(z^*_i) - \epsilon \leq m_i$ (again, the $\epsilon$ is not final). Observe that 
$$M_i - m_i \leq f(y^*_i) - f(z^*_i) + 2\epsilon. $$

*From above inequality, we have
$$\sum_{i=1}^n (M_i - m_i) (g(x_i)-g(x_{i-1})) \leq \sum_{i=1}^n (f(y^*_i) - f(z^*_i) + 2\epsilon) (g(x_i)-g(x_{i-1})) $$
rearrange the right hand side, we have
$$\sum_{i=1}^n (M_i - m_i) (g(x_i)-g(x_{i-1})) \leq \sum_{i=1}^n f(y^*_i)(g(x_i)-g(x_{i-1})) - \sum_{i=1}^n  f(z^*_i) (g(x_i)-g(x_{i-1})) + 2\epsilon (g(b)-g(a)).$$
By triangle inequality, the difference of the two sums on the left hand is small 
$$\left|\sum_{i=1}^n f(y^*_i)(g(x_i)-g(x_{i-1})) -L + L-\sum_{i=1}^n  f(z^*_i) (g(x_i)-g(x_{i-1}))\right| \leq 2\epsilon.$$
We now have 
$$\sum_{i=1}^n (M_i - m_i) (g(x_i)-g(x_{i-1})) \leq 2\epsilon  + 2\epsilon (g(b)-g(a))$$
where we can make the left hand side arbitrarily small.
A: 
Does there exists many partitions for which f is integrable with respect to g? If so, I am assuming we are choosing a particular one of these many partitions. 

Yes, if there exists at least one, then any finer partition will also work. The reason we know that such a partition exists is because we are assuming $f$ is integrable with respect to $g$, which you have presumably defined as there existing a partition such that for all finer partitions, the Riemann-Stieltjes sums are at most $\epsilon$ apart. (Or perhaps you've defined it so that for any points chosen within each partition interval, the resulting Riemann-Stieltjes sums differ by at most $\epsilon$ - either way, we get the same thing).

So for each subinterval of our particular partition we are just choosing $y_j$ and $z_j$ such that $f(z_j)$ an $f(y_j)$ are very close to $M_j$ an $m_j$.

Yes, that's right. 

$$\begin{align}
\sum_i ( M_i -m_i) &(g(x_i)-g(x_{i-1}) \le \\
 &\sum_i f(y_i)(g(x_i)-g(x_{i-1})-\sum_i f(z_i)(g(x_i)-g(x_{i-1}) + 2 \epsilon (g(b)-g(a))
\end{align}$$

We'll show this step by step.
$$\begin{align}
\sum_i ( M_i -m_i) (g(x_i)-g(x_{i-1}) &= \sum_i \color{#bb1f1f}M_i (g(x_i) - g(x_{i-1})) - \sum_i \color{#147360}{m_i} (g(x_i) - g(x_{i-1})) \\
&\leq \sum_i \color{#bb1f1f}{(f(y_i) + \epsilon)}(g(x_i)-g(x_{i-1})) - \sum_i \color{#147360}{(f(z_i) - \epsilon)}(g(x_i)-g(x_{i-1})) \\
&= \sum_i f(y_i) (g(x_i) - g(x_{i-1})) - \sum_i f(z_i) (g(x_i) - g(x_{i-1})) + \\
&\quad +\color{#0a4030}{\sum_i 2\epsilon(g(x_i) - g(x_{i-1}))},
\end{align}$$
where the $\color{#0a4030}{\text{last bit}}$ telescopes, as the $g(x_i)$ cancels with the $-g(x_i)$ of the following term, leaving only $2\epsilon (g(b) - g(a))$. 
The $\color{#bb1f1f}{\text{red}}$ and $\color{#147360}{\text{teal}}$ inequalities are almost exactly the inequalities described in the choices of $y_j$ and $z_j$ from the previous step, and the reason we know the direction of the sign overall is because we are (apparently) assuming $g$ is monotone increasing, so that $g(x_i) - g(x_{i-1}) \geq  0$. This last bit is important, as, for example, although $2 < 3$, we don't have that $2(1-2) < 3(1 - 2)$. So that is how we use monotonicity of $g$, and hwo the inequalities follow.
You might ask, what if $g$ is monotone decreasing? First of all, you should then realize that your theorem statement is poorly written, and it almost certainly actually wants $\displaystyle \left\lvert\sum_i (M_i -m_i)(g(x_i)-g(x_{i-1})\right\rvert < \epsilon$. Then the easiest thing to do is to do the proof on $-g$ instead.

I can't really prove (1) to myself. First of all, I am not sure why the inequality holds and I don't see how this shows that $∑_i(M_i−m_i)(g(x_i)−g(x_i−1)<ϵ$. Also, where does the fact that g is monotone ever come in to play?

So almost everything in this point is covered just above, except how this actually shows the desired theorem.
Since $f$ is integrable with respect to $g$, and we chose an $\epsilon$-partition, we know that both $\displaystyle \sum_i f(y_i)(g(x_i)-g(x_{i-1})$ and $\displaystyle \sum_i f(z_i)(g(x_i)-g(x_{i-1})$ are within $\epsilon$ of the value of the integral $I$. So their difference (triangle inequality!) is at most $2 \epsilon$.
Similarly, $g(b) - g(a)$ is just some number, so when multiplied by $2 \epsilon$, we get some constant times $\epsilon$. So the overall size of the final bit is $k \epsilon$ for some constant $k$ independent of $\epsilon$. This can be made arbitrarily small by choosing smaller initial $\epsilon$ values, which is the theorem.
