[proofplan]
The feasible solution polytope is the convex hull of the incidence vectors of feasible sets. We compare the value of the linear functional $x \mapsto w \cdot x$ on an arbitrary convex combination with the largest value it takes on the incidence vectors. This gives the upper bound for the polytope optimization problem, while the reverse bound follows because every incidence vector belongs to the polytope. Choosing a feasible set with maximum weight then gives an optimal incidence-vector solution.
[/proofplan]
[step:Declare the linear objective and rewrite its value on incidence vectors]
Define the linear functional $L_w: \mathbb{R}^E \to \mathbb{R}$ by
\begin{align*}
L_w(x) := w \cdot x = \sum_{e \in E} w_e x_e.
\end{align*}
For every $S \in \mathcal{F}$, the definition of $\mathbb{1}_S$ gives
\begin{align*}
L_w(\mathbb{1}_S)
=
\sum_{e \in E} w_e(\mathbb{1}_S)_e
=
\sum_{e \in S} w_e.
\end{align*}
Since $\mathcal{F}$ is finite and nonempty, the real number
\begin{align*}
M := \max_{S \in \mathcal{F}} L_w(\mathbb{1}_S)
=
\max_{S \in \mathcal{F}} \sum_{e \in S} w_e
\end{align*}
is well-defined.
[/step]
[step:Bound the value on every convex combination by the best incidence-vector value]
Let $x \in P(\mathcal{F})$. By the definition of convex hull, there exist feasible sets $S_1,\dots,S_m \in \mathcal{F}$ and coefficients $\lambda_1,\dots,\lambda_m \in [0,1]$, for some $m \in \mathbb{N}$, such that
\begin{align*}
\sum_{i=1}^m \lambda_i = 1,
\qquad
x = \sum_{i=1}^m \lambda_i \mathbb{1}_{S_i}.
\end{align*}
Using the linearity of $L_w$,
\begin{align*}
L_w(x)
=
L_w\left(\sum_{i=1}^m \lambda_i \mathbb{1}_{S_i}\right)
=
\sum_{i=1}^m \lambda_i L_w(\mathbb{1}_{S_i}).
\end{align*}
For each $i \in \{1,\dots,m\}$, the definition of $M$ gives $L_w(\mathbb{1}_{S_i}) \le M$. Since every $\lambda_i$ is nonnegative,
\begin{align*}
L_w(x)
=
\sum_{i=1}^m \lambda_i L_w(\mathbb{1}_{S_i})
\le
\sum_{i=1}^m \lambda_i M
=
M.
\end{align*}
Therefore
\begin{align*}
\max\{w \cdot x : x \in P(\mathcal{F})\} \le M.
\end{align*}
[guided]
We take an arbitrary point $x \in P(\mathcal{F})$ because the goal is to control the objective value on the whole polytope. The definition of $P(\mathcal{F})$ as a convex hull means precisely that $x$ can be expressed as a convex combination of incidence vectors: there are feasible sets $S_1,\dots,S_m \in \mathcal{F}$ and coefficients $\lambda_1,\dots,\lambda_m \in [0,1]$, with $m \in \mathbb{N}$, such that
\begin{align*}
\sum_{i=1}^m \lambda_i = 1,
\qquad
x = \sum_{i=1}^m \lambda_i \mathbb{1}_{S_i}.
\end{align*}
The point of introducing this representation is that the objective function is linear. Applying the linearity of the map $L_w: \mathbb{R}^E \to \mathbb{R}$, defined by
\begin{align*}
L_w(y) := \sum_{e \in E} w_e y_e,
\end{align*}
to the displayed convex combination gives
\begin{align*}
L_w(x)
=
L_w\left(\sum_{i=1}^m \lambda_i \mathbb{1}_{S_i}\right)
=
\sum_{i=1}^m \lambda_i L_w(\mathbb{1}_{S_i}).
\end{align*}
Now $M$ was defined as the maximum of $L_w$ over all incidence vectors coming from feasible sets:
\begin{align*}
M := \max_{S \in \mathcal{F}} L_w(\mathbb{1}_S).
\end{align*}
Since every $S_i$ belongs to $\mathcal{F}$, each term satisfies $L_w(\mathbb{1}_{S_i}) \le M$. Because the coefficients $\lambda_i$ are nonnegative, replacing each $L_w(\mathbb{1}_{S_i})$ by the larger number $M$ preserves the inequality:
\begin{align*}
L_w(x)
=
\sum_{i=1}^m \lambda_i L_w(\mathbb{1}_{S_i})
\le
\sum_{i=1}^m \lambda_i M
=
M \sum_{i=1}^m \lambda_i
=
M.
\end{align*}
The last equality uses the defining condition of a convex combination, namely $\sum_{i=1}^m \lambda_i = 1$. Since the chosen point $x \in P(\mathcal{F})$ was arbitrary, every point of the feasible solution polytope has objective value at most $M$. Hence
\begin{align*}
\max\{w \cdot x : x \in P(\mathcal{F})\} \le M.
\end{align*}
[/guided]
[/step]
[step:Use incidence vectors inside the polytope to get the reverse inequality]
For every $S \in \mathcal{F}$, the vector $\mathbb{1}_S$ belongs to $P(\mathcal{F})$ because it is a convex combination with one coefficient equal to $1$. Hence
\begin{align*}
L_w(\mathbb{1}_S) \le \max\{w \cdot x : x \in P(\mathcal{F})\}
\end{align*}
for every $S \in \mathcal{F}$. Taking the maximum over $S \in \mathcal{F}$ gives
\begin{align*}
M \le \max\{w \cdot x : x \in P(\mathcal{F})\}.
\end{align*}
Combining this inequality with the upper bound from the previous step yields
\begin{align*}
\max_{S \in \mathcal{F}} \sum_{e \in S} w_e
=
M
=
\max\{w \cdot x : x \in P(\mathcal{F})\}.
\end{align*}
[/step]
[step:Choose a maximum-weight feasible set to obtain an optimal incidence vector]
Since $\mathcal{F}$ is finite and nonempty, choose $S^* \in \mathcal{F}$ such that
\begin{align*}
L_w(\mathbb{1}_{S^*}) = M.
\end{align*}
Set $x^* := \mathbb{1}_{S^*}$. Then $x^* \in P(\mathcal{F})$, and by the equality just proved,
\begin{align*}
w \cdot x^*
=
L_w(\mathbb{1}_{S^*})
=
M
=
\max\{w \cdot x : x \in P(\mathcal{F})\}.
\end{align*}
Thus the right-hand-side optimization problem has an optimal solution that is the incidence vector of the feasible set $S^*$.
[/step]
