Doubt about the logic defining transitivity of a relation

170 Views Asked by At

Kindly, correct me where I am wrong.
Modified(11:50 AM, 26 March 20): [ for all a, b, c ∈ X ]
Let us define P: $(a, b), (b, c)∈R$ ; and Q: $(a, c)∈R$;
[A] When P is true:

  1. P is true, Q is true: Relation is TRANSITIVE.
  2. P is true, Q is false: Relation is NOT TRANSITIVE.

[B] When P is false
Now, I am going to deal with the condition P is false in this way.
Consider the first case, (P is true and Q is true) $\implies$ Relation is TRANSITIVE.
Then, the negation of this will be (P is false or Q is false) $\implies$ Relation is NOT TRANSITIVE.
This implies that the condition P is false is enough to say that the relation is NOT TRANSITIVE.
Is my argument valid?

1

There are 1 best solutions below

11
On

No, your argument is wrong because in your analysis of the notion of transitivity you omitted quantifiers and you destroyed the conditional (if... then) structure of the definition.

A binary relation $R$ (over a set $A$) is transitive when, for every $a, b, c \in A$, one has that $(a,b) \in R$ and $(b,c) \in R$ imply $(a,c) \in R$.

What is the negation of the condition above? We have to negate the universal quantifier and the implication! So, the relation $R$ is not transitive when there exist $a,b,c \in A$ such that $(a,b) \in R, \, (b,c) \in R$ and $(a,c) \notin R$.

Therefore, to prove that $R$ is transitive you have to take all possible $a,b,c\in A$ (not necessarily distinct) and check that if $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R$. Note that in the particular case where $(a,b) \notin R$ or $(b,c) \notin R$ the implication "if $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R$" is vacuously true. But you have to check that the implication "if $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R$" holds for all $a, b, c \in A$ to conclude that $R$ is transitive.


Some errors in your analysis are the following:

  1. Since you omitted quantifiers, you say that, given some $a, b, c \in A$, if you have that $(a,b) \in R$ and $(b,c) \in R$ and $(a,c) \in R$ then $R$ is transitive (case 1 in your analysis). This is wrong, because you have shown this just for some $a,b,c \in A$, not for all $a, b, c \in A$.

  2. Concerning your analysis in the case B, you misunderstand the meaning of the implication. In propositional logic, if you are in a situation where $P$ and $Q$ are both true, then the implication $P \to Q$ is true but it does not mean that in all the other situations the implication $P \to Q$ is false. For instance, $P \to Q$ is true also when $P$ and $Q$ are both false.