edited by
186 views
5 votes
5 votes
What is the number of relations which are either symmetric or asymmetric on the set $A=\{1,2,3,4\}$?
edited by

1 Answer

Best answer
11 votes
11 votes

$\textbf{For symmetric relation:}$ We can also think of it as a matrix $n\times n$, with the elements of the matrix being $(a_i,a_j)$ with $ a_i,a_j \in A$. The elements of the main diagonal can be perfectly chosen for the relation because they are symmetric. For the rest of the elements, picking a pair from the upper triangle say $(a_2,a_1)$ implies that you are also picking $(a_1,a_2)$. So from the total $n^2$ pairs you end up with only $$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$$ from which to choose. We can do this in $2^{\frac{n(n+1)}{2}}$ ways.

So, $n(S) = 2^{\frac{n(n+1)}{2}} = 2^{10} = 1024$

$\textbf{For asymmetric relation:}$ Let us take an example.

$$A = \{1,2,3\}$$
$$A\times A = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$$

We know that, $(1,1),(2,2),(3,3)$ won't come in the asymmetric relation.(3 elements)

Remaining elements of $A\times B$ can be grouped into 3 groups of 2 elements each as:

$[(1,2),(2,1)]$, $[(1,3),(3,1)]$, $[(2,3),(3,2)]$ (3 groups)

From every group, we can choose elements in 3 different ways.

1. choose 1st element.

2. choose 2nd element.

3. choose no elements.

That is, we can choose elements in $3^3$ different ways in this case.

Generalizing,

If there are $n$ elements in the set, the number of elements in the group is $\frac{\text{Total  number  of relations - reflexive  elements }}{2}=\frac{n^2 - n}{2}$

Each of these elements can be chosen in 3 ways. Therefore the number  of asymmetric  relations is $3^{\frac{n^2 - n}{2}}.$

So, $n(A) = 3^{\frac{n^2 - n}{2}} = 3^{6} = 729$



Some examples:

$R_{1}=\{(1,1),(1,2),(2,1)\}$, it is symmetric but not asymmetric.

$R_{2}=\{(1,2)\}$, it is asymmetric but not symmetric.

$R_{3}=\{\:\:\}$ , it is symmetric and  asymmetric.

$R_{4}=\{(1,1),(1,2)\}$, it is not symmetric and  not asymmetric.

$n(S\cap A) = 1$ because empty relation is the only one which is both symmetric as well as asymmetric.

Now, $n(S\cup A)=n(S) + n(A) - n(S \cap A)$

$\implies n(S \cup A) = 1024 + 729 - 1 = 1752$.

So, the correct answer is $1752$.

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
4 votes
4 votes
1 answer
3
gatecse asked Jul 12, 2020
170 views
Let $A=\{a,b,c,d,e\}$. The total number of unordered pairs of disjoint subsets of $A$ is equal to?$3^{5}$$5^{3}$$102$$122$
1 votes
1 votes
1 answer
4