# Well ordering principle

Watch
Announcements
#1
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
0
2 years ago
#2
(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
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.
3
#3
(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
0
2 years ago
#4
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/quest...g-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).
0
#5
(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
0
#6
(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
0
2 years ago
#7
(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.
0
2 years ago
#8
(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.
0
2 years ago
#9
(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.
Last edited by Gregorius; 2 years ago
1
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Should there be a new university admissions system that ditches predicted grades?

No, I think predicted grades should still be used to make offers (627)
33.66%
Yes, I like the idea of applying to uni after I received my grades (PQA) (784)
42.08%
Yes, I like the idea of receiving offers only after I receive my grades (PQO) (368)
19.75%
I think there is a better option than the ones suggested (let us know in the thread!) (84)
4.51%