Reaching approximate agreement in the presence of faults

\begin{lemma}
Suppose that $V$ and $W$ are non-empty multisets. Then
\begin{enumerate}
  \item $|V \cap W| - |s(V) \cap s(W)| \le 1$
  \item $|V \cap W| - |l(V) \cap l(W)| \le 1$
\end{enumerate}
\end{lemma}
\begin{proof}
  Let $s_{v}$ and $s_{w}$ be the elements that are removed from the multisets $V$ and $W$ respectively to obtain $s(V)$ and $s(W)$.
  If $s_{v} = s_{w}$, then this element belongs to both $V$ and $W$. Thus, it is present in $V\cap W$. Since they are the minimums in both sets, the only element missing in $s(V)\cap s(W)$ is $s_{v}$. As a result, $|V \cap W| = |s(V) \cap s(W)| + 1$.
  Else, then both elements $s_{v}$ and $s_{w}$ do not belong to $V \cap W$. Thus, $|V\cap W| = |s(V) \cap s(W)|$.
  The proof for (2) is similar.
\end{proof}

\begin{lemma}
Suppose that $j$ is a non-negative integer and that $V$ and $W$ are multisets such that $|V| \ge 2j$ and $|W| \ge 2j$. Then
\[ V \cap W - |reduce^{j}(V)\cap reduce^{j}(W)| \le 2j\]
\end{lemma}
\begin{proof}
  Applying Lemma 1 once results in $|V \cap W| - | s(V) \cap s(W)| \le 1$ or $|V \cap W| \le |s(V)\cap s(W)| + 1$. Applying it again, results in $|V \cap W| \le |s(V) \cap s(W)| \le |l(s(V)) \cap l(s(w))| + 2$ or $|V\cap W|\le |reduce(V) \cap reduce(W)| + 2$.
  Applying this iteratively for $i in 1,\ldots,j$, we get the statement in the lemma.
\end{proof}

\begin{lemma}
Suppose that $j$ is a non-negative integer and that $U$ and $V$ are non-empty multisets such that $|V-U|\le j$ and $|V|\ge 2j$. Then $\rho(reduce^{j}(V))\subseteq \rho(U)$.
\end{lemma}
\begin{proof}
Suppose $\rho(reduce^{j}(V))\not\subseteq \rho(U)$.
Then either $min(reduce^{j}(V))<min(U)$ or $max(reduce^j(V))>max(U)$.
If $min(reduce^j(V)) < min(U)$, then $\Sigma\limits_{r<min(U)}V(r) \ge j+1$.
Hence, $|V-U| \ge j+1$, which contradicts the hypothesis.
The other case can also be similarly shown to contradict the hypothesis.
\end{proof}