I have a relation problem that I am stuck on for my Discrete

I have a relation problem that I am stuck on for my Discrete Mathematics homework.

Question:

Consider the relation on the natural numbers given by a R b <=> a/b = 2^k for some k>= 0. Show that R is not an equivaence relation.

I know it\'s symmetric because a = b2^k so b2^k/b = 2^k => 2^k = 2^k

But I am not sure how to prove or disprove for reflexive, or transitivity. Since I am dissproving an equivlance I just need to find on case that is not transitive or reflexive. We did a few like this in class but not where a & b are equal to some number in a set of numbers.

Solution

This relation is not symmetric. Consider 4 and 2. 4 R 2 since 4/2 = 2 = 2^1. But 2 R 4 is false since 2/4=1/2 which is not of the form 2^k for k>=0.

This relation is transitive. Suppose x R y and y R z. This means x/y=2^a and y/z=2^b for a,b >=0. Multiplying we get

x/z = 2^(a+b) and a+b>=0 since both a and b are >=0. Thus x R z. The symmetric property fails.