Math2020: Solving discrete problems

homework 5 hint

An equivalence relation

1) must be symmetric - this means that if a is related to b, then b is related to a.

E.g., if the relation is <, this is not symmetric, since if we have a < b, then we won't have b < a. But = is symmetric, since if a=b, then b=a.

2) must be reflexive. This means that a is related to a for all a. E.g., < is not reflexive, since we don't have a< a. But = is, since a=a for all integers.

3) must be transitive. This means that if a is related to b and b is related to c, the a is related to c.

For example, if a< b and b< c, then a< c, so < is transitive (though since it's not reflexive or symmetric its not an equivalence relation).

You have to check each property; if you think it's true, use the definition to prove it. If you think it's not true, find an example where it's not true.

Here's an example of a relation which is symmetric and reflexive but not transitive: let the set be all positive integers except 1. Say "a R b" if gcd(a,b) > 1.

Then for all a, gcd(a,a)=a > 1, so a R a, so R is reflexive. (this is true, so I proved this using the definition)

For all a,b, gcd(a,b)=gcd(b,a), so if a R b, then b R a, so R is symmetric. (this is true, so I proved this using the definition)

But R is not transitive. For example, 9 R 6 and 6 R 8 but we don't have 9 R 8. (this property is false, which proved with an example to show that.)


A hint for question 1 (see the handout for notation)

It should help to construct some examples. I'll write W for the write box and B for the black box, since I don't have a key for writing a box in email.

E.g., 8 W 2 because 8/2 = 4 = 2^2
2 W 8 because 2/8 = 1/4 = (1/2)^2
3 W 75 because 3/75 = 1/25 = (1/5)^2.
Now for B we have
8 B 2 because 8*2 = 16 = 4^4
3 B 75 because 3*75 = 15^2
So, we have 8 W 2 and also 8 B 2.

Find some more examples with a W b, and see if we also have a B b.
Can you find any pattern and show that a W b => a B b?