The Student Room Group

Well ordering principle

So every non empty subset of the natural numbers has a least element.

every non empty subset of the integers has a least element if it is bounded below - i.e if there exists an integer which is less than or equal to all elements in the subset.

So firstly when can you not apply the well ordering principle to the rational numbers? i believe this is because this set is not bounded below.

But what about the positive rationals this set is bounded below, why can you not apply the well ordering principle here? Is it because the lower bound does not actually belong to the subset? say you have p/q you can keep going smaller p/2q and so on.

What about the positive reals. This set is bounded below but is it that you ant apply it because once again any lower bound is not included in the set?

And finally what about the non-negative reals. Can you apply WOP here? this set is bounded below and there exists a lower bound (0) which is ean element of the set which identifies it as the least element. Thanks in advance :smile:
Original post by hitherematey1
So every non empty subset of the natural numbers has a least element.


Correct. This is what is usually called the well-ordering principle or theorem.


every non empty subset of the integers has a least element if it is bounded below - i.e if there exists an integer which is less than or equal to all elements in the subset.


Correct


So firstly when can you not apply the well ordering principle to the rational numbers? i believe this is because this set is not bounded below.


Bit of terminology here - the well-ordering principle is a theorem about the natural numbers. What you are now asking about (I think) is whether the rationals (or a subset of the rationals) is well-ordered in its natural order.

With this distinction, your observation is correct, the rationals are not well-ordered in their natural order, as there is no lower bound.


But what about the positive rationals this set is bounded below, why can you not apply the well ordering principle here? Is it because the lower bound does not actually belong to the subset? say you have p/q you can keep going smaller p/2q and so on.


You can't apply the well-ordering principle, as that is a theorem about the natural numbers and does not apply to the rationals. But your reasoning is correct; you can always find a smaller strictly positive rational number less than a given strictly positive rational number.


What about the positive reals. This set is bounded below but is it that you ant apply it because once again any lower bound is not included in the set?


Same.


And finally what about the non-negative reals. Can you apply WOP here? this set is bounded below and there exists a lower bound (0) which is ean element of the set which identifies it as the least element. Thanks in advance :smile:


No. The positive reals (including zero) do have a minimal element; but for an ordering to be a well-order, every subset of the set your concerned with must have a minimal element. This clearly fails for the positive reals.
Original post by Gregorius
Correct. This is what is usually called the well-ordering principle or theorem.



Correct



Bit of terminology here - the well-ordering principle is a theorem about the natural numbers. What you are now asking about (I think) is whether the rationals (or a subset of the rationals) is well-ordered in its natural order.

With this distinction, your observation is correct, the rationals are not well-ordered in their natural order, as there is no lower bound.



You can't apply the well-ordering principle, as that is a theorem about the natural numbers and does not apply to the rationals. But your reasoning is correct; you can always find a smaller strictly positive rational number less than a given strictly positive rational number.



Same.



No. The positive reals (including zero) do have a minimal element; but for an ordering to be a well-order, every subset of the set your concerned with must have a minimal element. This clearly fails for the positive reals.

thank you thats alot clearer now
If you assume the Axiom of Choice under Zermelo–Fraenkel set theory (ZFC), every set has a well-ordering. Even the reals.

What this statement means is that there exists some ordering of the reals for which a well ordering exists. This allows us to conclude that there exists an ordering of the reals such that every subset of the reals has a least element.

The problem is, we don't actually know what this well ordering is (it may not even be possible to find one, see here for a bit of off-topic discussion on this: https://math.stackexchange.com/questions/6501/is-there-a-known-well-ordering-of-the-reals)

We do, however, know that the standard ordering of the reals is definitely not a well ordering. You discovered this yourself:

"But what about the positive rationals this set is bounded below, why can you not apply the well ordering principle here? Is it because the lower bound does not actually belong to the subset? say you have p/q you can keep going smaller p/2q and so on."

So, to summarise, the standard ordering isn't a well ordering, but there does exist another ordering (which nobody has been able to find despite much trying) which does produce a well ordering on the reals, if we assume the Axiom of Choice.

Finally - look up Zorn's Lemma. It's equivalent to the Axiom of Choice and is more practically helpful (although not easy to state).
Original post by Gregorius
Correct. This is what is usually called the well-ordering principle or theorem.



Correct



Bit of terminology here - the well-ordering principle is a theorem about the natural numbers. What you are now asking about (I think) is whether the rationals (or a subset of the rationals) is well-ordered in its natural order.

With this distinction, your observation is correct, the rationals are not well-ordered in their natural order, as there is no lower bound.



You can't apply the well-ordering principle, as that is a theorem about the natural numbers and does not apply to the rationals. But your reasoning is correct; you can always find a smaller strictly positive rational number less than a given strictly positive rational number.



Same.



No. The positive reals (including zero) do have a minimal element; but for an ordering to be a well-order, every subset of the set your concerned with must have a minimal element. This clearly fails for the positive reals.

So the set of rational numbers greater than 0 has a lower bound but is not well ordered. However a set like rational numbers greater than or equal to 1/2 is bounded below and has a least element (1/2). so is well ordered
Original post by hitherematey1
So the set of rational numbers greater than 0 has a lower bound but is not well ordered. However a set like rational numbers greater than or equal to 1/2 is bounded below and has a least element (1/2). so is well ordered

Actually is it that both sets are not well ordered but just that the second has a least element
Original post by hitherematey1
Actually is it that both sets are not well ordered but just that the second has a least element


This is not correct. Under ZFC both sets are well ordered. See my post above for more details.
Original post by hitherematey1
Actually is it that both sets are not well ordered but just that the second has a least element


Yes, this is correct; but you should also say "with respect to its natural order" somewhere. A "well-order" on any set refers to the particular order under consideration.
Original post by President Snow
This is not correct. Under ZFC both sets are well ordered. See my post above for more details.


No, not quite. "well ordering" refers to the particular ordering of the set in question. So the subsets of the rationals mentioned by OP, in their natural ordering, are not well-ordered sets.

However, if you assume the axiom of choice, for any set S, you can assume that there is a total order on S (< ) such that the pair (S, < ) is a well-order.
(edited 5 years ago)

Quick Reply

Latest