Is this relation transitive? I think it is.

31 Views Asked by At

A={a,b,c,d}

R={(a,b),(a,c),(c,b)}

According to the definition for transitive relation, if there is (a,b) and (b,c) there should be (a,c)

In the above relation there is (a,c),(c,b) as well as (a,b). Shouldn't it be transitive?

2

There are 2 best solutions below

0
On

Yes, your relation is transitive (and your argument is correct).

0
On

Incidentally, if the concern was whether you caught all possible cases where $x \mathrel{R} y$ and $y \mathrel{R} z$ are both satisfied - a proof assistant might be able to help with that (and this is one sort of mundane case checking for which automated proof assistants excel). For example, in Coq:

Inductive A : Set :=
a | b | c | d.
Inductive R : A -> A -> Prop :=
| R1 : R a b
| R2 : R a c
| R3 : R c b.

Require Import RelationClasses.

Instance R_trans : Transitive R.
Proof.
intros x y z. inversion 1; inversion 1.
constructor.
Qed.