Relations assignment 1. Prove or disprove that < (\"less than\") is a partial or
ID: 3889853 • Letter: R
Question
Relations assignment
1. Prove or disprove that < ("less than") is a partial order on .
2. Determine whether {(a,a)(a,b),(b,b),(c,c),(c,d),(c,e),(d,d),(d,e), (e,e)} is a partial order on {a,b,c,d,e}.
3. Prove or disprove that "is a subset of" is a partial order on the power set of a set A.
4.For a poset({2,4,6,9,12,18,27,36,48,60,72}, |), answer the following.
A. Give all maximal elements.
B. Give all minimal elements.
C. Is there the greatest element? If so, what is it?
D.Is there the least element? If so, what is it?
E. Give all upper bounds of {2, 9}.
F. Is there the least upper bound of {2, 9}? If so, what is it?
G. Give all lower bounds of {60, 72}.
H. Is there the greatest lower bound of {60, 72}? If so, what is it?
5. Let R(S) denote the set of all binary relations on a set S. A binary relation < on R(S) is defined as R 1 < R2 iff R 1 R2.Prove or disprove that (R(S), < ) is a poset.
6. Let be an alphabet. Assume that is totally ordered with a total order on .Let < denote a lexicographic order on.Prove or disprove that (, < ) is a poset.
7. Let | be a binary relation on + such that a | b iff b = ka for some integer k. Prove or disprove that (+, | ) is a poset.
8. Let | be a binary relation on such that a | b iff a 0 and b = ka for some integer k. Prove or disprove that (, | ) is a poset.
11. Let R be a binary relation on + such that a R b iff a b and b = ka for some integer k. Prove or disprove that R has each of the following 3 properties: Reflexivity, antisymmetry and transitivity.
12. Let R be abinary relation on × such that (x1, y 1) R (x2 ,y2) iff ( x1 < x2) ( x 1= x 2 y 1 y 2). Prove or disprove that (2,R) is a poset.
13. Let R be a binary relation on + such that x R y iff x y ( x ylcm(x,y) = xy ), where "lcm" stands for the least common multiple. Prove or disprove that (+, R) is a poset.
Explanation / Answer
Hi, As per chegg policy, we are ony supposed to answer 4 subparts of a question, in this case 1,2,3 since others are independent questions, please post them as separate question.
A relation on set is called partial order if its transitive and anti-symmetric
A relation is antisymmetic if for any a,b in R and b,a also in R then a=b
A relation is transitive if for any a,b in R and b,c in R then a,c is in R
1. For less than.
Anti-symmetric- if for any 2 integers p and q, if p,q is in relation i.e p<q
then assume q,p also exists i.e q<p which is only possible when p=q, hence anti symmetric
Tranitive- if for any 3 integers exist in R such that p<q and q<r then we know that p<r which means p,r is in R hence transitive.
Therefore < is a partial order on Z
2.given R is {(a,a)(a,b),(b,b),(c,c),(c,d),(c,e),(d,d),(d,e), (e,e)} on set {a,b,c,d,e}
Transitive- if you observe in this (c,d) exists and also (d,e) but not (c,e) hence not transitive therefore not a partial order
3.Given relation is 'is subset of" on power set of a set A
Anti-symmetric- consider 2 element of the relation A and B then A is subet of B i.e every element of A is in B.
Now assuming B is subset of A, i.e every element of B is in A, which means that any element we choose should be both in A and B i.e A=B, hence anti symmetric
Transitive-Condiser 3 element of relation A,B,C such that A is subset of B, B is subset of C, lets take a arbitary value p from A, we know that p is in B since 'A is subset of B' similary since p is in B, its in C, therefore for any arbitary value p which is in A is also in C therefore A is subset of C, hence transitive
Hence this relation is a partial order
Thumbs up if this was helpful, otherwise let me know in comments.