# How many “transitive relation” can be formed by A×A [duplicate]

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

## marked as duplicate by Anurag A, Theo Bendit, Thomas Shelby, Mees de Vries, ShaileshAug 14 at 9:19

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)\neq A$$ while $$\psi(i)=A$$ for each $$i . Then $$\psi(n-1)$$ does not contain $$1,\dots ,n-2$$ because otherwise $$A=\psi(i)\subseteq \psi(n-1)$$ and it is not possible. So we can have only

$$\psi(n-1)=\{n-1\}$$ or $$\psi(n-1)=\{n-1, n\}$$ or $$\psi(n-1)=\{n\}$$

In the first case we can choice $$\psi(n)=\{n\}$$ or $$\psi(n)=\{n, n-1\}$$ or $$\psi(n)=A$$ while in the second case we can have

$$\psi(n)=\{n\}$$ or $$\psi(n)=\{n,n-1\}$$

and in the third case we have

$$\psi(n)=\{n\}$$

So we have 6 cases.