# Proof Verification: Prove the well-ordering principle

I tried to prove the well-ordering principle but I’m not sure whether or not it’s rigorous or even valid. Feedback would be greatly appreciated:

Let S be a nonempty set of positive integers. S is bounded below by 0 and therefore, $$\inf S$$ exists.

But we know that for any $$\phi > \inf S$$, there must exist some “a” such that $$a \in S$$ and $$a < \phi$$

Let $$\phi = \inf S + \varepsilon$$ where $$\varepsilon > 0$$

$$a < \inf S + \varepsilon$$ but since $$a \in S$$ $$a \geq \inf S$$

And I ended up with the inequality, $$\inf S \leq a < \inf S + \varepsilon$$ (1)

Meaning there must exist some element $$a \in S$$ that satisfies the inequality.

if $$\inf S \notin Z^{+}$$, there exists $$\varepsilon$$ such that no element of S could satisfy the inequality:

set $$\varepsilon = k - \inf S$$, where k is a positive integer. $$\inf S = k - \varepsilon$$ Plugging that into (1) $$k - \varepsilon \leq a < k$$ For $$0 < \varepsilon < 1$$, there exists no integer a that satisfies the inequality which is a contradiction. Thus, $$\inf S \in Z^{+}$$ (2) By definition, $$\inf S \geq 0$$, since $$0$$ is a lower bound of S (3)

From (2) and (3), $$\inf S \in S$$ which means that $$min S$$ exists.

EDIT: I replaced $$\frac{1}{n}$$ with $$\varepsilon$$ to generalize the problem further without making the assumption that $$\varepsilon$$ is rational and also because $$\frac{1}{n}$$ basically served no purpose.

EDIT 2: I was advised against defining the set to make the proof more general.

• Um... it seem to me you are only considering sets of the form $\{\sigma, \sigma + 1, \sigma + 2,...\}$. You need to prove it for all sets of natural numbers. But about the set $\{27,39, 45\}$ or $\{2,4,8,16,....\}$ or infinite sets with no pattern or the set of all numbers so that $n^2 \equiv 3 \pmod 7$. Commented Oct 5, 2020 at 18:36
• For the sets you've stated $\sigma$ is a lower bound, and $\sigma \in S$ so $\min S = \sigma$. QED. But we need to show that any possible set of natural numbers always has a lowest elements. That's a different kettle of fish. Commented Oct 5, 2020 at 18:41
• @Blue I agree with you, but you've proved, as fleablood mentioned, the property only for $\{\sigma, \sigma + 1, \sigma + 2,...\}$. Commented Oct 5, 2020 at 18:41
• @fleablood I don’t think this proof assumes the set is inductive. I’m pretty sure the existence of $a \in S$ such that a < x is true for any set so long as $x > inf S$ Commented Oct 5, 2020 at 18:41
• @fleablood How do you know $\sigma \in S$? I never assumed that, sigma was an arbitrary real number. I could have set \sigma = 0 which would be redundant. EDIT: Oh sorry, I see the mistake. But still, \sigma could be an arbitrary positive real number. Commented Oct 5, 2020 at 18:44

You seem to want to prove the well-ordering of the natural numbers from the completeness of the reals. OK, although this looks like a petitio principii.

Let $$S$$ be a nonempty set of natural numbers. It is certainly bounded below by $$0$$, so it has an infimum $$a$$.

You want to prove that $$a$$ is actually the minimum of $$S$$. By the properties of the infimum, there exists $$s\in S$$ such that $$a\le s.

If $$a\notin S$$, then $$a, so there exists $$t\in S$$ such that $$a. However, this is a contradiction, because $$s-a>s-t\ge1$$, whereas $$s-a<1/2$$.

Basically, we can choose an interval starting from the infimum that can contain no more than one natural numbers. Because of the properties of the infimum, such interval must contain one natural number, but if the infimum is not the minimum, each interval starting from it must contain infinitely many members of the set. Now you have to prove the lemma: the difference between two distinct natural numbers is at least $$1$$.

This requires induction, but not the full strength of the well-ordering principle.

• wait, how is my argument circular? Isn’t the existence of inf S directly deduced from the existence of Sup S which is in and of itself a axiom? And thanks for your proof. Commented Oct 5, 2020 at 22:08
• @Blue Of course it depends on how you introduce the real numbers. If you want to construct them, then you have to use the well-ordering of the natural numbers. In any case, some (weak) form of induction is needed. Commented Oct 5, 2020 at 22:18
• I tried avoiding induction because I felt like using a “base case” is somewhat circular, since you are already implying the existence of a smallest element by using a base case. Commented Oct 5, 2020 at 22:19
• @Blue I disagree. Peano arithmetic (first order logic) is essential anyway, if you want to talk about numbers in a sensible way. The lemma I mention is needed (in my argument and also in yours). Commented Oct 5, 2020 at 22:22
• Also, can’t I prove that there exists no integer a that satisfies the inequality $k < a < k+1$ for k being an integer, and claim k-1 < k - epsilon, which would make the final equation k -1 < a < k. Hence a is not an integer. Commented Oct 5, 2020 at 22:24

I advise NOT defining $$S$$ as $$S$$ can be any set of natural numbers. (not just $$S = \{k,k+1,k+2,....\}$$.

As $$0$$ is a lower bound of $$S$$ then $$\inf S$$ exists.

If $$\inf S\in S$$ we are done. $$\min S = \inf S$$ as 1) $$\inf S \in S$$ and 2) $$\inf S \le x$$ for all $$x \in S$$.

If $$\inf S \not \in S$$ then that actually disproves the well ordering principle. Because for any $$a \in S$$ then $$a > \inf S$$. So $$a$$ is not a lower bound so there is an $$a'\in S$$ so that $$\inf S < a' < a$$ and no $$a\in S$$ can be $$\min S$$.

So we it suffices to prove that $$\inf S\in S$$ for any set of natural numbers.

Consider $$1 > 0$$. Then $$\inf S+ 1$$ is not a lower bound. So there is an $$a \in S$$ so that $$\inf S \le a < \inf S+1$$. If $$a = \inf S$$ then we are done. $$\inf S =a \in S$$.

If $$a \ne \inf S$$ then $$a$$ is not a lower bound. So there is an $$a'\in S$$ so that $$\inf S\le a' < a< \inf S+1$$. But that means $$1 > a-a' >0$$. But as $$a,a'$$ are natural numbers $$a-a'$$ is an integer and there is no integer between $$0$$ and $$1$$.

So $$a =\inf S$$ and $$\inf S \in S$$ and $$\inf S = \min S$$ and the well-ordered principle is proven.

• My purpose with the proof was to consider all cases, not just when S is inductive. I assumed $inf S /notin S$ for the sake of contradiction, then I showed that inf S /in S to avoid said contradiction. I think the way my proof went is somewhat analogous to yours, but yours is more rigorous. Anyhow, thanks for the help. Greatly appreciated. Commented Oct 5, 2020 at 19:04
• I don't know what you mean by $S$ being inductive. But considering $S=\{x \in \mathbb Z^+| x \ge \sigma\}$ is to assume $S$ is the set of all naturals larger than or equal to $\sigma$. that is not an arbitrary set and not a useful general set. Commented Oct 5, 2020 at 20:14
• if you assume sigma = 1 then it includes all the naturals, anyhow, I see the mistake I made now. By assuming such sigma exists, any number greater than said sigma is included thus making the set {\sigma, \sigma + 1, \sigma + 2....}. Now I fixed it, since sigma served no purpose anyway. Thanks for your help. By inductive, I’m referring to any set where if k is in the set, k+1 must be too. My set was at first inductive but now the proof is generalized, thanks. Commented Oct 5, 2020 at 22:00