Question

For the set of cities on a map, consider the relation xry if and only if city x is connected by a road to city y. A city is considered to be connected to itself, and two cities are connected even though there are cities on the road between them. Is this an equivalence relation or a partial ordering? Explain

Answer 1

It is an equivalence relation

Explanation:

REcall that a binary operation * is an equivalence relation if the three following properties hold

1. * is reflexive. That is every element happens to fulfill a*a.

2. * is symmetric. That is if a*b, then b*a.

3. * it has transitivity. That is if a*b and b*c then a*c.

Let * be the relation is connected by a road. By definition, every city is connected to itself, so if x is a city, then x*x.

If a city x is connected to y(x*y) then y is connected to x (y*x).

The statement "two cities are connected even though there are cities on the road between them" is the description of transitivity. That is, if we have 3 cities, x, c and y and c is in the middle of x and y, and x is connected to c (x*c)and c is connected to y(c*y) then x is connected to y (x*y).

So, this relation fulfills the three characteristics of an equivalence relation.