1
$\begingroup$

How many relations in ${\mathscr P}(A \times A)$ defined on $A$ are symmetric?

$A$ = $\{1,2,...,n\}$ and ${\mathscr P}(A \times A)$ is the power set of the cartesian product of $A$ with itself.

A symmetric relation in this case would be $\forall x \forall y, \{x,y\} \in X \implies \{y,x\} \in X$ for $X$ in ${\mathscr P}(A \times A)$.

EDIT: I think the answer is $2^{\frac{n(n+1)}{2}}$, because you have $2^{\frac{n(n-1)}{2}}$ number of sets containing only $\{x, y\}$ where $x < y$ and $2^n$ number of sets containing only $\{x, y\}$ where $x = y$

$\endgroup$
2
$\begingroup$

Let $\mathscr{S}$ be the set of all symmetric relations on $A=\{1,2,\dots ,n\},$ and define $V=\{\langle x, y\rangle \in A\times A \mid x\le y\}.$

Define $f\colon \mathscr{S} \to\mathscr{P}(V)$ by setting $f(R)=R\cap V$ for any symmetric relation $R$ on $A.$ Then $f$ is a bijection between $\mathscr{S}$ and $\mathscr{P}(V).$

Since $\lvert V \rvert=\dfrac{n(n+1)}{2},$ it follows that \begin{align}\lvert \mathscr{S} \rvert &= \lvert \mathscr{P}(V) \rvert\\&=2^{\lvert V \rvert} \\&=2^{n(n+1)/2}. \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.