Definition of transitivity of relations

312 Views Asked by At

We are currently learning about transitivity, and my teacher gave us the following definition: For some binary relation $R$ of type $A^2$ (so $R \subseteq A^2$ holds): $$R \ \text{is transitive} \triangleq \forall a,c \in A ( \ \exists b \in A ( \ (aRb \wedge bRc) \implies aRc \ ) \ )$$

But online, I instead find the following definition: $$R \ \text{is transitive} \triangleq \forall a,b,c \in A ( \ (aRb \wedge bRc) \implies aRc \ )$$

These are equivalent to each other? But I don't quite (intuitively) get how so. Does that then generalise to this? $$\forall a,b,c( \ P(a,b,c) \ ) \iff \forall a,c ( \ \exists b( \ P(a,b,c) \ ) \ )$$

If so, is there a proof for it?

1

There are 1 best solutions below

3
On BEST ANSWER

The two are not equivalent, and your teacher's (EDIT: per the OP's comment below, they miscopied the definition) proposed definition is wrong. In particular, the property your teacher describes is automatically satisfied as soon as there is some element not related to anything (take this as your $b$, regardless of what $a$ and $c$ are).

If you move parentheses, though, you do get an equivalent definition, namely $$\forall a,c[\exists b(aRb\wedge bRc)\implies aRc].$$ Note that here the parentheticals following the existential quantifier do not contain the implication! I suspect that this is what your teacher meant, or that this is what your teacher actually wrote and you miscopied (either is plausible, it's an easy mistake to make). The equivalence here follows from writing the implication as a disjunction and remembering that $\exists$ is the same as $\neg\forall\neg$.