91Ó°ÊÓ

The complement \(\bar{A}\) of an \(r\) -subset \(A\) of \(\\{1,2, \ldots, n\\}\) is the \((n-r)\) -subset of \(\\{1,2, \ldots, n\\}\), consisting of all those elements that do not belong to \(A\). Let \(M=\left(\begin{array}{l}n \\\ r\end{array}\right)\), the number of \(r\) -subsets and, at the same time, the number of \((n-r)\) subsets of \(\\{1,2, \ldots, n\\} .\) Prove that, if $$ A_{1}, A_{2}, A_{3}, \ldots, A_{M} $$ are the \(r\) -subsets in lexicographic order, then $$ \overline{A_{M}}, \ldots, \overline{A_{3}}, \overline{A_{2}}, \overline{A_{1}} $$ are the \((n-r)\) -subsets in lexicographic order.

Let \(X\) be a set of \(n\) elements. How many different relations on \(X\) are there? How many of these relations are reflexive? Symmetric? Antisymmetric? Reflexive and symmetric? Reflexive and anti-symmetric?

Prove that the intersection \(R \cap S\) of two equivalence relations \(R\) and \(S\) on a set \(X\) is also an equivalence relation on \(X\). Is the union of two equivalence relations on \(X\) always an equivalence relation?