Show that the relation R on N is given by aRb iff \\( b = 2^ka \\) for some inte
ID: 1888432 • Letter: S
Question
Show that the relation R on N is given by aRb iff ( b = 2^ka ) for some integer ( k ge 0 ) is a partial orderingExplanation / Answer
We need to show the relation is reflexive, antisymmetric, and transitive: (Reflexive) Since a = (2^0)a, then aRa. Thus the relation is reflexive. (Antisymmetric) Assume aRb and bRa. Then b=(2^x)a and a=(2^y)b for some integers x,y. Hence b=(2^x)(2^y)b implying 1=2^(x+y). Hence x+y=0 => x=-y. Since x and y have to both be nonnegative, if x = -y, then that means x = y = 0. Therefore a=(2^x)b=(2^0)b implies a = b. Thus the relation is antisymmetric. (Transitive) Assume aRb and bRc. Then b=(2^x)a and c=(2^y)b for some integers x,y. Hence c=(2^y)(2^x)a=(2^(x+y))a. Since x+y is also an integer, then aRc. Thus the relation is transitive. Therefore R is a partial ordering on N.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.