Proving partial orders in set theory for $(x_1,y_1 )≤(x_2,y_2 )⇔〖(x〗_1 ≤_X x_2$ and $x_2 ≰_X...
I'm trying to prove partial order for a set, but I can't seem to be able to fully understand what I'm doing and weather I'm doing it right at all. I don't think I understand how to work with all the conditions between the two partial oders when proving antisymmetry and transitivity because of all the conditions I have to work with to get there.
The exercise is as follows:
Let X be a partial order with the sign $$≤_X$$ and Y be a partial order with the sign $$≤_Y$$ Prove that the following is a partial order for $$Xtimes Y$$ given that: $$(x_1,y_1 ) le (x_2,y_2 ) iff (x_1 le_X x_2 text{ and } x_2 not le_X x_1)text{ or }(x_1 =_X x_2 text { and } y_1 le_Y y_2)$$
elementary-set-theory order-theory
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
asked Nov 23 '18 at 8:22
yard24yard24
32
closed as off-topic by Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos Nov 24 '18 at 9:07
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
I'm trying to prove partial order for a set, but I can't seem to be able to fully understand what I'm doing and weather I'm doing it right at all. I don't think I understand how to work with all the conditions between the two partial oders when proving antisymmetry and transitivity because of all the conditions I have to work with to get there.
The exercise is as follows:
Let X be a partial order with the sign $$≤_X$$ and Y be a partial order with the sign $$≤_Y$$ Prove that the following is a partial order for $$Xtimes Y$$ given that: $$(x_1,y_1 ) le (x_2,y_2 ) iff (x_1 le_X x_2 text{ and } x_2 not le_X x_1)text{ or }(x_1 =_X x_2 text { and } y_1 le_Y y_2)$$
elementary-set-theory order-theory
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
asked Nov 23 '18 at 8:22
yard24yard24
32
closed as off-topic by Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos Nov 24 '18 at 9:07
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos
If this question can be reworded to fit the rules in the help center, please edit the question.
Check the definition in the last formula again, please! At the end of the first parenthesis, $x_1 not le_X x_1$ is always false, and at the beginning of the second parenthesis $x_1 =_X x_2$ makes not much sense, as $X$ defines an order, not an equality.
– Ingix
Nov 23 '18 at 8:58
I corrected the mistake with the x1≰Xx1, it is suppose to be x2≰Xx1. And with the x1=Xx2 I think the meaning is that since X is a partial order in itself then $$ X_1 <_x X_2$$ and $$ X_2 >_x X_1$$.
– yard24
Nov 23 '18 at 9:19
A partial order is antisymmetric, that means $a le b$ and $b le a$ implies $a=b$. $x_1=x_2$ makes sense, $x_1$ and $x_2$ are just the same. What I'm meaning with $x_1 =_X x_2$ making no sense is that there is no additional information or structure provided with it, it just the same as $x_1=x_2$,for any $X$. Now the problems makes sense (to me). Try to understand what the first parenthesis wants to express, maybe you can express that in a simpler formula as first step to understanding what it means.
– Ingix
Nov 23 '18 at 9:37
add a comment |
I'm trying to prove partial order for a set, but I can't seem to be able to fully understand what I'm doing and weather I'm doing it right at all. I don't think I understand how to work with all the conditions between the two partial oders when proving antisymmetry and transitivity because of all the conditions I have to work with to get there.
The exercise is as follows:
Let X be a partial order with the sign $$≤_X$$ and Y be a partial order with the sign $$≤_Y$$ Prove that the following is a partial order for $$Xtimes Y$$ given that: $$(x_1,y_1 ) le (x_2,y_2 ) iff (x_1 le_X x_2 text{ and } x_2 not le_X x_1)text{ or }(x_1 =_X x_2 text { and } y_1 le_Y y_2)$$
elementary-set-theory order-theory
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
asked Nov 23 '18 at 8:22
yard24yard24
32
I'm trying to prove partial order for a set, but I can't seem to be able to fully understand what I'm doing and weather I'm doing it right at all. I don't think I understand how to work with all the conditions between the two partial oders when proving antisymmetry and transitivity because of all the conditions I have to work with to get there.
The exercise is as follows:
Let X be a partial order with the sign $$≤_X$$ and Y be a partial order with the sign $$≤_Y$$ Prove that the following is a partial order for $$Xtimes Y$$ given that: $$(x_1,y_1 ) le (x_2,y_2 ) iff (x_1 le_X x_2 text{ and } x_2 not le_X x_1)text{ or }(x_1 =_X x_2 text { and } y_1 le_Y y_2)$$
elementary-set-theory order-theory
elementary-set-theory order-theory
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
asked Nov 23 '18 at 8:22
yard24yard24
32
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
asked Nov 23 '18 at 8:22
yard24yard24
32
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
edited Nov 23 '18 at 9:39
Scientifica
6,37641335
6,37641335
asked Nov 23 '18 at 8:22
yard24yard24
32
asked Nov 23 '18 at 8:22
yard24yard24
32
asked Nov 23 '18 at 8:22
yard24yard24
32
32
closed as off-topic by Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos Nov 24 '18 at 9:07
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos Nov 24 '18 at 9:07
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Scientifica, GNUSupporter 8964民主女神 地下教會, Leucippus, Cesareo, Rebellos
If this question can be reworded to fit the rules in the help center, please edit the question.
Check the definition in the last formula again, please! At the end of the first parenthesis, $x_1 not le_X x_1$ is always false, and at the beginning of the second parenthesis $x_1 =_X x_2$ makes not much sense, as $X$ defines an order, not an equality.
– Ingix
Nov 23 '18 at 8:58
I corrected the mistake with the x1≰Xx1, it is suppose to be x2≰Xx1. And with the x1=Xx2 I think the meaning is that since X is a partial order in itself then $$ X_1 <_x X_2$$ and $$ X_2 >_x X_1$$.
– yard24
Nov 23 '18 at 9:19
A partial order is antisymmetric, that means $a le b$ and $b le a$ implies $a=b$. $x_1=x_2$ makes sense, $x_1$ and $x_2$ are just the same. What I'm meaning with $x_1 =_X x_2$ making no sense is that there is no additional information or structure provided with it, it just the same as $x_1=x_2$,for any $X$. Now the problems makes sense (to me). Try to understand what the first parenthesis wants to express, maybe you can express that in a simpler formula as first step to understanding what it means.
– Ingix
Nov 23 '18 at 9:37
add a comment |
Check the definition in the last formula again, please! At the end of the first parenthesis, $x_1 not le_X x_1$ is always false, and at the beginning of the second parenthesis $x_1 =_X x_2$ makes not much sense, as $X$ defines an order, not an equality.
– Ingix
Nov 23 '18 at 8:58
I corrected the mistake with the x1≰Xx1, it is suppose to be x2≰Xx1. And with the x1=Xx2 I think the meaning is that since X is a partial order in itself then $$ X_1 <_x X_2$$ and $$ X_2 >_x X_1$$.
– yard24
Nov 23 '18 at 9:19
A partial order is antisymmetric, that means $a le b$ and $b le a$ implies $a=b$. $x_1=x_2$ makes sense, $x_1$ and $x_2$ are just the same. What I'm meaning with $x_1 =_X x_2$ making no sense is that there is no additional information or structure provided with it, it just the same as $x_1=x_2$,for any $X$. Now the problems makes sense (to me). Try to understand what the first parenthesis wants to express, maybe you can express that in a simpler formula as first step to understanding what it means.
– Ingix
Nov 23 '18 at 9:37
Check the definition in the last formula again, please! At the end of the first parenthesis, $x_1 not le_X x_1$ is always false, and at the beginning of the second parenthesis $x_1 =_X x_2$ makes not much sense, as $X$ defines an order, not an equality.
– Ingix
Nov 23 '18 at 8:58
Check the definition in the last formula again, please! At the end of the first parenthesis, $x_1 not le_X x_1$ is always false, and at the beginning of the second parenthesis $x_1 =_X x_2$ makes not much sense, as $X$ defines an order, not an equality.
– Ingix
Nov 23 '18 at 8:58
I corrected the mistake with the x1≰Xx1, it is suppose to be x2≰Xx1. And with the x1=Xx2 I think the meaning is that since X is a partial order in itself then $$ X_1 <_x X_2$$ and $$ X_2 >_x X_1$$.
– yard24
Nov 23 '18 at 9:19
I corrected the mistake with the x1≰Xx1, it is suppose to be x2≰Xx1. And with the x1=Xx2 I think the meaning is that since X is a partial order in itself then $$ X_1 <_x X_2$$ and $$ X_2 >_x X_1$$.
– yard24
Nov 23 '18 at 9:19
A partial order is antisymmetric, that means $a le b$ and $b le a$ implies $a=b$. $x_1=x_2$ makes sense, $x_1$ and $x_2$ are just the same. What I'm meaning with $x_1 =_X x_2$ making no sense is that there is no additional information or structure provided with it, it just the same as $x_1=x_2$,for any $X$. Now the problems makes sense (to me). Try to understand what the first parenthesis wants to express, maybe you can express that in a simpler formula as first step to understanding what it means.
– Ingix
Nov 23 '18 at 9:37
A partial order is antisymmetric, that means $a le b$ and $b le a$ implies $a=b$. $x_1=x_2$ makes sense, $x_1$ and $x_2$ are just the same. What I'm meaning with $x_1 =_X x_2$ making no sense is that there is no additional information or structure provided with it, it just the same as $x_1=x_2$,for any $X$. Now the problems makes sense (to me). Try to understand what the first parenthesis wants to express, maybe you can express that in a simpler formula as first step to understanding what it means.
– Ingix
Nov 23 '18 at 9:37
add a comment |
1 Answer
1
active
oldest
votes
I preassume that $=_X$ denotes the equality relation on $X$.
Then relation $leq$ on $Xtimes Y$ is defined by:$$(x_1,y_1)leq(x_2,y_2)iff [x_1<_X x_2text{ or }(x_1=x_2text{ and }y_1leq_Y y_2)]$$where $x_1<_X x_2$ abbreviates $x_1leq_X x_2text{ and }x_1neq x_2$.
Based on $x_1=x_1text{ and }y_1=y_1$ we then find that $(x_1,y_1)leq(x_1,y_1)$, proving reflexivity.
In order to prove transitivity let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_3,y_3)$.
Now discern the following cases:
$x_1<_X x_2$ and $x_2<_Xx_3$ leading to $x_1<_X x_3$
$x_1<_X x_2$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $x_2<_X x_3$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $[x_1=x_3text{ and }y_1leq_Y y_3]$
In each case the conclusion $(x_1,y_1)leq(x_3,y_3)$ is justified, so this proves transitivity.
Now it remains to prove antisymmetry, and for that let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_1,y_1)$.
On base of this it must be shown that $(x_1,y_1)=(x_3,y_3)$.
As above discern $4$ cases and give it a try yourself.
Let me know if you run into troubles.
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
|
show 3 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I preassume that $=_X$ denotes the equality relation on $X$.
Then relation $leq$ on $Xtimes Y$ is defined by:$$(x_1,y_1)leq(x_2,y_2)iff [x_1<_X x_2text{ or }(x_1=x_2text{ and }y_1leq_Y y_2)]$$where $x_1<_X x_2$ abbreviates $x_1leq_X x_2text{ and }x_1neq x_2$.
Based on $x_1=x_1text{ and }y_1=y_1$ we then find that $(x_1,y_1)leq(x_1,y_1)$, proving reflexivity.
In order to prove transitivity let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_3,y_3)$.
Now discern the following cases:
$x_1<_X x_2$ and $x_2<_Xx_3$ leading to $x_1<_X x_3$
$x_1<_X x_2$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $x_2<_X x_3$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $[x_1=x_3text{ and }y_1leq_Y y_3]$
In each case the conclusion $(x_1,y_1)leq(x_3,y_3)$ is justified, so this proves transitivity.
Now it remains to prove antisymmetry, and for that let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_1,y_1)$.
On base of this it must be shown that $(x_1,y_1)=(x_3,y_3)$.
As above discern $4$ cases and give it a try yourself.
Let me know if you run into troubles.
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
|
show 3 more comments
I preassume that $=_X$ denotes the equality relation on $X$.
Then relation $leq$ on $Xtimes Y$ is defined by:$$(x_1,y_1)leq(x_2,y_2)iff [x_1<_X x_2text{ or }(x_1=x_2text{ and }y_1leq_Y y_2)]$$where $x_1<_X x_2$ abbreviates $x_1leq_X x_2text{ and }x_1neq x_2$.
Based on $x_1=x_1text{ and }y_1=y_1$ we then find that $(x_1,y_1)leq(x_1,y_1)$, proving reflexivity.
In order to prove transitivity let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_3,y_3)$.
Now discern the following cases:
$x_1<_X x_2$ and $x_2<_Xx_3$ leading to $x_1<_X x_3$
$x_1<_X x_2$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $x_2<_X x_3$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $[x_1=x_3text{ and }y_1leq_Y y_3]$
In each case the conclusion $(x_1,y_1)leq(x_3,y_3)$ is justified, so this proves transitivity.
Now it remains to prove antisymmetry, and for that let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_1,y_1)$.
On base of this it must be shown that $(x_1,y_1)=(x_3,y_3)$.
As above discern $4$ cases and give it a try yourself.
Let me know if you run into troubles.
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
|
show 3 more comments
I preassume that $=_X$ denotes the equality relation on $X$.
Then relation $leq$ on $Xtimes Y$ is defined by:$$(x_1,y_1)leq(x_2,y_2)iff [x_1<_X x_2text{ or }(x_1=x_2text{ and }y_1leq_Y y_2)]$$where $x_1<_X x_2$ abbreviates $x_1leq_X x_2text{ and }x_1neq x_2$.
Based on $x_1=x_1text{ and }y_1=y_1$ we then find that $(x_1,y_1)leq(x_1,y_1)$, proving reflexivity.
In order to prove transitivity let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_3,y_3)$.
Now discern the following cases:
$x_1<_X x_2$ and $x_2<_Xx_3$ leading to $x_1<_X x_3$
$x_1<_X x_2$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $x_2<_X x_3$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $[x_1=x_3text{ and }y_1leq_Y y_3]$
In each case the conclusion $(x_1,y_1)leq(x_3,y_3)$ is justified, so this proves transitivity.
Now it remains to prove antisymmetry, and for that let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_1,y_1)$.
On base of this it must be shown that $(x_1,y_1)=(x_3,y_3)$.
As above discern $4$ cases and give it a try yourself.
Let me know if you run into troubles.
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
I preassume that $=_X$ denotes the equality relation on $X$.
Then relation $leq$ on $Xtimes Y$ is defined by:$$(x_1,y_1)leq(x_2,y_2)iff [x_1<_X x_2text{ or }(x_1=x_2text{ and }y_1leq_Y y_2)]$$where $x_1<_X x_2$ abbreviates $x_1leq_X x_2text{ and }x_1neq x_2$.
Based on $x_1=x_1text{ and }y_1=y_1$ we then find that $(x_1,y_1)leq(x_1,y_1)$, proving reflexivity.
In order to prove transitivity let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_3,y_3)$.
Now discern the following cases:
$x_1<_X x_2$ and $x_2<_Xx_3$ leading to $x_1<_X x_3$
$x_1<_X x_2$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $x_2<_X x_3$ leading to $x_1<_X x_3$
$[x_1=x_2text{ and }y_1leq_Y y_2]$ and $[x_2=x_3text{ and }y_2leq_Y y_3]$ leading to $[x_1=x_3text{ and }y_1leq_Y y_3]$
In each case the conclusion $(x_1,y_1)leq(x_3,y_3)$ is justified, so this proves transitivity.
Now it remains to prove antisymmetry, and for that let $(x_1,y_1)leq(x_2,y_2)$ and $(x_2,y_2)leq(x_1,y_1)$.
On base of this it must be shown that $(x_1,y_1)=(x_3,y_3)$.
As above discern $4$ cases and give it a try yourself.
Let me know if you run into troubles.
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
answered Nov 23 '18 at 10:01
drhabdrhab
98.5k544129
98.5k544129
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
|
show 3 more comments
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
Thanks a lot! I had a look at it again and tried to solve it myslef. I managed to get nearly all the way to proving transitivity but I have a problem with combining all the cases you've stated back to the original condition for $$(x_1,y_1)≤(x_3,y_3)$$. I can see the $$x_1 = x_3 and y_1 ≤_Y y_3$$ part but I can't figure out how to reach the first condition being $$(x_1 ≤_X x_2 and x_2 ≰_X x_1)$$ I assume that between all the bullets for proving transitivity ther'e 'or's.
– yard24
Nov 23 '18 at 15:28
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
I had a look at it again and I think I got it. I worked with all the conditions together and ended up having 4 different conditions with 'or's between them and 2 of them were $$x_1=x_3 and y_1 ≤_Y y_3$$ and the second: $$x_1 ≤_X x_3 and x_3≰X x_1$$ So basically I have a the conditions I need to prove that $$(x_1,y_1) <= (x_3,y_3)$$
– yard24
Nov 23 '18 at 15:42
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
and in my first comment I meant $$x_3$$ insted of $$x_2$$
– yard24
Nov 23 '18 at 15:45
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
To get more clarity I ask you the following questions: 1) do you understand that $x_1leq_X x_2text{ and }neg[x_2leq_X x_1]$ is exactly the same as the more handsome $x_1<_X x_2$? 2) do you agree with the proof in my answer of transitivity? 3) have you managed to prove antisymmetry, or are you still wrestling with that?
– drhab
Nov 23 '18 at 16:01
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
doesn't the ≤ sign only denote the partial order and not the regular ≤ sign, so there can't be only a '<' sign? and can't ¬x1 be equall to either x2 or x3? (since it's the complement).
– yard24
Nov 23 '18 at 16:14
|
show 3 more comments
Check the definition in the last formula again, please! At the end of the first parenthesis, $x_1 not le_X x_1$ is always false, and at the beginning of the second parenthesis $x_1 =_X x_2$ makes not much sense, as $X$ defines an order, not an equality.
– Ingix
Nov 23 '18 at 8:58
I corrected the mistake with the x1≰Xx1, it is suppose to be x2≰Xx1. And with the x1=Xx2 I think the meaning is that since X is a partial order in itself then $$ X_1 <_x X_2$$ and $$ X_2 >_x X_1$$.
– yard24
Nov 23 '18 at 9:19
A partial order is antisymmetric, that means $a le b$ and $b le a$ implies $a=b$. $x_1=x_2$ makes sense, $x_1$ and $x_2$ are just the same. What I'm meaning with $x_1 =_X x_2$ making no sense is that there is no additional information or structure provided with it, it just the same as $x_1=x_2$,for any $X$. Now the problems makes sense (to me). Try to understand what the first parenthesis wants to express, maybe you can express that in a simpler formula as first step to understanding what it means.
– Ingix
Nov 23 '18 at 9:37