Let $A=\{1{,}2{,}3\}$. Then show that the number of relations containing $(1{,}2)$ and $(2{,}3)$ which are reflexive and transitive but not symmetric is three.

Step 1: Define Reflexive Property

A relation $R$ on a set $A$ is reflexive if every element in $A$ is related to itself. For the given set $A=\{1{,}2{,}3\}$, this means the pairs $(1{,}1)$, $(2{,}2)$, and $(3{,}3)$ must be present in any reflexive relation.

Step 2: Define Transitive Property

A relation $R$ is transitive if, whenever there is a path from $a$ to $b$ and from $b$ to $c$, there must also be a direct path from $a$ to $c$. Given $(1{,}2) \in R$ and $(2{,}3) \in R$, transitivity implies $(1{,}3) \in R$.

Step 3: Define Symmetric Property

A relation $R$ is symmetric if for every pair $(a,b)$ in $R$, the reverse pair $(b,a)$ is also in $R$. We are looking for relations that are NOT symmetric, meaning there must be at least one pair $(a,b)$ such that $(a,b) \in R$ but $(b,a) \notin R$.

Step 4: Identify Mandatory Elements

Based on reflexivity, $(1{,}1), (2{,}2), (3{,}3)$ must be in $R$. The problem states $(1{,}2)$ and $(2{,}3)$ are in $R$. By transitivity, since $(1{,}2) \in R$ and $(2{,}3) \in R$, it implies $(1{,}3) \in R$. These are the minimum elements required.

Step 5: Construct Relations and Check Conditions

Let $R_0 = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3)\}$. We need to add elements to $R_0$ such that the relation remains reflexive and transitive, but becomes non-symmetric. The pairs that could potentially be added are $(2{,}1)$, $(3{,}1)$, $(3{,}2)$. 1. $R_0$: Reflexive and transitive. Not symmetric because $(1{,}2) \in R_0$ but $(2{,}1) \notin R_0$. This is one such relation. 2. Consider adding $(2{,}1)$: If $(2{,}1)$ is added, then $(1{,}2) \in R$ and $(2{,}1) \in R$. Also $(2{,}3) \in R$ and $(3{,}1) \in R$ (from $R_0$). Transitivity would require $(1{,}1)$, $(2{,}2)$, $(3{,}3)$ (already there). Also $(2{,}3)$ and $(3{,}1)$ implies $(2{,}1)$ (already added). $(1{,}2)$ and $(2{,}3)$ implies $(1{,}3)$ (already there). $(2{,}1)$ and $(1{,}3)$ implies $(2{,}3)$ (already there). If $(2{,}1)$ is added, then $(1{,}2)$ and $(2{,}1)$ are present, making it symmetric for these pairs. To maintain non-symmetry, we must ensure $(3{,}1)$ or $(3{,}2)$ are not added if their symmetric counterparts are not. If we add $(2{,}1)$, then $(1{,}2)$ and $(2{,}1)$ are present. If we don't add $(3{,}1)$ and $(3{,}2)$, then $(1{,}3)$ is present but $(3{,}1)$ is not, so it's not symmetric. This forms a valid relation. 3. Consider adding $(3{,}1)$: $R_1 = R_0 \cup \{(3{,}1)\}$. Reflexive and transitive. Not symmetric because $(1{,}2) \in R_1$ but $(2{,}1) \notin R_1$. This is a second relation. 4. Consider adding $(3{,}2)$: $R_2 = R_0 \cup \{(3{,}2)\}$. Reflexive and transitive. Not symmetric because $(1{,}2) \in R_2$ but $(2{,}1) \notin R_2$. This is a third relation. 5. Consider adding $(2{,}1)$ and $(3{,}1)$: $R_3 = R_0 \cup \{(2{,}1), (3{,}1)\}$. Transitivity: $(3{,}1) \in R_3$ and $(1{,}2) \in R_3 \implies (3{,}2) \in R_3$. So we must add $(3{,}2)$. Then $R_3 = R_0 \cup \{(2{,}1), (3{,}1), (3{,}2)\}$. Now, $(1{,}2)$ and $(2{,}1)$ are present. $(1{,}3)$ is present, $(3{,}1)$ is present. $(2{,}3)$ is present, $(3{,}2)$ is present. This relation is symmetric. So this is not a valid relation. 6. Consider adding $(2{,}1)$ and $(3{,}2)$: $R_4 = R_0 \cup \{(2{,}1), (3{,}2)\}$. Transitivity: $(3{,}2) \in R_4$ and $(2{,}1) \in R_4 \implies (3{,}1) \in R_4$. So we must add $(3{,}1)$. This again leads to a symmetric relation. 7. Consider adding $(3{,}1)$ and $(3{,}2)$: $R_5 = R_0 \cup \{(3{,}1), (3{,}2)\}$. Reflexive and transitive. Not symmetric because $(1{,}2) \in R_5$ but $(2{,}1) \notin R_5$. This is a fourth relation. Let's re-evaluate the possible relations systematically: Base relation $R_{base} = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3)\}$. Possible pairs to add (excluding those that would make it symmetric for $(1{,}2)$, $(2{,}3)$, $(1{,}3)$): $(2{,}1)$, $(3{,}1)$, $(3{,}2)$. Case 1: No additional pairs. $R_1 = R_{base}$. - Reflexive: Yes. - Transitive: Yes (checked in step 4). - Symmetric: No, because $(1{,}2) \in R_1$ but $(2{,}1) \notin R_1$. (Valid) Case 2: Add $(2{,}1)$. $R_2 = R_{base} \cup \{(2{,}1)\}$. - Reflexive: Yes. - Transitivity check: $(2{,}1) \in R_2$ and $(1{,}3) \in R_2 \implies (2{,}3) \in R_2$ (already present). $(3{,}1)$ is not present, so $(3{,}2)$ is not forced. $(1{,}2)$ and $(2{,}1)$ are present. $(1{,}3)$ is present, but $(3{,}1)$ is not. So it is transitive. - Symmetric: No, because $(1{,}3) \in R_2$ but $(3{,}1) \notin R_2$. (Valid) Case 3: Add $(3{,}1)$. $R_3 = R_{base} \cup \{(3{,}1)\}$. - Reflexive: Yes. - Transitivity check: $(3{,}1) \in R_3$ and $(1{,}2) \in R_3 \implies (3{,}2) \in R_3$. So we must add $(3{,}2)$. - This leads to $R_3' = R_{base} \cup \{(3{,}1), (3{,}2)\}$. - Symmetric: No, because $(1{,}2) \in R_3'$ but $(2{,}1) \notin R_3'$. (Valid) Case 4: Add $(3{,}2)$. $R_4 = R_{base} \cup \{(3{,}2)\}$. - Reflexive: Yes. - Transitivity check: $(1{,}2) \in R_4$ and $(2{,}3) \in R_4 \implies (1{,}3) \in R_4$. $(3{,}2) \in R_4$ and $(2{,}3) \in R_4$ does not force anything new. $(1{,}3)$ is present, but $(3{,}1)$ is not. $(2{,}3)$ is present, but $(3{,}2)$ is present. $(1{,}2)$ is present, but $(2{,}1)$ is not. So it is transitive. - Symmetric: No, because $(1{,}2) \in R_4$ but $(2{,}1) \notin R_4$. (Valid) Let's list the relations that satisfy the conditions: 1. $R_A = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3)\}$ - Reflexive: Yes - Transitive: Yes - Symmetric: No (e.g., $(1{,}2) \in R_A$ but $(2{,}1) \notin R_A$) 2. $R_B = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3), (2{,}1)\}$ - Reflexive: Yes - Transitive: Yes (e.g., $(2{,}1) \in R_B$ and $(1{,}3) \in R_B \implies (2{,}3) \in R_B$, which is present) - Symmetric: No (e.g., $(1{,}3) \in R_B$ but $(3{,}1) \notin R_B$) 3. $R_C = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3), (3{,}1), (3{,}2)\}$ - Reflexive: Yes - Transitive: Yes (e.g., $(3{,}1) \in R_C$ and $(1{,}2) \in R_C \implies (3{,}2) \in R_C$, which is present) - Symmetric: No (e.g., $(1{,}2) \in R_C$ but $(2{,}1) \notin R_C$) These are the three relations that satisfy all conditions.

More from this chapter

• Show that an onto function f:1,2,3 →1,2,3 is always one-one.
• Let A=-2,-1,0,1,2,3. Define a relation R on A by xRy if and only if y=max(x,1). If l is the number of elements in R, and m and n are the minimum numbers of orde
• 32. Show that f: R -> R defined as f(x) = x / sqrt(1 + x²) is one-one but not onto. (function, one-one, onto, real numbers, domain, codomain, range)
• Let A be the set of all students of a boys school. Show that the relation R in A given by R=(a, b): a is sister of b is the empty relation and R^()=(a, b): the
• Consider the identity function I_N: N → N defined as I_N(x)=x x N. Show that although I_N is onto but I_N+I_N: N → N defined as (I_N+I_N)(x)=I_N(x)+I_N(x)=x+x=2
• Prove that the relation R in the set A = 1, 2, 3, 4, 5 given by R = (a, b): |a - b| is even is an equivalence relation.
• Let f(x) = log_e x and g(x) = (x^4 - 2x³ + 3x² - 2x + 2)/(2x² - 2x + 1). Then the domain of f ° g is
• Let the domain of the function f(x) = cos^(-1) ( (4x + 5)/(3x - 7)) be [α, β] and the domain of g(x) = log_2(2 - 6log_7(2x + 5)) be [, ]. Then |7(α + β) + 4( +)

All Relations and Functions solutions →