Is this relation $R$ over $A$ transitive?$$A=\{1,2,3\}$$ $$R=\{(1,2),(1,1),(2,1),(2,2)\}$$

Since from the definition a relation is transitive if $\forall x,y,z\in A (xRy,yRz\to xRz)$, so since $3$ isn't in the relation then it isn't transitive?

  • 2
    $\begingroup$ Actually the "etc" is important and your reasoning is false. $\endgroup$ – user2345215 Jan 20 '15 at 18:04
  • $\begingroup$ If $\neg(xRy \land yRz)$ then the statement is vacuously true on $x,y,z$, so that reasoning doesn't work $\endgroup$ – GFauxPas Jan 20 '15 at 18:06
  • $\begingroup$ @user2345215 ok I added it, I still don't see how it's transitive. Just like it isn't reflexive since $3,3$ isn't in the relation. $\endgroup$ – shinzou Jan 20 '15 at 18:06
  • 1
    $\begingroup$ To prove non-transitivity you need to exhibit a specific trio $x,y,z$ such that $xRy$ and $yRz$ but not $xRz$. Can you do that? $\endgroup$ – Steven Stadnicki Jan 20 '15 at 18:07
  • $\begingroup$ @kuhaku Now observe that the implication is always true if the assumption is false. $\endgroup$ – user2345215 Jan 20 '15 at 18:08

This relation is transitive. 3 doesn't play any role here since you don't require a transitive relation to be full. Observe that the transitivity here means: $$(1,2)\wedge(2,1)\in R\Rightarrow(1,1)\in R \\(2,1)\wedge(1,2)\in R\Rightarrow(2,2)\in R$$ and these are found in the relation so it's transitive. In fact that's equivalence relation on $\{1,2\}$ (since it's also reflexive and symmetric there).

EDIT: We can justify my remark by definitions ($T$ is the set on which the relation $R$ is defined):

  • Reflexivity means $\forall x\in T,(x,x)\in R$ - In our case $(1,1),(2,2)\in R$
  • Symmetry means $xRy\Leftrightarrow yRx$. It doesn't mean that the relation is full. In our case $(1,2)\in R\wedge (2,1)\in R$. Trivially $(1,1),(2,2)\in R$.

So for these reasons it's an eqivalence relation on $T=\{1,2\}$.

  • $\begingroup$ So symmetry doesn't have to be full either? Is the relation in my question also symmetric? $\endgroup$ – shinzou Jan 20 '15 at 18:12
  • $\begingroup$ @kuhaku YES!!!! $\endgroup$ – D Wiggles Jan 20 '15 at 18:15
  • $\begingroup$ @kuhaku See my edit please. $\endgroup$ – user65985 Jan 20 '15 at 18:17
  • $\begingroup$ Yes it's easy to see that it's an equivalence relation on $\{1,2\}$ since it's full, but it's just symmetric and transitive on $\{1,2,3\}$? $\endgroup$ – shinzou Jan 20 '15 at 18:20
  • $\begingroup$ Checking transitive is more than just those two. For example $(1,2)\wedge(2,2)\in R\Rightarrow(1,2)\in R$ $\endgroup$ – GEdgar Jan 20 '15 at 18:33

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.