1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Apr 30, 2020 at 3:23

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.