0
$\begingroup$

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?

$\endgroup$

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.