How do you figure out what relations of $A \times A$ are not transitive?

Question

I have found all 16 relations on a two element set. But now I can not find the ones which are not transitive. I dont know how ($xRy \land yRz) \implies xRz$ relates to this conversation.

This should be obvious because some relations in this context have $x,y,z,w$ elements.

Any help would be tremendously appreciated.

Answer 1

I don't know how $(xRy∧yRz)⟹xRz$ relates to this conversation.

It is $\forall x\,\forall y\,\forall z\;\Big(\big(x\mathop Ry\wedge y\mathop Rz\big) \to x\mathop Rz\Big)$.

Transitivity is the claim that if there is some indirect relationship from one entity ($x$) to another entity ($z$), through some bridge ($y$), then there must be a direct relationship.

It's not a matter of finding cases that satisfy this condition, just that no case can be found to falsify it.

Another way to express transitivity is that: $$\neg\,\exists x\,\exists y\,\exists z\;\Big(\big(x\mathop Ry\wedge y\mathop Rz\big)\wedge\neg x\mathop Rz\Big)$$

So if you can find any such indirect relationship but cannot find a corresponding direct relationship, then the entire relation is not transitive.

Only if you can demonstrate that no such counterexample exists can you claim transitivity.

Answer 2

The relation $\{(a_1,a_2), (a_2,a_1)\}$ is not transitive. We can prove this by contradiction: assume the relation is transitive. We have that $a_1\sim a_2$, and that $a_2\sim a_1$. This means that by transitivity, we must have that $a_1\sim a_1$. But we don't. This is a contradiction, so the above relation is not transitive.

Answer 3

Suppose $R$ is not transitive.Equivalently, for some $a,b,c$ we have $(a,b)\in R \wedge (b,c)\in R\wedge (a,c)\not \in R.$ If you put $a=b$ or $b=c$ into this you get a contradiction. So $a \ne b\wedge b\ne c$. Since $a,b,c$ belong to $\{x,y\}$ with $x\ne y$ this gives, equivalently, (i) $(x,y)\in R\wedge (y,x)\in R\wedge (x,x)\not \in R$ or (ii) $(y,x)\in R\wedge (x,y)\in R\wedge (y,y)\not \in R$. That is, $(x,y)$ and $(y,x)$ both belong to $R$ and at least one of $(x,x),(y,y)$ does not. In all, $3$ non-transitive binary relations on $\{x,y\} $ : $R_1=A , R_2=A\cup \{(x,x)\}, R_3=A\cup \{(y,y)\}$ where $A=\{(x,y),(y,x)\}.$