• The set $\{(1, 1), (2, 2), (3, 3), (4, 4)\}$ apparently is is transitive.

This confuses me as I thought set transitivity meant that if $(x,y)$ and $(y,z)$ then $(x,z)$

Wouldn't that mean that in order for this set to be transitive, it should contain $(1,2), (1,3), (1,4), (2,1), etc... $?

  • Another set $\{(1, 2), (2, 3), (3, 4)\}$ is said to be anti-symmetric.

I understood anty-symmetry as if $(x,y)$ and $(y,x)$ then $y=x$

Thus shouldn't $(1,2) = 1 = 2$ which isn't true?

  • $\begingroup$ For the first question, the condition you state is satisfied, since the set only consists of elements of the form $(x,x)$. Therefore, for any pairs $(x,y),(y,z)$ in the set, we have that $x=y=z$, hence $(x,z)=(x,y)$($=(x,x)$) which is in the set by assumption. For the second question, the condition is also satisfied, since for any $(x,y)$ in the set, $(y,x)$ is not in the set, so the statement is vacuously true. $\endgroup$ – Uncountable Jan 16 '17 at 22:37
  • $\begingroup$ To the first part of your question, the set is transitive in a trivial sense. For instance, "$(1,2)$ and $(2,3)$" would imply $(1,3)$, $(1,2) \wedge (2,3) \rightarrow (1,3)$. But $(1,2) \wedge (2,3)$ is false, therefore, trivially, $(1,2) \wedge (2,3) \rightarrow (1,3)$ is true. $\endgroup$ – bob.sacamento Jan 16 '17 at 22:37
  • 1
    $\begingroup$ Exactly: that's my point. The relation is transitive, unless there exists a counterexample, and there are no counter examples. Hence transitive. $\endgroup$ – Namaste Jan 16 '17 at 22:48
  • 1
    $\begingroup$ Yes, transitivity requires that for all x, y, z in the set on which the relation is defined, if $(x, y)$ and $(y, z)$ are in a relation, then $(x, z)$ must also be in the relation. In those relations in which there are no x, y, z such that $(x, y)$ and $(y, z)$, no worries. $\endgroup$ – Namaste Jan 16 '17 at 22:56
  • 1
    $\begingroup$ You're welcome, @Johny! $\endgroup$ – Namaste Jan 16 '17 at 23:01

Math definitions are highly literal. You can read it as "In every case that there is an (x,y) and a (y,z) there is a (x,z)". In your $\{(1,1), (2,2), \dots \}$ example the cases x,y and z all being equal which fulfills the requirement of the definition. Alternatively you can read it as there being no counterexamples.

In the second example you gave is antisemetric because while there is a $(1,2)$ there isn't a $(2,1)$. Both parts of an and must be fulfilled for it to matter.

  • $\begingroup$ I think I just have a major misconceptions about set properties. Take $(x,y)$ to be (1,1), how can we have $(y,z)$ since in the set defined previously $y = 1 $ $\endgroup$ – Johny Jan 16 '17 at 22:46
  • $\begingroup$ Is this the case? $\endgroup$ – Johny Jan 16 '17 at 22:55
  • $\begingroup$ Take $(x,y)$ to be $(1,1)$ and $(y,z)$ to be $(1,1)$ no one said that they had to be diffrent pairs. $\endgroup$ – Q the Platypus Jan 16 '17 at 23:04
  • $\begingroup$ @Johny: Also, if a relation has the property that, for every $(x,y)$ in the relation, there does not exist a $z$ such that $(y,z)$ is in the relation, then it's still transitive! Vacuous truth! $\endgroup$ – user14972 Jan 16 '17 at 23:11

Another way to formulate transitivity is as follows.

To any binary relation $R$, we can construct a ternary relation $S$ by

$$ S = \{ (x,y,z) \mid (x,y) \in R \wedge (y,z) \in R \} $$

By construction, if $(x,y,z) \in S$, it follows that $(x,y) \in R$ and $(y,z) \in R$. $R$ is a transitive relation if and only if $S$ has the additional property

If $(x,y,z) \in S$, then $(x,z) \in R$.


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.