1
$\begingroup$

Is A = {(1,1) (1,2) (2,1)} a transitive relation on {1,2}?

It is confusing. Yes and No both seems to be right. I only need a hint.

  • 5
    My hint is: First write down the definition of a transitive relation. It is a condition that begins "For all $x$, $y$, and $z$, …". There are only 8 possible choices of $x$, $y$, and $z$. Then check the condition for each of the 8 possible cases. If they are all true, the relation is transitive.2012-04-30
  • 3
    When I said "write down" I really meant that you should *write* it, not that you should read it from the book, or imagine it. I hope this was clear.2012-04-30
  • 0
    http://en.wikipedia.org/wiki/Transitive_relation2012-04-30
  • 0
    2 is related to 1, and 1 is related to 2, therefore transitivity would say 2 is related to 2. But it isn't.2012-04-30
  • 0
    You might want to explain why you think that both Yes and No are right.2012-05-27

2 Answers 2

3

Hint: $(2,2)$ is not a member of $A$.

2

Hint: if it were "no", you would be able to find a pair (a,b), (b,c), but you would be missing the pair (a,c).

  • 0
    so you are saying that the answer is yes.2012-04-30
  • 3
    I'm giving you a hint to try to get you to stop thinking the answer is "Yes and No". Mark Dominus' advice above is good, try it out!2012-04-30
  • 0
    since 1R2 and 2R1 and we also have 1R1 therefore the relation is transitive. Is this correct?2012-04-30
  • 4
    That is one of the 8 things to check. Now do the other 7.2012-04-30
  • 1
    In the present situation, the other 4, really.2012-04-30
  • 0
    @Didier thank you. I was struggling to find 7 more choices but they are not really there. There are only 3 more to check.2012-04-30
  • 1
    You already checked `121`. Remain `111`, `112`, `212` and `211` (making 4 (not 3) more to check). When more experienced, you will see that `xxy` and `xyy` cannot be counterexamples to transitivity (can you show why?). Which would leave `121` (already checked) and `212`, and... nothing else.2012-04-30