3.9k views
2 votes
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

1 Answer

4 votes

Answer:

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.

User Sschilli
by
8.7k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories