Set Relations and Equivalence relation.

Question

I'm confused as the question mention from a to b but why does it mention including 0 flights? Can somebody answer the whole question and explain the solution?

Thanks.

Answer 1

An equivalence relation must be reflexive (i.e., $aRa$ for all $a\in V$), symmetric ($aRb$ implies $bRa$) and transitive ($aRb$ and $bRc$ implies $aRc$).

The relation is reflexive because you can travel from one city to the same city using 0 flights ($0$ is even), symmetric because if you can travel from $a$ to $b$ using an even number of flights, you can take the flights back to travel from $b$ to $a$ using an even number of flights. Finally, it is transitive because if $aRb$ and $bRc$, then the number of flights needed to go from $a$ to $c$ is the sum of the numbers of flights from $a$ to $b$ and from $b$ to $c$, respectively.

To describe the equivalence relations, simply take one element and look for the cities that can be reached from that city using an even number of flights (for instance, $y$ and $w$). There will be two equivalence classes.

Finally, if we ask for an odd number of flights instead of an even number of flights, would the new relation be reflexive? or transitive? (If we call $R'$ to this new relation, notice that $yR'x$ and $xR'w$, but $yR'w$ does not hold)

Answer 2

Recall that an equivalence relation is reflexive, symmetric, and transitive.

a) In this scenario, if you can travel from a city to another city in an even number of flights, they are $R$ related.   Zero is also an even number.   Of course, this means any city is $R$ related to itself.   What does that mean?   What else must we test?

b) In this scenario, if you can travel from a city to another city in an odd number of flights, they are $R$ related.   Zero is not an odd number.   Of course, this means any city is not $R$ related to itself.   What does that mean?   What else must we test?

Answer 3

One possible way is to define a relation $R_1$ on $V$, according to adjacency of vertices. Then using relation composition, one can get new relations, by composing $R_1$ to itself ($R=R_1.R_1$). Now, you need to notice that if $(a,b)\in R_1$, then so is $(b,a)\in R_1$ and by composing them, we get $(a,a),(b,b)\in R$. Going from $a$ to $a$ can be done using even flights, because of the structure of the graph (a cycle of length $4$ and a branch). So, when we say we have gone from $a$ to $a$, it can be any even number and for the sake of algebraic accurateness, we want to include $0$.