How many "transitive relation" can be formed by A×A

by Booki   Last Updated August 14, 2019 09:20 AM - source

If A is non-empty set then how may " transitive relation " can be made by A×A ?



Answers 1


There is no simple way to get a solution but you can interpretate your problem in this way:

For each relation $\sim$ of $A$ we can define the map

$\psi_\sim: A\to \mathcal{P}(A)$

such that

$\psi_\sim(a):=\{b\in A: a\sim b\}$

In this case you have that if $\sim$ is transitive then for each $b\in \psi_\sim(a)$

$\psi_\sim(b)\subseteq \psi_{\sim}(a)$

So

$\{\sim : \sim transitive \}\cong \Lambda$

where $\Lambda:= \{\psi:A\to \mathcal{P}(A): \forall a,b \ if \ b\in \psi(a) \ then \ \psi(b)\subseteq \psi(a)\}$

Now we want prove to determine the cardinality of $\Lambda$. For simplicity $A=\{1,\dots , n\}$

We suppose that $\psi(i)=A$ for each $i< n$ then the only choice of $\psi(n)$ to get $\psi$ transitive can be $\psi(n)=\{n\}$ or $\psi(n)=A$. So in this case we have

$|\{\psi\in \Lambda : \psi(i)=A \forall i< n\}|=2$

We suppose that $\psi(n-1)=\{1,\dots n-1\}$ while $\psi(i)=A$ for each $i<n-1$ . Then

Federico Fallucca
Federico Fallucca
August 14, 2019 08:52 AM

Related Questions


recurrence solution of placing tiles

Updated March 06, 2016 01:08 AM

Which possible relations are relations here?

Updated May 05, 2017 09:20 AM

Count the partial equivalence relations on a set

Updated November 15, 2017 07:20 AM

Combinatorics | Recurrence relations | Problem

Updated May 09, 2017 17:20 PM