Given a binary relation $R$ over a set $A$ with $n$ elements,then :

$R$ is coreflexive if:

$$\forall a,b \in A:aRb \implies a=b$$

$R$ is Quasi-reflexive if: $$\forall a,b \in A:aRb \implies aRa \;\;\;\text{and}\;\;\; bRb$$

  • How many coreflexive and Quasi-reflexive relations exist on $A$?

Define $$A:=\left\{a_i \mid i \in I\right\}\tag{$\left|I\right|=n,n \in \mathbb N$}$$

Based on the definition $(a_i,a_j)\in R$ if $a_i=a_j$ .

On the other hand for each such $i$,either $(a_i,a_i)\in R$ or $(a_i,a_i) ∉ R$,so

Easily follows the number of coreflexive relation on $A$ is $2^n$.

For the other question let $i<j$.

If $(a_i,a_j)\in R$,then so are $(a_i,a_i)$ and $(a_j,a_j)$,also for each such $i$ either $(a_j,a_i)\in R$ or $(a_j,a_i)∉ R$,if $(a_i,a_j)∉ R$,then the only uncounted case appears when $(a_i,a_j)\in R$,from here it's seen that for all such $i$ there are 3 distinct Quasi-reflexive relations on $A$

Now we are left with the number of such $i$ which is $\sum_{k=1}^{n-1}k=\frac{n\left(n-1\right)}{2}$

So the number of Quasi-reflexive relations with $i \ne j$ is $$3^{\large\frac{n\left(n-1\right)}{2}}\tag{I}$$

Also for equal indexes either $(a_i,a_i) \in R$ or $(a_i,a_i) ∉ R$,the number of such $i$ is $n$,follows the number of such Quasi-relations is $$2^n\tag{II}$$

Summing $(\text{I})$ and $(\text{II})$ gives thew total number of Quasi-reflexive relations on $A$ for $n\ge2$.

But I'm not sure if the results are true,can someone check them?


Your Answer

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

Browse other questions tagged or ask your own question.