Is one tuple set transitive relation?

Question

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$} *

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.)