First, a direct proof.
- Our goal is a conditional statement, namely
xRy and yRz --> xRz , for all x, y, z.
Strategy : let x, y, z be any arbitrary objects ( this will allow generalization at the end of the proof) and assume the antecedent of the conditional ( namely : xRy and yRz) ; under this hypothesis, derive the consequent ( namely : xRz); finally generalize ( on account of the fact that you started with arbitrary objects).
Let x, y, z be any arbitrary objects.
Suppose that : xRy and yRz is true.
This implies that x = a, y= b, y = a and z = b. ( The reason is that the only way for an ordered pair to belong to R is to be identical to the ordered pair (a,b) ) .
Now , since ( under our assumption) x = a and z = b, this means that (x,z) = (a,b), and consequently, that (x,z) belongs to R ( or, if you prefer, that xRz is true) as desired.
So , IN CASE ( xRy and yRz) , WE HAVE xRz.
But x, y, z were arbitrary. This allows us to generalize as follows :
for all x, y, z ( IF xRy and yRz THEN xRz)
which means that R is a transitive relation.
Negating R's transitivity amounts to an existential statement . But it appears impossible to find a consistent interpretation of the variables that makes true the whole statement. Hence the conclusion according to which R must be transitive.
- Saying that R is transitive amounts to saying that :
(1) For all x, y, z ( both (x,y) and (y,z) belong to R --> (x,z)
belongs to R).
- Saying that R is not transitive amounts therefore to saying that :
(2) for some x, y , z [ ~ ( both (x,y) and (y,z) belong to R -->
(x,z) belongs to R)]
Note : One obtains (2) by applying three times to (1) the predicate logic rule according to which :
" ~ ( for all v, P(v) )" is equivalent to " for some v, ~ P(v) "
( with " v" being any variable, and "P(v)" any open sentence).
Proposition (2) contains the negation of a conditional. In general, the negation of ( X --> Y) is equivalent to ( X & ~Y).
Applying this to (2) yields :
(3) for some , x, y, z [ both (x,y) AND ( y,z) belong to R AND (x,z) does not belong to R]
Proposition (3) contains a conjunction of 3 conjuncts. In order a conjunction to be true, all its conjuncts have to be true at the same time.
Let's consider in particular the two first ones.
Can one find some x, y, z such that both "(x,y) belong to R" and " (y,z) belong to R" are true?
In order "(x,y) belong to R" to be true,
x must be equal to a
y must be equal to b.
And in order " (y,z) belong to R" to be true
y must be equal to a
z must be equal to b.
Therefore, ( combining there 4 equalities) proposition (3) is true for some x,y,z only if
(4) x = a = y= b = z.
Now, the third conjunct ( namely" ~ (x,z) belong to R") is true if and
only if x is not equal to a OR z is not equal to b.
But this is not consistant with (4) which says that x = a and that z = b.
Conclusion : there is no possible interpretation of x, y, z which can make true proposition (3) . Since it is impossible to negate R's transitivity, R must be transitive.