[proofplan] We first use finiteness to guarantee the existence of at least one optimal feasible solution. Then we prove by induction on the prefix length $k$ that some optimal feasible solution contains the greedy prefix $P_k$. At the final prefix $P_r$, the completion hypothesis forces that optimal feasible solution to equal the greedy output $G$, so $G$ itself is optimal. [/proofplan] [step:Choose an optimal feasible solution to start the induction] Since $E$ is finite, its power set $\mathcal P(E)$ is finite, and hence the subfamily $\mathcal F\subseteq\mathcal P(E)$ is finite. Since $\mathcal F\ne\varnothing$ and $c:\mathcal F\to\mathbb R$ is real-valued, the finite set \begin{align*} c(\mathcal F):=\{c(F):F\in\mathcal F\}\subseteq\mathbb R \end{align*} has a minimum. Define \begin{align*} m:=\min\{c(F):F\in\mathcal F\}. \end{align*} Choose $O_0\in\mathcal F$ such that $c(O_0)=m$. Then $O_0$ is an optimal feasible solution. Since $P_0=\varnothing$, we have $P_0\subseteq O_0$. [guided] The induction needs an optimal feasible solution containing the first prefix. The first prefix is $P_0=\varnothing$, so every feasible set contains it. What remains is to know that an optimal feasible solution exists. Because $E$ is finite, the power set $\mathcal P(E)$ is finite. Since $\mathcal F\subseteq\mathcal P(E)$, the feasible family $\mathcal F$ is finite as well. The hypothesis $\mathcal F\ne\varnothing$ says there is at least one feasible set. Therefore the image \begin{align*} c(\mathcal F):=\{c(F):F\in\mathcal F\} \end{align*} is a nonempty finite subset of $\mathbb R$, so it has a smallest element. Define this smallest value by \begin{align*} m:=\min\{c(F):F\in\mathcal F\}. \end{align*} By the definition of a minimum over a finite nonempty set, there exists $O_0\in\mathcal F$ such that $c(O_0)=m$. This set $O_0$ is optimal. Finally, because $\varnothing\subseteq O_0$, we have $P_0\subseteq O_0$. Thus the induction starts with an optimal feasible solution containing the greedy prefix of length $0$. [/guided] [/step] [step:Propagate optimality through the greedy prefixes] We prove the following assertion for every integer $k$ with $0\le k\le r$: there exists an optimal feasible solution $O_k\in\mathcal F$ such that $P_k\subseteq O_k$. The assertion holds for $k=0$ by the previous step. Now let $k$ be an integer with $0\le k<r$, and assume there exists an optimal feasible solution $O_k\in\mathcal F$ satisfying $P_k\subseteq O_k$. Applying the exchange hypothesis to this integer $k$ and to the optimal feasible solution $O_k$, there exists an optimal feasible solution $O_{k+1}\in\mathcal F$ satisfying $P_{k+1}\subseteq O_{k+1}$. This proves the induction step, and hence the assertion holds for all $0\le k\le r$. [/step] [step:Use completion to identify the final optimal solution with the greedy output] Applying the assertion from the previous step with $k=r$, there exists an optimal feasible solution $O_r\in\mathcal F$ such that \begin{align*} P_r\subseteq O_r. \end{align*} Since $O_r\in\mathcal F$, the completion hypothesis applies to $F=O_r$ and gives $O_r=G$. Because $O_r$ is optimal, this equality gives \begin{align*} c(G)=c(O_r)=\min\{c(F):F\in\mathcal F\}. \end{align*} Therefore the greedy output $G$ is an optimal feasible solution. [/step]