Question

The number of symmetric relations defined on the set {1, 2, 3, 4} which are not reflexive is _____.

Answer 1

Correct Answer: 960

Define symmetric relations: A relation \( R \) is symmetric if \( (a, b) \in R \implies (b, a) \in R \). A relation is reflexive if \( (a, a) \in R \) for all \( a \).

Count total relations:

\[ \text{Total relations} = 2^{n^2} \text{ for } n = 4. \]

\[ \text{Total relations} = 2^{4^2} = 2^{16} = 65536. \]

Count reflexive relations: Reflexive pairs: \( (1, 1), (2, 2), (3, 3), (4, 4) \) (4 pairs). Remaining symmetric pairs: \( (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) \) (6 pairs).

\[ \text{Total reflexive relations} = 2^6 = 64. \]

Count symmetric relations:

\[ \text{Symmetric relations} = 2^{\binom{n}{2} + n} = 2^{6 + 4} = 2^{10} = 1024. \]

Non-reflexive symmetric relations:

\(\text{Non-reflexive symmetric relations} = \text{Total symmetric relations} - \text{Reflexive symmetric relations} = 1024 - 64 = 960.\)

Thus, the answer is: 960

Answer 2

The problem asks for the number of relations on the set \( A = \{1, 2, 3, 4\} \) that are symmetric but not reflexive. We can find this by first calculating the total number of symmetric relations on the set and then subtracting the number of relations that are both symmetric and reflexive.

Concept Used:

1. Relation on a Set: A relation \( R \) on a set \( A \) is a subset of the Cartesian product \( A \times A \).

2. Symmetric Relation: A relation \( R \) on \( A \) is symmetric if for every pair of elements \( a, b \in A \), the condition \( (a, b) \in R \) implies \( (b, a) \in R \).

3. Reflexive Relation: A relation \( R \) on \( A \) is reflexive if for every element \( a \in A \), the pair \( (a, a) \) is in \( R \).

4. Counting Principle: The number of symmetric relations that are not reflexive is the difference between the total number of symmetric relations and the number of relations that are both symmetric and reflexive.

5. Counting Symmetric Relations: A symmetric relation on a set \( A \) of size \( n \) is determined by which diagonal elements \( (a, a) \) are included and which pairs of off-diagonal elements \( \{(a, b), (b, a)\} \) for \( a \neq b \) are included. There are \( n \) diagonal elements and \( \binom{n}{2} \) such pairs.

• Total number of symmetric relations = \( 2^n \times 2^{\binom{n}{2}} = 2^{n(n+1)/2} \).
• Total number of symmetric and reflexive relations = \( 1 \times 2^{\binom{n}{2}} = 2^{n(n-1)/2} \) (since all diagonal elements must be included).

 

Step-by-Step Solution:

Step 1: Identify the size of the set and the types of elements in \( A \times A \).

The given set is \( A = \{1, 2, 3, 4\} \). The size of the set is \( n = 4 \).

The Cartesian product \( A \times A \) has \( n^2 = 4^2 = 16 \) ordered pairs. These pairs can be categorized into:

• Diagonal elements: Pairs of the form \( (a, a) \). There are \( n = 4 \) such elements: \( (1,1), (2,2), (3,3), (4,4) \).
• Off-diagonal elements: Pairs of the form \( (a, b) \) where \( a \neq b \). There are \( n^2 - n = 16 - 4 = 12 \) such elements. These can be grouped into \( \binom{n}{2} = \binom{4}{2} = \frac{4 \times 3}{2} = 6 \) pairs of the form \( \{(a, b), (b, a)\} \).

Step 2: Calculate the total number of symmetric relations on set \( A \).

For a relation to be symmetric, for each of the 6 off-diagonal pairs \( \{(a, b), (b, a)\} \), we have two choices: either include both ordered pairs \( (a, b) \) and \( (b, a) \) in the relation, or include neither. This gives \( 2^6 \) possibilities for the off-diagonal elements.

For the 4 diagonal elements \( (a, a) \), there are no restrictions for symmetry. We can independently choose to include or not include each one. This gives \( 2^4 \) possibilities for the diagonal elements.

Total number of symmetric relations = (Choices for diagonal elements) \( \times \) (Choices for off-diagonal pairs)

\[ \text{Total Symmetric Relations} = 2^4 \times 2^6 = 2^{10} = 1024 \]

Step 3: Calculate the number of relations that are both symmetric and reflexive.

For a relation to be reflexive, all 4 diagonal elements \( (1,1), (2,2), (3,3), (4,4) \) must be included in the relation. So, there is only 1 choice for the diagonal elements.

The condition for symmetry on the 6 off-diagonal pairs remains the same, giving \( 2^6 \) possibilities.

Number of symmetric and reflexive relations = (Choices for diagonal elements) \( \times \) (Choices for off-diagonal pairs)

\[ \text{Symmetric and Reflexive Relations} = 1 \times 2^6 = 64 \]

Step 4: Find the number of symmetric relations that are not reflexive.

This is the total number of symmetric relations minus the number of relations that are both symmetric and reflexive.

\[ \text{Number of required relations} = (\text{Total Symmetric Relations}) - (\text{Symmetric and Reflexive Relations}) \]

Final Computation & Result:

Using the values calculated in the previous steps:

\[ \text{Number of required relations} = 1024 - 64 = 960 \]

The number of symmetric relations defined on the set {1, 2, 3, 4} which are not reflexive is 960.