Number of relations that are both symmetrical and also reflexive

Consider a non - vacant set A having n things. The amount of relations on A are both symmetrical and also reflexive?

The response to this is $2^p$ where $p=$ $n \choose 2$. Nonetheless, I do not recognize why this is so. Can any person clarify this?

2019-12-02 02:49:00
Source Share
Answers: 4

Being reflexive methods that $(x,x)\in R$ for all $x\in A$. Being symmetrical methods that $(x,y)\in R$ indicates that $(y,x)\in R$ too.

Begin by detailing $A$ as $A=\{a_1,\dots,a_n\}$. After that allow $B$ be the set $$\{(a_i,a_j)\mid 1\le i<j\le n\}.$$ Note that if $x\ne y$ are components of $A$, after that either $(x,y)\in B$ or $(y,x)\in B$ yet not both.

Allow $S$ be any kind of part of $B$. Allow $$R_S=S\cup\{(y,x)\mid (x,y)\in S\}\cup\{(x,x)\mid x\in A\}.$$ Then $R_S$ is a symmetrical and also reflexive relationship on $A$.

Keep in mind that there are $2^{|B|}$ parts of $B$, which if $S\ne S'$ are parts of $B$, after that $R_S\ne R_{S'}$. Additionally, keep in mind that $|B|=\binom{n}2$. (If the last equal rights is unclear, note that $$B=\{(a_1,a_j)\mid j>1\}\cup\{(a_2,a_j)\mid j>2\}\cup\dots$$ so $|B|=(n-1)+(n-2)+\dots+1$, and also it is well - recognized that the last amount amounts to $n(n-1)/2=\binom n2$.

This reveals that the variety of symmetrical, reflexive relations on $A$ goes to the very least $2^p$ with $p=\binom n2$.

To see the equal rights, it suffices to examine that any kind of such relationship $R$ is $R_S$ for some $S\subseteq B$. Yet, offered $R$, allow $S=\{(a_i,a_j)\in R\mid i<j\}$. This is a part of $B$, and also it is very easy to examine that $R=R_S$.

2019-12-03 04:24:18

To be reflexive, it has to include all sets $(a,a)$ with $a\in A$. To be symmetrical, whenever it consists of a set $(a,b)$, it has to include both $(b,a)$. So it totals up to picking which $2$ - component parts from $A$ will certainly represent linked sets. If you select a part $\{a,b\}$ with 2 components, it represents including both $(a,b)$ and also $(b,a)$ to your relationship.

The amount of $2$ - component parts does $A$ have? Given that $A$ has $n$ components, it has specifically $\binom{n}{2}$ parts of dimension $2$.

So currently you intend to select a collection of parts of $2$ - components. There are $\binom{n}{2}$ of them, and also you can either select or otherwise select each of them. So you have $2^{\binom{n}{2}}$ means of selecting both of distinctive components that will certainly be connected.

2019-12-03 04:24:14

Maybe you can see it similar to this : a relationship $R$ on $A$ is a part of $A\times A$, and also it is symmetrical if and also just if $(x,y)\in R \implies (y,x)\in R$, in addition, if the relationship is reflexive, after that $(x,x)\in R$ for all $x\in A$. After that you can establish distinctly such a relationship by claiming which parts of 2 distinctive components of $A$ "belong" to $R$, in the feeling that $\{x,y\}\in R \iff (x,y),(y,x)\in R$. Currently, you recognize that the variety of parts with 2 distinctive components of $A$ is $\binom{n}{2}$, and also the variety of part of a set with $p$ components is $2^p$. I'm sorry if i was also rare.

2019-12-03 04:23:56

There is just one means to make the relationship reflexive - - all gotten sets $(x,x), x\in A$ have to remain in the relationship. So the variety of reflexive symmetrical relations on $A$ coincides as the variety of means of including symmetrical sets $(a,b),(b,a)$, where $a\neq b$ right into the relationship.

Allow $S$ be a part of $2^A$ containing parts of 2 components. After that $S$ generates specifically one reflexive symmetrical relationship on $A$. As an example, if $A=\lbrace 1,2,3,4\rbrace$, after that an instance of $S$ is $\lbrace \lbrace 1,2\rbrace, \lbrace 1,4\rbrace, \lbrace 3,2\rbrace\rbrace$. The relationship generated by $S$ is $$\lbrace (1,2), (2,1), (1,4), (4,1), (2,3), (3,2)\rbrace$$ plus all $(x,x), x\in A$. Alternatively, every reflexive symmetrical relationship on $A$ emerges this way.

Given that there are $p={n\choose 2}$ parts of 2 components, there are $2^p$ such $S$'s. The response to your inquiry is consequently $2^p$.

2019-12-03 04:12:05