Joshua Zucker writes:

Is this based on the assumption that 1 is the smallest positive integer, which is what you said you needed as an additional assumption? This step seems like the key to the proof.

If there were an integer y strictly between x-1 and x, where x is an integer, then x-y would be a positive integer less than 1.

But x-1 might not be positive? Hm, some details to worry about.

Oops. This uncovers another error in my write-up. Every induction needs a base case! Putting it differently: My earlier write-up never used the assumption that S contains 1, so you can tell it isn't quite right. But I'm fairly sure all the bugs have been fixed now.

Induction is equivalent to the statement that any set of positive integers has a least element. So all you need is the part that establishes that the greatest lower bound of E is itself in E, right? You don't even need the set S at all.

Good point!

But wait a minute. How do you know that for any x that is not an integer, you can find x' > x with no integers between x and x'? This seems also equivalent to what you're trying to prove. (I'm imagining counterexamples of the form "all fractions with denominator a power of 2".)

This isn't hard. There is at most one integer between x and x+1 because if there were two of them, say y and z with y < z, then z-y would be positive integer less than 1. (In fact there's exactly one integer between x and x+1, but say we don't know this yet.) If there are no integers between x and x+1, take x' = x+1 (or take x+1/2 if you prefer). On the other hand, if there is an integer n between x and x+1, take x' = n (or (x+n)/2 if you prefer). Either way, there are no integers between x and x'. I guess what surprises me is that you don't need any second-order assumptions to get from the completeness of the reals to the least element principle --- just the first-order assumption that every positive integer is greater than or equal to 1. Jim Propp