Suppose that I have k envelopes, numbered $0,1,...,k−1$, such that envelope i contains $2^i$ dollars. Using the well-ordering principle, prove the following claim.
Claim: for any integer $0 ≤ n < 2^k$, there is a set of envelopes that contain exactly n dollars between them.
How would I tackle this problem? I am stumped. I know that the well-ordering principle states that a non-empty set will always have a smallest element in the set, but I don't exactly know how to apply it to write the proof.
Call the positive integer $k$ bad if there is a set of $k$ envelopes, numbered $0$ to $k-1$, with contents as described in the question, and an integer $n\lt 2^k$, such that no subset of the envelopes contains exactly $n$ dollars between them.
We want to prove there are no bad $k$. Suppose to the contrary that there are. Then the set $B$ of bad $k$ is non-empty. It follows that there is a smallest bad $k$. Call it $m$.
$m$ is greater than $0$, because $m=0$ holds obviously.
So $m$ is bad, and all positive integers $\lt m$ are good.
We arrive at a contradiction by showing that $m$ is good, that is, that any number $n\lt 2^m$ of dollars can be obtained by choosing an appropriate collection of the envelopes.
Case (i), $n\lt 2^{m-1}$: Since $m-1$ is good, there is a subset of the first $m-1$ envelopes that gives sum $n$.
Case (ii), $2^{m-1}\le n\lt 2^m$. Take the contents of the biggest envelope, that is, envelope with label $m-1$, which has $2^{m-1}$ dollars.
Then we still need an amount $a$ of dollars, where $0=2^{m-1}-2^{m-1}\le a\lt 2^m-2^{m-1}=2^{m-1}$. Because $m-1$ is good, we can produce this amount $a$ from the first $m-1$ envelopes. Hence by adding the contents of the envelope with label $m-1$, we get our $n$ dollars.
Remark: This is just an ordinary proof by induction, rewritten to use "well-ordering principle" language.
Let $S$ denote the values in $\{0,1,2,\ldots, 2^k-1\}$ that cannot be expressed with the envelopes. $0$ is not in $S$, because "no envelopes" has zero dollars. $S$ is well-ordered because it is a subset of the naturals; if it is nonempty it has a smallest element $s$. Hence $0,1,2,\ldots, s-1$ can all be expressed with combinations of envelopes, but $s$ cannot be. You need to use the combination of these two facts to get a contradiction; hence $S$ is empty and your theorem is proved.
If you need a hint for how to get that contradiction, let me know.
This should be easy to prove by mathematical induction, and in turn you can use the well-ordering principle to prove the principle of induction. This is somewhat odd, as I believe generally the principle of induction is taken as fundamental and the well-ordering principle is proved from it, but the two are logically equivalent.
Let S denote the values in $\{0,1,2,…,2k−1\}$ that cannot be expressed with the envelopes. $0$ is not in $S$, because "no envelopes" has zero dollars. $S$ is well-ordered because it is a subset of the naturals; if it is nonempty it has a smallest element $s$. Hence $0,1,2,…,s−1$ can all be expressed with combinations of envelopes, but s cannot be. You need to use the combination of these two facts to get a contradiction; hence $S$ is empty and your theorem is proved.
If you need a hint for how to get that contradiction, let me know.
How do I get to a contradiction?
