Key Concepts and Formulas

• Symmetric Relation: A relation $R$ on a set $A$ is symmetric if for all $a, b \in A$, $(a, b) \in R \implies (b, a) \in R$.
• Reflexive Relation: A relation $R$ on a set $A$ is reflexive if for all $a \in A$, $(a, a) \in R$.
• Counting Relations: For a set with $n$ elements, the total number of possible relations is $2^{n^2}$. The number of relations with specific properties can be found by counting the number of independent choices in their corresponding relation matrices.
• Inclusion-Exclusion Principle (Subtraction): The number of elements in set A that are not in set B is $|A| - |A \cap B|$. In this context, we want symmetric relations that are not reflexive, which is (Total Symmetric Relations) - (Symmetric AND Reflexive Relations).

Step-by-Step Solution

Step 1: Determine the size of the set and the structure of the relation matrix. The given set is $A = \{1, 2, 3, 4\}$. The number of elements is $n = |A| = 4$. A relation on this set can be represented by a $4 \times 4$ matrix where the entry $(i, j)$ is 1 if $(i, j)$ is in the relation, and 0 otherwise.

Step 2: Calculate the total number of symmetric relations on the set. A relation is symmetric if its relation matrix $M$ satisfies $M_{ij} = M_{ji}$ for all $i, j$. In a $4 \times 4$ matrix, there are $n=4$ diagonal elements ($M_{11}, M_{22}, M_{33}, M_{44}$) and $\frac{n(n-1)}{2} = \frac{4(3)}{2} = 6$ pairs of off-diagonal elements that must be equal (e.g., $M_{12}=M_{21}$, $M_{13}=M_{31}$, etc.). The diagonal elements can be chosen independently in 2 ways (0 or 1). For the off-diagonal elements, we only need to make independent choices for the elements above the main diagonal (or below). There are $\frac{n(n-1)}{2}$ such positions. Once these are chosen, their symmetric counterparts are determined. The total number of independent choices for a symmetric relation is $n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$. For $n=4$, this is $\frac{4(4+1)}{2} = \frac{4 \times 5}{2} = 10$. Each of these 10 independent positions can be either 0 or 1. So, the total number of symmetric relations is $2^{10} = 1024$.

Step 3: Calculate the number of relations that are both symmetric and reflexive. A relation is reflexive if $M_{ii} = 1$ for all $i$. For a relation to be both symmetric and reflexive:

• The diagonal elements ($M_{11}, M_{22}, M_{33}, M_{44}$) must all be 1. There is only 1 choice for each of these (they are fixed).
• The off-diagonal elements must satisfy $M_{ij} = M_{ji}$. As in Step 2, we have $\frac{n(n-1)}{2}$ independent choices for the elements above the main diagonal. For $n=4$, the number of independent choices for the off-diagonal elements is $\frac{4(4-1)}{2} = \frac{4 \times 3}{2} = 6$. Each of these 6 independent positions can be either 0 or 1. So, the number of relations that are both symmetric and reflexive is $2^6 = 64$.

Step 4: Calculate the number of symmetric relations that are NOT reflexive. We use the subtraction principle: Number of (Symmetric AND Not Reflexive Relations) = (Total Number of Symmetric Relations) - (Number of Symmetric AND Reflexive Relations) $= 2^{10} - 2^6$ $= 1024 - 64$ $= 960$.

Common Mistakes & Tips

• Confusing Independent Choices: Be careful to distinguish between matrix entries that are fixed by a property (like diagonal elements in a reflexive relation) and those that can be freely chosen (like off-diagonal elements in a symmetric relation).
• Double Counting: When counting symmetric relations, remember that choosing $M_{ij}$ automatically determines $M_{ji}$. Only count the unique pairs or the elements in the upper/lower triangle.
• Formula Application: Ensure you are using the correct formula for the number of independent choices for each type of relation property.

Summary To find the number of symmetric relations that are not reflexive on the set $\{1, 2, 3, 4\}$, we first calculated the total number of symmetric relations by considering the independent choices in its $4 \times 4$ relation matrix, which resulted in $2^{10} = 1024$ possibilities. Next, we determined the number of relations that are both symmetric and reflexive. For these, the diagonal elements are fixed to 1, leaving the off-diagonal elements to be determined by symmetry, resulting in $2^6 = 64$ possibilities. Subtracting the latter from the former gives us the number of symmetric relations that are not reflexive: $1024 - 64 = 960$.

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