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.
Best Answer
Yes, this is all correct.
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<x$. 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.
And unlike the second observation, both your first observation and the method of infinite descent it motivates are crucially about well-ordering.