Transitivity

To define transitivity in terms of graphs we need the notions of a broken journey and a short cut. There is a broken journey from dot x to dot z via dot y, just if there is an arrow from x to y, and an arrow from y to z. (Note that dot x might be the same as dot y, and dot y might be the same as dot z; so if Raa and Rab, there is a broken journey from a to b via a. And if Raa  there is a broken journey from a to a via a.)

There is a short cut just if there is an arrow direct from x to z. So if Rab and Rbc and also Rac, we have a broken journey from a to c via b, together with a short cut. And if Raa and Rab there is a broken journey from a to b via a together with a short cut.) Now we can define transitivity.

Rxy is transitive just if there is no broken journey in its graph without a short cut.

That is:

            Rxy is transitive just if "x"y"z[[RxyÙRyz]®Rxz]

or, equivalently,

            Rxy is transitive just if ¬$x$y$z[[RxyÙRyz]Ù¬Rxz].

Examples: "x=y"; "x>y"; "x³y"; "x is an ancestor of y".

Rxy is intransitive just if there is no broken journey in its graph with a short cut.

That is:

            Rxy is intransitive just if "x"y"z[[RxyÙRyz]®¬Rxz]

or, equivalently,

            Rxy is intransitive just if ¬$x$y$z[[RxyÙRyz]ÙRxz].

Examples: "x=y+1"; "x is the mother of y".

Rxy is non-transitive just if it is neither transitive nor intransitive; i.e. just if there is at least one broken journey with a short cut and at least one without.

That is:

Rxy is non-transitive just if [$x$y$z[[RxyÙRyz]ÙRxz]Ù$x$y$z[[RxyÙRyz]Ù¬Rxz]].

Examples: "¬x=y" (in a domain with at least two things in it); "x is a brother or sister of y" in suitable domains. (Don't be caught out by this! Remember that it may be that John is a brother or sister of Mary and Mary of John, but John will not be his own bother or sister.)

Again a relation may be both transitive and intransitive. It will be if the domain is empty; it will also be if the relation is empty; but it may be both even though the relation is not empty. This will be the case if there are some arrows but no broken journeys. In that case there will be no broken journeys with short cuts (so the relation will be intransitive) and none without (so it will be transitive). Again one can see this when one expresses things formally. To say that there are no broken journeys is to say that ¬$x$y$z[RxyÙRyz]. But in that case it follows that ¬$x$y$z[[RxyÙRyz]ÙRxz] (so Rxy is intransitive) and also that ¬$x$y$z[[RxyÙRyz]Ù¬Rxz] (so Rxy is transitive).

An example of a relation which is both transitive and intransitive is "x is the husband of y", since (of course), if a is b's husband, b can't be anyone's husband.