Supremum of a set, relations and order

[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?

 

[PeroK]

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

 

[lys04]

It was from another physics forum post

 

[lys04]

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?

 

[PeroK]

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$.

Could you link to that thread?

 

[lys04]

Let r be an upper bound for S. Note that 1∈S, so r≥1. That disproves your assertion that r could be

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. But 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/

 

[PeroK]

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.

 

[lys04]

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?

 

[PeroK]

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$.

 

[PeroK]

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$.

 

[lys04]

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?

 

[PeroK]

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.

 

[lys04]

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.

Yes your right.
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?

 

[PeroK]

Yes your right.
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".

 

[lys04]

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?

 

[PeroK]

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.

 

[lys04]

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

 

[PeroK]

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.

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).

 

[lys04]

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?

 

[PeroK]

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?

 

[lys04]

It's something that can be proved quite easily.

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

yes

 

[PeroK]

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.

 

[lys04]

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.

 

[PeroK]

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$.

 

[lys04]

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?

 

[PeroK]

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.

 

[lys04]

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..

 

[PeroK]

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}$$

 

[lys04]

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

yes.

 

[PeroK]

yes.

That's the contradiction. And it all started by assuming that $s = \sup(S)$.

 

[PeroK]

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

 

[lys04]

That's the contradiction. And it all started by assuming that $s = \sup(S)$.

is 2s/n+1/n^2 in S tho?

 

[PeroK]

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.

 

[lys04]

$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?

 

[PeroK]

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.

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?