The number of relations on the set $A = \{1, 2, 3\}$ containing at most 6 elements including $(1, 2)$, which are reflexive and transitive but not symmetric, is _____

Step 1: Understand the properties of the relation

We are given a set $A = \{1, 2, 3\}$. We need to find the number of relations $R$ on $A$ that satisfy several conditions: it must be reflexive, transitive, not symmetric, contain the element $(1, 2)$, and have at most 6 elements.

Step 2: Apply reflexivity condition

For a relation $R$ on set $A$ to be reflexive, every element in $A$ must be related to itself. Therefore, the pairs $(1{,}1)$, $(2{,}2)$, and $(3{,}3)$ must be in $R$. These are 3 elements.

Step 3: Apply the given element condition

The problem states that the relation $R$ must include the element $(1{,}2)$. This is an additional element to the reflexive pairs.

Step 4: Apply transitivity condition

Since $(1{,}2) \in R$ and $(2{,}2) \in R$, by transitivity, $(1{,}2)$ must be in $R$, which is already established. Similarly, $(1{,}1) \in R$ and $(1{,}2) \in R$ implies $(1{,}2) \in R$. No new elements are forced by transitivity with just $(1{,}1), (2{,}2), (3{,}3), (1{,}2)$ present.

Step 5: Apply non-symmetry condition

For the relation to be not symmetric, since $(1{,}2) \in R$, it must be that $(2{,}1) \notin R$. If $(2{,}1)$ were in $R$, then the relation would be symmetric with respect to $(1{,}2)$ and $(2{,}1)$.

Step 6: Consider possible additional elements

We currently have 4 elements: $(1{,}1), (2{,}2), (3{,}3), (1{,}2)$. The relation must have at most 6 elements, meaning we can add at most 2 more elements. The pairs $(2{,}1)$ is forbidden. The remaining pairs to consider are $(1{,}3), (2{,}3), (3{,}1), (3{,}2)$. We need to check transitivity for each case.

Step 7: Evaluate cases for adding elements

Let's analyze the possible relations: 1. $R_1 = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2)\}$: Reflexive, contains $(1{,}2)$, not symmetric (since $(2{,}1) \notin R_1$), transitive. This is a valid relation. 2. If we add $(1{,}3)$: $R_2 = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (1{,}3)\}$. Reflexive, contains $(1{,}2)$, not symmetric (since $(2{,}1) \notin R_2$ and $(3{,}1) \notin R_2$), transitive. This is valid. 3. If we add $(2{,}3)$: $R_3 = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3)\}$. Reflexive, contains $(1{,}2)$, not symmetric (since $(2{,}1) \notin R_3$ and $(3{,}2) \notin R_3$). Transitivity: $(1{,}2) \in R_3$ and $(2{,}3) \in R_3 \implies (1{,}3) \in R_3$. So, $R_3$ must contain $(1{,}3)$ to be transitive. But then it would have 6 elements: $\{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3)\}$. This is $R_4$. If we only add $(2{,}3)$ and not $(1{,}3)$, it's not transitive. 4. If we add $(3{,}1)$: $R_5 = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (3{,}1)\}$. Transitivity: $(3{,}1) \in R_5$ and $(1{,}2) \in R_5 \implies (3{,}2) \in R_5$. So $R_5$ must contain $(3{,}2)$. Also, $(1{,}2) \in R_5$ and $(2{,}2) \in R_5 \implies (1{,}2) \in R_5$. $(3{,}1) \in R_5$ and $(1{,}1) \in R_5 \implies (3{,}1) \in R_5$. If $(3{,}1)$ is added, $(3{,}2)$ must also be added for transitivity. This would make 6 elements: $\{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (3{,}1), (3{,}2)\}$. This relation is not symmetric (since $(1{,}3) \notin R_5$ and $(2{,}3) \notin R_5$). This is a valid relation. 5. If we add $(3{,}2)$: $R_6 = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (3{,}2)\}$. Transitivity: $(3{,}2) \in R_6$ and $(2{,}2) \in R_6 \implies (3{,}2) \in R_6$. $(1{,}2) \in R_6$ and $(2{,}2) \in R_6 \implies (1{,}2) \in R_6$. No new elements are forced. This relation is not symmetric (since $(2{,}3) \notin R_6$). This is a valid relation. Let's list the valid relations with at most 6 elements: - $R_A = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2)\}$ (4 elements) - $R_B = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (1{,}3)\}$ (5 elements) - $R_C = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (2{,}3), (1{,}3)\}$ (6 elements, forced by transitivity from $(1{,}2)$ and $(2{,}3)$) - $R_D = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (3{,}2)\}$ (5 elements) - $R_E = \{(1{,}1), (2{,}2), (3{,}3), (1{,}2), (3{,}1), (3{,}2)\}$ (6 elements, forced by transitivity from $(3{,}1)$ and $(1{,}2)$) We need to ensure no other elements are forced by transitivity that would make the relation symmetric or exceed 6 elements. Consider $R_C$: $(1{,}2) \in R_C$ and $(2{,}3) \in R_C \implies (1{,}3) \in R_C$. All pairs are present. Not symmetric because $(2{,}1) \notin R_C$, $(3{,}1) \notin R_C$, $(3{,}2) \notin R_C$. Consider $R_E$: $(3{,}1) \in R_E$ and $(1{,}2) \in R_E \implies (3{,}2) \in R_E$. All pairs are present. Not symmetric because $(1{,}3) \notin R_E$, $(2{,}1) \notin R_E$, $(2{,}3) \notin R_E$. So there are 5 such relations.

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 →