3
$\begingroup$

Let $A={a,b,c,d,e,f}$ and let $R\subset A\times A$ be a relation which is symmetric and transitive. You have been given some partial information about the relation which is that the following are known to be true for the relation:

$$R(e,a), R(b,f), R(e,c), R(d,a), R(b,a)$$

Given all the above information does $R(c,f)$ hold or not? Explain your answer using the information you have been provided with above.

I would argue that $R(c,f)$ does not hold. No two pairs would equal $R(c,f)$ and $R(f,c)$.

Does this seem correct?

Update: Just thought of this.

R(b,f) and R(b,a) would be the same as R(f,a).

R(f,a) and R(e,a) would be the same as R(f,e).

Therefore, R(f,e) and R(e,c) would be the same as R(f,c).

As the relation is symmetric, R(f,c) -> R(c,f).

How's that?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ That's correct! Note - be careful not to mix up symmetry and transitivity; on the last line, you meant to say symmetry. $\endgroup$ – Alexander Heyes Dec 14 '15 at 3:48
  • $\begingroup$ Just corrected that! Did I solve this as efficiently as possible or is there a better method? $\endgroup$ – M-R Dec 14 '15 at 3:50
  • $\begingroup$ There is a technical term "transitive set", and while it relates to your use here, what you really mean is a transitive (and symmetric) relation. $\endgroup$ – Asaf Karagila♦ Dec 14 '15 at 4:34
  • $\begingroup$ I think if you draw a picture, you'll see that you've taken the most efficient path from $c$ to $f$, so in that sense this is the most efficient route using the properties of transitivity and symmetry. In another sense, you could argue it would be more 'neat' to simply draw the picture, and say "there is a path from $c$ to $f$, therefore $R(c, f)$." Efficiency isn't really what you're looking for in mathematics answers, it's more about understanding and effective communication. If you can explain your answer well, you've succeeded. $\endgroup$ – Alexander Heyes Dec 14 '15 at 20:46
1
$\begingroup$

This is a great question to apply some methods from Polya's 'How to Solve it'. Namely, can you draw a picture???

Because the relation $R$ is symmetric and transitive, it makes a lot of sense to draw this like a mathematical graph (that's different from a 'graph' of $f(x)=x^2$, by the way - wiki it).

So if you draw $a, b, c, d, e, f$ as points on your page, and connect them with lines whenever you know they're related, the question becomes - is there a path from $c$ to $f$?

If there was any such path, using, for example, $c\mapsto e\mapsto a\mapsto b\mapsto f$, then you would know, using symmetry: $$R(c, e), R(e, a), R(a, b), R(b, f)$$ Applying transitivity to the first pair, you could 'walk' from $c$ to $a$, concluding $R(c, a)$. Then repeat, until you conclude $R(c, f)$!

Improve this answer
$\endgroup$
0
$\begingroup$

Each of the following must hold. I leave as an exercise finding the justifications, in order.

  1. $R(c,e)$

  2. $R(c,a)$

  3. $R(a,b)$

  4. $R(c,b)$

  5. $R(c,f)$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.