What is the correct answer for why the relation $R = \{(1,1),(2,2),(3,3),(1,2)\}$ on the set $A = \{1,2,3\}$ is transitive?

Question

$$A = \{1,2,3\}$$

$$R = \{(1,1),(2,2),(3,3),(1,2)\}$$

I've seen two ways to say that the relation is transitive.

Explicit Truth

In the given relation we have $(1,1)$ and $(1,2)$ in $R. (1,2) $ should be in $R$ which it is. Similarly, we have $(1,2)$ and $(2,2)$ in $R. (1,2)$ should be in $R$ which it is. Therefore, for all $(a,b)$ and $(b,c)$ in $R$ then $(a,c)$ is also in $R$.

Vacuous Truth

There exists no $(a,b)$ and $(b,c)$ such that $(a,c)$ cannot be in $R$. The antecedent is not satisfied so the statement is assumed to be vacuously true.

Which one is correct or are both correct?

Answer 1

Neither is correct. The explicit truth version does not address the reflexive case, (1, 1) in R, etc.

The Vacuous truth version is also insufficient. To prove something does not exist technically, we would have to list all possibilities and show that none of them meet the criteria. Your vacuous truth attempt "begs the question" instead of justifying why it does not exist. See note A below.

Definition of Transitive Relations:

When $(a, b) \in R$ and $(b, c) \in R, (a, c) \text{ must also be in } R$

To prove R is transitive, show this property holds.

Proof:
For any choice of a, let $b = a$.
$(a,a) \text { is } \in R \text{ which implies }(a, b) = (a, a) \in R$

Moreover, $(1, 1) \in R \text{ and }(1,2) \in R$. However, $(1, 2) \in R.$
Likewise, $(1, 2) \in R \text{ and }(2,2) \in R$. However, $(1, 2) \in R.$

These are the only pairs of ordered pairs which satisfy the hypothesis for transitivity. All these ordered pairs are transitive therefore the relation is transitive. Tadahhh!

Note A: Technically, my conclusion also assumes all the possibilities have been covered. In practice, particularly for most undergraduate courses the reasoning I gave is considered sufficient. An abstract algebra course would require much more thoroughness.

Answer 2

Neither is correct. $R$ is transitive if whenever $(a,b)$ and $(b,c)$ are in $R$ then $(a,c)$ is in $R$. To determine if this holds for the $R$ given, we need to do something like the following:

Step 1. Find $T=\{(a_1,a_2,a_3) \in A^3: (a,b) \in R, (b,c)\in R\}$. Note that if $p\colon A^3 \to A^2$ given by $p(a_1,a_2,a_3)= (a_1,a_2)$, then $p(T) = R$, and we can use this to compute $$ T = \{(1,1,1), (2,2,2), (3,3,3), (1,1,2), (1,2,2)\} $$ Step 2. Let $q\colon A^3 \to A^2$ be the map $q(a_1,a_2,a_3) = (a_1,a_3)$. Then $R$ is transitive if $q(T)\subseteq R$. In our case, $q(T) = \{(1,1),(2,2),(3,3),(1,2)\} = R$, so $R$ is indeed transitive.

The "explicit truth" gives an incomplete proof: in terms of the above, it essentially shows that $(1,1,2)$ and $(1,2,2)$ are elements of $T$ but does not compute all of $T$.

The "vacuous truth" simply asserts that $\neg(\neg(\mathrm{transitive}))$ is true for $R$, which is equivalent to asserting that $R$ is transitive, but does not prove anything about $R$.