I have a set, $$ X = \{ x_1, x_2, x_3, \dotsc, x_n \}~. $$
The elements $x_i$ from this set are the input to a combinatorial problem I solve with an algorithm. The algorithm returns a solution set, $S \subseteq X$.
However, there are usually more than one potential solutions, i.e., $S_1 \subseteq X$, $S_2 \subseteq X$, and so on, with $S_1 \ne S_2 \ne \cdots \ne S_n$. My algorithm tries to find the optimal solution set. "Optimal" in this case is defined through a weight or distance function, $$ \mathrm{d}(x) \mapsto \mathbb{R}~.$$
This way, I can calculate the total weight/distance of a solution set, and I can also order the elements in $X$ using $$x_i \le x_j \quad\Leftrightarrow\quad \mathrm{d}(x_i) \le \mathrm{d}(x_j)~.$$
So much for the initial definitions.
Now, my algorithm assumes that any solution set that contains the $x$ with the lowest distance value will also be the solution set with the lowest total distance value. Or, put in another way: Any solution set that contains this element with the smallest distance value will have a smaller total distance value than any solution set that does not contain the element with the overall smallest distance value.
Basically, I want to show that, if $x_1$ is the element with the smallest distance value, any $S_i$ with $x_1 \in S_i$ and any other $S_j$ with $x_1 \notin S_j$, $ \mathrm{d}(S_i) \le \mathrm{d}(S_j) $ is always true. Is that possible?
I do not know how to model this assumption, let alone prove that it is true or false. I've tried to model it as a simple example, like this.
Let $X' = \{x_1, x_2, x_3\},\: x_1 \le x_2 \le x_3$. Let $S_1 = \{ x_1 \}$ and $S_2 = \{ x_2, x_3 \}$. From $x_1 \le x_2 \le x_3$ follows that $\mathrm{d}(S_1) \le \mathrm{d}(S_2)$, because $\mathrm{d}(x_1) \le \mathrm{d}(x_2) + \mathrm{d}(x_3)$.
Does that prove my initial assumption that any solution set that contains the smallest element in $X$ will also have the smallest global distance? I fear not, and I fear that I have missed a case, i.e., that this "proof" is not complete. But I do not know how to progress further.
