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

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?

• Actually the "etc" is important and your reasoning is false. – user2345215 Jan 20 '15 at 18:04
• If $\neg(xRy \land yRz)$ then the statement is vacuously true on $x,y,z$, so that reasoning doesn't work – GFauxPas Jan 20 '15 at 18:06
• @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. – shinzou Jan 20 '15 at 18:06
• 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? – Steven Stadnicki Jan 20 '15 at 18:07
• @kuhaku Now observe that the implication is always true if the assumption is false. – 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\}$.

• So symmetry doesn't have to be full either? Is the relation in my question also symmetric? – shinzou Jan 20 '15 at 18:12
• @kuhaku YES!!!! – D Wiggles Jan 20 '15 at 18:15
• @kuhaku See my edit please. – user65985 Jan 20 '15 at 18:17
• 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\}$? – shinzou Jan 20 '15 at 18:20
• Checking transitive is more than just those two. For example $(1,2)\wedge(2,2)\in R\Rightarrow(1,2)\in R$ – GEdgar Jan 20 '15 at 18:33