1
$\begingroup$

I am wondering if a relationship with only one tuple e.g. {$(a,b)$} is transitive. If so, what about empty relation {$\emptyset$}.

We know that if a relation is transitive if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c) \in R$. I don't know how to use the definition to interpret my question. Please show me your thread.

We got only one tuple, and it seems does not fit in the definition. Appreciate for any help.

Updated notes: *Not sure about the notation of empty relation should be either $\emptyset$ or {$\emptyset$}. Undoubtedly, $\emptyset$ is an element of {$\emptyset$}, if $\emptyset$ still be a subset of every set in this case, e.g {$\emptyset$} *

$\endgroup$
2
$\begingroup$

Here's Yves Stalder's proof, written out in more detail, since you found his argument hard to follow. Suppose the relation $R=\{(a,b)\}$ contains two pairs $(u,v)$ and $(v,w)$; I need to show that it also contains $(u,w)$.

The fact that $(u,v)\in R=\{(a,b)\}$means that $(u,v)=(a,b)$, i.e., that $u=a$ and $v=b$. Similarly, from $(v,w)\in R$, we get that $v=a$ and $w=b$. In particular, $u=a$ and $w=b$, which means that $(u,w)=(a,b)$ and therefore $(u,w)\in R$.

(The hypotheses also imply that $a=b$ because $v$ equals both $a$ and $b$, but that information isn't needed for this proof.)

$\endgroup$
2
  • $\begingroup$ Thank you for your further clarification. "This implies a=b" is my confusion, as it adapts that one tuple has to be a reflexive element. Why isn't that important in this proof? $\endgroup$ – LJNG Dec 26 '19 at 12:21
  • $\begingroup$ (1) I've never seen a concept of "reflexive element". What is true in this direction is that, if a transitive relation consists os a dingle ordered pair, then the two components of that pair are equal. (2) The fact isn't important for this proof because the proof (the second paragraph of my answer) never used it. $\endgroup$ – Andreas Blass Dec 27 '19 at 20:18
1
$\begingroup$

The relation $R$ with one couple $(a,b)$ is transitive because, if we suppose $(u,v)\in R$ and $(v,w)\in R$, we have $u=a$, $a=v=b$, and $w=b$. This implies $(u,w)=(a,b)$, hence $(u,w)\in R$.

The empty relation $R=\emptyset$ is transitive, since the condition $$ \forall (u,v)\in R, \ \forall (v,w)\in R, \ (u,w) \in R $$ is trivially true. Indeed, its negation asserts that there exists a "counterexample", which is impossible since $R$ is empty.

$\endgroup$
1
  • $\begingroup$ Thank you for your help. I understand your empty relation reasoning, but still unclear with one tuple set. If the question has a further constraint, says a distinct element$a,b$ form a tuple {$(a,b)$}, then your reasoning seems a bit slide. $\endgroup$ – LJNG Dec 22 '19 at 11:08
1
$\begingroup$

There are quantifiers in the definition of transitivity \begin{equation} \forall (a, b)\in R, \forall (c, d)\in R, b = c \Rightarrow (a, c)\in R \end{equation} A logical proposition starting with $\forall x\in\emptyset$ is always true. There are no pairs of tuples $(a, b)$ and $(b, c)$ in $R$, hence transitivity is true.

Also note that a proposition starting with $\exists x\in\emptyset$ is always false. Indeed there is no element in the empty set, so there is no element in the empty set satisfying a property $P(x)$, hence the proposition $\exists x\in\emptyset, P(x)$ is always false. I don't think this property can be proved, the existence of the empty set is axiomatic.

Remark that the logical negation of the proposition $\forall x\in\emptyset, P(x)$ is the proposition $\exists x\in\emptyset,\neg P(x)$. Since the latter is false, the former must be true.

$\endgroup$
4
  • $\begingroup$ Thank you for your help. Would you please further enlighten me about the statement "A logical proposition starting with $\forall x \in R$ is always true but $\exists x \in R$ is false." $\endgroup$ – LJNG Dec 22 '19 at 10:59
  • $\begingroup$ I didn't say $R$, I said $\emptyset$ $\endgroup$ – Gribouillis Dec 22 '19 at 11:20
  • $\begingroup$ Sorry, it was a typo. I mean $\emptyset$ $\endgroup$ – LJNG Dec 22 '19 at 11:23
  • $\begingroup$ See my edits above $\endgroup$ – Gribouillis Dec 22 '19 at 11:32
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.