# Well Ordering Principle Proof without mathematical induction with different approach

Denote $$\Bbb Z_0$$ be the set of all non-negative integers.

Well Ordering Principle for $$\Bbb Z_0$$. Every non-empty subset $$S$$ of $$\Bbb Z_0$$ has a least element; that is, there exists $$m \in S$$ such that $$m \le s$$ for all $$s \in S$$.

Note: $$0$$ is a least element of $$\Bbb Z_0$$.

Proof: Let $$\emptyset \ne S \subseteq \Bbb Z_0$$ be arbitrary given. Let $$k$$ be an element of $$S$$. Then $$k$$ is a non-negative number. Define a subset $$T$$ of $$S$$ by $$T=\{x \in S \mid x \le k\}$$. Then $$T \ne \emptyset$$ and $$T \subseteq \{0,1,2,\ldots,k\}$$. Clearly, $$T$$ is a finite subset of $$\Bbb Z_0$$ and therefore it has a least element, say $$m$$. Then $$0 \le m \le k$$. Now, we must to show that $$m$$ is the least element of $$S$$. Indeed, let $$s$$ be any element of $$S$$. If $$s>k$$, then the inequality $$m \le k$$ implies $$m. If $$s \le k$$, then $$s \in T$$. Since $$m$$ being the least element of $$T$$, then $$m \le s$$. Hence, $$m$$ is the least element of $$S$$. This completes the proof. $$\qquad \square$$

Does this correct? I'm had a little bit confusing on the sentence "therefore it has a least element, say $$m$$". It seems obviously true, but I couldn't to prove it yet. Any ideas? Thanks in advanced.

• Commented Mar 29, 2023 at 14:07
• Commented Mar 29, 2023 at 14:10
• Does this answer your question? How do you prove Well-Ordering without Mathematical Induction? (and vice-versa) It gives a simpler proof (based on the same tool: induction) than the answer below. Commented Mar 29, 2023 at 14:17
• Unfortunately, they are not answer my question. So, why closed??? Commented Mar 29, 2023 at 14:58

That sentence is true, but it does need proof, and I would say one proves it by induction on $$k$$. So you don't get a free ride here, induction has to come in somewhere.

We must prove that for all $$k \in \mathbb Z_0$$, every nonempty subset of $$\{0,...,k\}$$ has a least element.

Basis step: if $$k=0$$ and $$T \subseteq \{0\}$$ is a nonempty subset, then $$T = \{0\}$$ and therefore $$0$$ is the least element of $$T$$.

Inductive step: suppose that every nonempty subset of $$\{0,...,k-1\}$$ has a least element. Now let $$T \subset \{0,...,k-1,k\}$$ be a nonempty subset. To prove that $$T$$ has a least element there are two cases.

Case 1: If the intersection $$T \cap \{0,...,k-1\}$$ is nonempty then by induction it has a least element $$j$$. It follows that $$j$$ is also the least element of $$T$$, because the only other possible element of $$T$$ is $$k$$ but $$j < k$$.

Case 2: If $$T \cap \{0,...,k-1\}$$ is empty then $$T=\{k\}$$ and so $$k$$ is its least element.

• Here are direct proofs that (on natural numbers) induction $\implies$ well ordering. Without introducing $k$ and $T$ like the OP did. I think it might be considered as a duplicate. Commented Mar 29, 2023 at 14:15
• Any method without using induction? Like contradiction? Commented Mar 29, 2023 at 14:57
• I mean, suppose that $T$ do not have a least element. Then, for any $t \in T$, there is an $s \in T$ such that $t>s$. But, $s < t \le n$. I got stucked here. Commented Mar 29, 2023 at 15:33
• Since you were stuck, I showed you how how to make your method work by using induction. There are other proofs that use induction by other methods, for example at the link provided by @AnneBauval. But no, you cannot avoid induction on this problem. Commented Mar 29, 2023 at 16:22