Key Concepts and Formulas

• Equivalence Relation Properties: A relation $R$ on a set $A$ is an equivalence relation if it is:
  • Reflexive: For all $a \in A$, $(a,a) \in R$.
  • Symmetric: For all $a, b \in A$, if $(a,b) \in R$, then $(b,a) \in R$.
  • Transitive: For all $a, b, c \in A$, if $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$.
• Smallest Equivalence Relation: The smallest equivalence relation containing a given set of pairs is formed by starting with the given pairs and reflexivity, and then systematically adding the minimum number of pairs required to satisfy symmetry and transitivity until no new pairs can be added.
• Equivalence Classes and Relation Size: An equivalence relation partitions the set $A$ into disjoint equivalence classes. If $C_1, C_2, \ldots, C_k$ are the equivalence classes of $A$, then the number of elements in the equivalence relation $R$ is given by $\sum_{i=1}^k |C_i|^2$.

Step-by-Step Solution

Let the given set be $A = \{1, 2, 3, 4\}$. We are looking for the smallest equivalence relation $R$ on $A$ such that $\{(1,2), (1,3)\} \subset R$.

Step 1: Ensure Reflexivity For $R$ to be an equivalence relation, it must be reflexive. This means that every element in the set $A$ must be related to itself. Therefore, we must include the pairs $(1,1), (2,2), (3,3), (4,4)$ in $R$. Let $R_0 = \{(1,1), (2,2), (3,3), (4,4)\}$.

Step 2: Incorporate Given Pairs We are given that $\{(1,2), (1,3)\}$ must be a subset of $R$. We add these pairs to our current relation. Let $R_1 = R_0 \cup \{(1,2), (1,3)\} = \{(1,1), (2,2), (3,3), (4,4), (1,2), (1,3)\}$.

Step 3: Ensure Symmetry For $R$ to be symmetric, if $(a,b) \in R$, then $(b,a)$ must also be in $R$. From $R_1$:

• Since $(1,2) \in R_1$, we must add $(2,1)$ to $R$.
• Since $(1,3) \in R_1$, we must add $(3,1)$ to $R$. The reflexive pairs are already symmetric. Let $R_2 = R_1 \cup \{(2,1), (3,1)\} = \{(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (2,1), (3,1)\}$.

Step 4: Ensure Transitivity For $R$ to be transitive, if $(a,b) \in R$ and $(b,c) \in R$, then $(a,c)$ must also be in $R$. We systematically check for missing transitive pairs using the elements in $R_2$.

• Consider $(2,1) \in R_2$ and $(1,3) \in R_2$. By transitivity, $(2,3)$ must be in $R$.
• Since $(2,3)$ is now in $R$, by symmetry, $(3,2)$ must also be in $R$.

Let's update our relation to include these new pairs: Let $R_3 = R_2 \cup \{(2,3), (3,2)\} = \{(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (2,1), (3,1), (2,3), (3,2)\}$.

Now, we must re-check transitivity with $R_3$ to ensure no further pairs are generated.

• $(1,2) \in R_3$ and $(2,3) \in R_3 \implies (1,3) \in R_3$ (already present).
• $(1,3) \in R_3$ and $(3,2) \in R_3 \implies (1,2) \in R_3$ (already present).
• $(2,3) \in R_3$ and $(3,1) \in R_3 \implies (2,1) \in R_3$ (already present).
• $(3,2) \in R_3$ and $(2,1) \in R_3 \implies (3,1) \in R_3$ (already present).
• All other combinations of pairs in $R_3$ that involve elements from $\{1,2,3\}$ and lead to a new pair are already present or are reflexive pairs. For example, $(1,1)$ and $(1,2)$ yields $(1,2)$.
• The element $4$ is only related to itself $(4,4)$. There are no pairs connecting $4$ to $1, 2,$ or $3$. Therefore, transitivity will not introduce any new pairs involving $4$ with other elements.

Since no new pairs are generated by applying the transitivity property to $R_3$, $R = R_3$ is the smallest equivalence relation containing the given pairs.

Step 5: Count the Elements in R The relation $R$ is: $R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (2,1), (3,1), (2,3), (3,2)\}$ The number of elements in $R$ is 10.

Alternatively, we can identify the equivalence classes formed by $R$.

• From the pairs involving 1, 2, and 3, we see that 1 is related to 1, 2, and 3. By symmetry and transitivity, 2 is related to 1, 2, and 3, and 3 is related to 1, 2, and 3. This forms one equivalence class: $C_1 = \{1, 2, 3\}$.
• The element 4 is only related to itself: $(4,4) \in R$. This forms another equivalence class: $C_2 = \{4\}$.

The set $A = \{1, 2, 3, 4\}$ is partitioned into $C_1$ and $C_2$. The number of elements in $R$ is the sum of the squares of the sizes of these equivalence classes: Number of elements in $R = |C_1|^2 + |C_2|^2 = (3)^2 + (1)^2 = 9 + 1 = 10$.

This matches the count of elements in $R$ derived directly.

Common Mistakes & Tips

• Forgetting Reflexivity: Always start by adding all reflexive pairs $(a,a)$ for every element in the set.
• Incomplete Transitivity Check: After adding new pairs due to symmetry or transitivity, always re-check if these new pairs, when combined with existing pairs, generate further transitive pairs. This process must continue until no new pairs can be added.
• Understanding Equivalence Classes: Recognize that an equivalence relation partitions the set into disjoint equivalence classes. The structure of the relation is entirely determined by these classes. The number of elements in the relation is the sum of the squares of the sizes of these classes.

Summary

The smallest equivalence relation $R$ on the set $\{1,2,3,4\}$ containing $\{(1,2), (1,3)\}$ is constructed by ensuring reflexivity, symmetry, and transitivity. This process leads to the relation $R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (2,1), (3,1), (2,3), (3,2)\}$. This relation partitions the set into two equivalence classes: $\{1,2,3\}$ and $\{4\}$. The total number of elements in $R$ is the sum of the squares of the sizes of these classes, which is $3^2 + 1^2 = 9 + 1 = 10$.

The final answer is $\boxed{10}$.