The number of relations, on the set [1,2,3] containing (1,2) and (2,3), which are reflexiv…

Question

The number of relations, on the set $$\{1,2,3\}$$ containing $(1,2)$ and $(2,3)$, which are reflexive and transitive but not symmetric, is \_\_\_\_\_\_\_\_\_\_.

Answer: 3

Accepted Answer

To find the number of such relations, let's first understand what it means for a relation to be reflexive, transitive, and not symmetric.

A relation $R$ on a set $S$ is reflexive if every element is related to itself. That is, $(a,a)\in R$ for all $a\in S$.

A relation is transitive if whenever $(a,b)\in R$ and $(b,c)\in R$, then it must also be the case that $(a,c)\in R$.

A relation is symmetric if whenever $(a,b)\in R$, then $(b,a)\in R$ also.

Since we are looking for relations that are reflexive and transitive but not symmetric, we will need to include certain elements and exclude others.

First, for the relation to be reflexive on the set ${1,2,3}$, it must contain $(1,1),(2,2),$ and $(3,3)$.

Given that the relation must contain $(1,2)$ and $(2,3)$ and be transitive, it must also contain $(1,3)$ because if $(1,2)$ and $(2,3)$ are included, then to maintain transitivity, $(1,3)$ must be included as well.

So far, the must-have elements of the desired relation are:

For reflexivity: $(1,1),(2,2),(3,3)$

Given in the problem: $(1,2),(2,3)$

For transitivity (induced by given elements): $(1,3)$

"To maintain a relation that is reflexive, transitive, and not symmetric, we must carefully select additional pairs beyond the reflexive minimum $(1,1),(2,2),(3,3)$, and the given $(1,2),(2,3)$, which also necessitates $(1,3)$ due to transitivity. While including pairs such as $(2,1)$, $(3,1)$, or $(3,2)$ could potentially introduce symmetry, we can include some of these pairs as long as the resulting relation does not fulfill the condition for symmetry for all elements. This means we can include one or more of these pairs if doing so does not result in every pair being mirrored (i.e., for every $(a,b)\in R$, $(b,a)\in R$ is not required), thus keeping the relation not symmetric. The key is ensuring that the inclusion of any such pair does not lead to a situation where for every $(a,b)$ in the relation, the reverse $(b,a)$ also exists, which would make the relation symmetric, contradicting our requirement."

1. R1 = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)}

Here, none of (2,1), (3,2), (3,1) are in R1.

2. R2 = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3), (2,1)}

Here, only (2,1) is in R2, and neither (3,2) nor (3,1) are in R2.

3. R3 = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3), (3,2)}

Here, only (3,2) is in R3, and neither (2,1) nor (3,1) are in R3.

Solutions · 1