# 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 ?

Tags :

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 . Then