# Confusion in well ordering principle

Well-ordering principle states that every non-empty set of positive integers contains a least element.

I have a set S which is a subset of natural numbers. Now by well-ordering principle I can conclude that S will have a least element in it. I may figure it out or I may not but there is a least element.

Let $$m\in S$$ such that $$m=3n$$ for some $$n \in \mathbb{N}$$, Now I somehow show that if $$3n \in S$$ then $$2n\in S$$.

Now can I conclude that the least element of S is not any multiple of 3?

Now if I somehow show that the least element of S is not of the form say, $$4n$$, $$4n+1$$, $$4n+2$$ and $$4n+3$$ then can I conclude that S is an empty set?

Kindly help me.

• Yes, if $3n\in S$ implies that $2n\in S$, then clearly no multiple of $3$ can be the least element of $S$. And since every positive integer has one of the forms $4n,4n+1,4n+2$, and $4n+3$, if you can show that $S$ contains no element of any of those forms, then $S$ must of course be empty. Apr 30, 2020 at 3:23

The second observation isn't really about well-ordering at all: you're just proving the non-existence of a certain type of object by ruling out all possible cases (in this case, it's supposed to be a natural number but it can't be $$0$$, $$1$$, $$2$$, or $$3$$ mod $$4$$).
The first observation though contains the germ of something deep. Granting your hypotheses, you've correctly shown that the least element of the set can't be a multiple of $$3$$, since given any multiple of $$3$$ that's in the set we can "go down" and find an even smaller number which is also in the set. This is the idea behind infinite descent, which is a well-ordering-based way to prove that a given set is empty: prove that (for $$A$$ a particular set of natural numbers) for every element $$x$$ of $$A$$ there is a $$y\in A$$ with $$y. The well-ordering principle then says that this means $$A=\emptyset$$. Infinite descent is really just induction in disguise: for example, if we want to prove that a certain property $$P$$ holds of every natural number, we can try to use infinite descent to show that the set of natural numbers which don't have property $$P$$ is empty.