# Supremum of a set, relations and order

• I
• lys04
lys04
TL;DR Summary
prove that a supremum for a set doesn't exist; relations, total order and partial order
Hello, found this proof online, I was wondering why they defined r_2=r_1-(r_1^2-2)/(r_1+2)? i understand the numerator, because if i did r_1^2-4 then there might be a chance that this becomes negative. But for the denominator, instead of plus 2, can i do plus 10 as well? or some other number thats positive

I also did some reading on Cartesian product, relations, total order and partial order.
So a Cartesian product AxB is just ordered pair (a,b) where a is an element of A and b is an element of B right.
And a relation is just a subset of the Cartesian product.
Now total and partial orders.
Total order is denoted by < and partial order is denoted by <=? I’m a bit unsure about these, please correct me if I’m wrong.
And a total order relation requires four things:
Reflexive, anti-symmetric, transitive and comparability? I’m a bit unsure what comparability is though.
And for partial order relation I think it just needs to be reflexive, anti-symmetric and transitive?

That proof looks wrong to me. Did you get it from a reliable source?

It was from another physics forum post

PeroK
lys04 said:
It was from another physics forum post
Wrong because for the first line they said r is upper bound if and only if r^2>2? but r could be -3?

lys04 said:
Wrong because for the first line they said r is upper bound if and only if r^2>2? but r could be -3?
We have a set:
$$S = \{x\in \mathbb Q: x^2 < 2\}$$Let ##r## be an upper bound for ##S##. Note that ##1 \in S##, so ##r \ge 1##. That disproves your assertion that ##r## could be ##-3##.

Also, the initial conclusion in the post is wrong. We cannot conclude immediately that ##r^2 \ge 2##.

lys04 said:
Yes I know, I was referring to the original post where they concluded that r is an upper bound if and only if r^2>2, and r^2 for r=-3 is greater than 2, but it's definitely not an upper bound.

The original post is from here: https://www.physicsforums.com/threads/rational-numbers-supremum-is-my-proof-correct.866903/
The first step doesn't work, because there might be a rational ##q## with ##q^2 < 2##, which is an upper bound for ##S##. You definitely need to prove that can't happen before you go any further.

And, yes, the second line also has the error that you have to exclude negative rationals.

It's probably best to ignore that thread.

I think there is a simpler and better proof in any case. I would start with:

Let ##q = \frac m n## be an upper bound for ##S##. Then find a contradiction.

PS: you could also patch up that proof.

Last edited:
PeroK said:
Let q=mn be an upper bound for S. Then find a contradiction.
I'm not sure how I'm meant to find a contradiction for this. As in q=m/n is not an upper bound?
Could I do this instead? Let q=m/n be an upper bound. Then q=m/n >=sqrt(2)
But there is no q in Q that is equal to sqrt(2) since its irrational. so q=m/n >sqrt(2) for it to be an upper bound.
Then using Archimedean principle, that for every epsilon>0 (Take this to be the distance between q and sqrt(2), this is an irrational number since the sum of any rational with irrational is still irrational), there is always an integer N st 1/N<epsilon. (1/N will be rational)
what ever q is, since its greater than sqrt(2), and epsilon, the distance between q and sqrt(2) is irrational, and 1/N is less than that, I can always make q closer and closer to sqrt(2) but never reaching it, so supremum doesn't exist?

lys04 said:
I'm not sure how I'm meant to find a contradiction for this. As in q=m/n is not an upper bound?
Could I do this instead? Let q=m/n be an upper bound. Then q=m/n >=sqrt(2)
This assumption is what is wrong with the above proof!!!

We know that ##q^2 \ne 2##, so we have to cover both cases where ##q^2 < 2## and ##q^2 > 2##. You cannot rule out either of these cases.

The rest of that proof looks correct and can be adapted to cover the case ##q < 2##.

Here's an alternative idea if you want something different.

Suppose ##s\in \mathbb Q## is the supremum for ##S## with ##s^2 < 2##. For ##n \in \mathbb N##, consider ##q_n = s + \frac 1 n##. As ##q_n > s##, ##q_n \notin S##, hence ##q_n^2 > 2##. So, we have, ##\forall n \in \mathbb N##:
$$s^2 < 2 < (s + \frac 1 n)^2 = s^2 + \frac{2s}{n} + \frac 1 {n^2}$$Hence, ##\forall n \in \mathbb N##:$$0 < 2 - s^2 < \frac{2s}{n} + \frac 1 {n^2}$$From that you can try to find a positive rational which is less than ##\frac 1 n## for every ##n##.

Then, use a similar argument if ##s^2 > 2##.

PeroK said:
This assumption is what is wrong with the above proof!!!

We know that ##q^2 \ne 2##, so we have to cover both cases where ##q^2 < 2## and ##q^2 > 2##. You cannot rule out either of these cases.

The rest of that proof looks correct and can be adapted to cover the case ##q < 2##.
q<sqrt(2) cannot be an upper bound based on the definition of the set though, because again q is rational here, and using Archimedean Principle the distance between q<sqrt(2) and sqrt(2) is irrational, so I can always find a bigger number that is in the set?

lys04 said:
q<sqrt(2) cannot be an upper bound based on the definition of the set though,
Why not? If ##S## were a subset of the integers, then the supremum would be ##1##. Why can't there be a greatest rational in the set ##S##? That's what you have to prove.

PeroK said:
Why not? If ##S## were a subset of the integers, then the supremum would be ##1##. Why can't there be a greatest rational in the set ##S##? That's what you have to prove.
So there is no q in Q that is equal to sqrt(2) since its irrational.
For q>sqrt(2) I can do this:
q=m/n >sqrt(2) for it to be an upper bound.
Then using Archimedean principle, that for every epsilon>0 (Take this to be the distance between q and sqrt(2), this is an irrational number since the sum of any rational with irrational is still irrational), there is always an integer N st 1/N<epsilon. (1/N will be rational)
what ever q is, since its greater than sqrt(2), and epsilon, the distance between q and sqrt(2) is irrational, and 1/N is less than that, I can always make q closer and closer to sqrt(2) but never reaching it, so supremum doesn't exist.
And for q=a/b<sqrt(2):
Again q is rational here so distance between q<sqrt(2) and sqrt(2) is irrational, and using Archimedean Principle I can always find a bigger number that is in the set?

lys04 said:
So there is no q in Q that is equal to sqrt(2) since its irrational.
For q>sqrt(2) I can do this:
q=m/n >sqrt(2) for it to be an upper bound.
Then using Archimedean principle, that for every epsilon>0 (Take this to be the distance between q and sqrt(2), this is an irrational number since the sum of any rational with irrational is still irrational), there is always an integer N st 1/N<epsilon. (1/N will be rational)
what ever q is, since its greater than sqrt(2), and epsilon, the distance between q and sqrt(2) is irrational, and 1/N is less than that, I can always make q closer and closer to sqrt(2) but never reaching it, so supremum doesn't exist.
And for q=a/b<sqrt(2):
Again q is rational here so distance between q<sqrt(2) and sqrt(2) is irrational, and using Archimedean Principle I can always find a bigger number that is in the set?
You have to write this up more formally. Also, it's better not to use the properties of real numbers, as this sort of proof is part of developing the real numbers. Note that I haven't use the number ##\sqrt 2## at all. Nor did the original proof you quoted.

All we know is that there is no member of ##\mathbb Q## which squares to ##2##. That's a more precise statement at this stage than to say that "##\sqrt 2## is irrational".

PeroK said:
You have to write this up more formally. Also, it's better not to use the properties of real numbers, as this sort of proof is part of developing the real numbers. Note that I haven't use the number ##\sqrt 2## at all. Nor did the original proof you quoted.

All we know is that there is no member of ##\mathbb Q## which squares to ##2##. That's a more precise statement at this stage than to say that "##\sqrt 2## is irrational".
Sorry for the late reply. I was looking through my universitys notes and this is what they did, although it’s kind of a different example. Is this kind of similar to what I did?

#### Attachments

• IMG_0184.jpeg
35.8 KB · Views: 9
• IMG_0183.jpeg
23.7 KB · Views: 11
lys04 said:
Sorry for the late reply. I was looking through my universitys notes and this is what they did, although it’s kind of a different example. Is this kind of similar to what I did?
The proof is much easier if you have developed the real numbers and can use the properties of real numbers. That's what these notes have done. That is not a proof from first principles. If you just developed the rationals from the naturals, then you don't have the power of real analysis at your disposal. And irrational numbers, such as ##\sqrt 2## simply do not exist within the mathematics you have so far developed.

In the PF thread you originally quoted, the student has a proof that relies only on the properties of rational numbers. That proof is not perfect, but it is a good attempt at a proof from first principles.

properties of the rational numbers as in the distance d is irrational? (They used the fact that the difference between a rational and an irrational number is also irrational?) So does first principle refer to only using properties of the rational numbers?
I had a read over your proof for this problem, I'm a bit confused to as what's happening. I understand the algebra but I don't know whats the logic behind it

lys04 said:
properties of the rational numbers as in the distance d is irrational? (They used the fact that the difference between a rational and an irrational number is also irrational?) So does first principle refer to only using properties of the rational numbers?
Yes. There are maths courses where this is the idea. To develop the rational numbers first and then develop the real numbers.
lys04 said:
I had a read over your proof for this problem, I'm a bit confused to as what's happening. I understand the algebra but I don't know whats the logic behind it
The logic is that:

a) We know that there is no positive rational number that is less than ##\frac 1 n## for every ##n \in \mathbb N##.

b) If ##q## is the greatest rational with ##q^2 < 2##, then for every ##n##, we have ##(q + \frac 1 n)^2 > 2##. And, after some algebra, this can be shown to contradict a).

c) If ##q## is the least rational with ##q^2 > 2##, then for every ##n##, we have ##(q - \frac 1 n)^2 < 2##. And, again, this can be shown to contradict a).

PeroK said:
a) We know that there is no positive rational number that is less than 1n for every n∈mathbbN.
Is this an assumption for contradiction?

lys04 said:
Is this an assumption for contradiction?
It's something that can be proved quite easily.

May I ask why you are asking these questions? Are you studying mathematics?

PeroK said:
It's something that can be proved quite easily.

May I ask why you are asking these questions? Are you studying mathematics?
yes

lys04 said:
yes
Okay, but it seems this thread has got into a loop where I post something and you ask questions about what I've written. And this loop seems to have little chance of terminating!

You have at least three proofs of this now, two from first principles and one using real numbers. You have to decide whether you want to focus on this last one - from your textbook.

PeroK said:
Okay, but it seems this thread has got into a loop where I post something and you ask questions about what I've written. And this loop seems to have little chance of terminating!

You have at least three proofs of this now, two from first principles and one using real numbers. You have to decide whether you want to focus on this last one - from your textbook.
I'm fine with the proof from the notes, its just that since you said it wasn't from first principles I was just wondering on how your proof, which comes from first principle works.

lys04 said:
I'm fine with the proof from the notes, its just that since you said it wasn't from first principles I was just wondering on how your proof, which comes from first principle works.
I'll repost what I have above. Do you follow this?

Suppose ##s\in \mathbb Q## is the supremum for ##S## with ##s^2 < 2##. For ##n \in \mathbb N##, consider ##q_n = s + \frac 1 n##. As ##q_n > s##, ##q_n \notin S##, hence ##q_n^2 > 2##. So, we have, ##\forall n \in \mathbb N##:
$$s^2 < 2 < (s + \frac 1 n)^2 = s^2 + \frac{2s}{n} + \frac 1 {n^2}$$Hence, ##\forall n \in \mathbb N##:$$0 < 2 - s^2 < \frac{2s}{n} + \frac 1 {n^2}$$From that you can try to find a positive rational which is less than ##\frac 1 n## for every ##n##.

Then, use a similar argument if ##s^2 > 2##.

PeroK said:
I'll repost what I have above. Do you follow this?

Suppose ##s\in \mathbb Q## is the supremum for ##S## with ##s^2 < 2##. For ##n \in \mathbb N##, consider ##q_n = s + \frac 1 n##. As ##q_n > s##, ##q_n \notin S##, hence ##q_n^2 > 2##. So, we have, ##\forall n \in \mathbb N##:
$$s^2 < 2 < (s + \frac 1 n)^2 = s^2 + \frac{2s}{n} + \frac 1 {n^2}$$Hence, ##\forall n \in \mathbb N##:$$0 < 2 - s^2 < \frac{2s}{n} + \frac 1 {n^2}$$From that you can try to find a positive rational which is less than ##\frac 1 n## for every ##n##.

Then, use a similar argument if ##s^2 > 2##.
Not really, is the goal here trying to find a contradiction to the assumption that s is a supremum?

lys04 said:
Not really, is the goal here trying to find a contradiction to the assumption that s is a supremum?
Yes. A contradiction can be to something assumed within the proof, or to some established result. Like a) above.

PeroK said:
Yes. A contradiction can be to something assumed within the proof, or to some established result. Like a) above.
hmm I don't see where there might be a contradiction though..

lys04 said:
hmm I don't see where there might be a contradiction though..
Do you see that the following can't hold for all ##n##?
$$0 < 2 - s^2 < \frac{2s}{n} + \frac 1 {n^2}$$

PeroK said:
Do you see that the following can't hold for all ##n##?
$$0 < 2 - s^2 < \frac{2s}{n} + \frac 1 {n^2}$$
yes.

lys04 said:
yes.
That's the contradiction. And it all started by assuming that ##s = \sup(S)##.

If you understand this, you should do the second half of the proof for the case where ##s^2 > 2##.

PeroK said:
That's the contradiction. And it all started by assuming that ##s = \sup(S)##.
is 2s/n+1/n^2 in S tho?

lys04 said:
is 2s/n+1/n^2 in S tho?
##s## is rational and ##n## is a natural number, so yes, that is definitely a rational number.

PeroK said:
##s## is rational and ##n## is a natural number, so yes, that is definitely a rational number.
Ok so you’re supposing s is the supremum of S, which when squared should be a number that is extremely close to 2, but not exactly since there is no sqrt 2 in Q.
And since s is the supremum, there should be no number whose squared is bigger than it?
But how is 2s/n+1/n^2 in S? Even though it’s a rational number. (2s/n+1/n^2)^2=4s^2/n^2+4s/n^3+1/n^4. How is this less than 2?

lys04 said:
Ok so you’re supposing s is the supremum of S, which when squared should be a number that is extremely close to 2, but not exactly since there is no sqrt 2 in Q.
And since s is the supremum, there should be no number whose squared is bigger than it?
But how is 2s/n+1/n^2 in S?
That question makes no sense.
lys04 said:
Even though it’s a rational number. (2s/n+1/n^2)^2=4s^2/n^2+4s/n^3+1/n^4. How is this less than 2?
That number is arbitrarily small for increasing ##n##.

To be honest, I don't think you understand what I'm doing at all. I'm not sure how much more I can help.

Have you done any subject that requires proofs?

• Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
881
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K