How do the set of all transitive relations on a set form a lattice? I am new to discrete mathematics and only thing that i know about lattices is that to form a lattice, each pair of the set must have a lowest upper bound and greatest lower bound.
 A: Let $X$ be a set, and let $\mathscr{L}$ be the set of transitive relations on $X$. The lattice order on $\mathscr{L}$ is $\subseteq$. If $R,S\in\mathscr{L}$, it's not hard to show that $R\cap S$ is transitive, so it's in $\mathscr{L}$. (I'll leave it to you to try to prove that; it really is a very straightforward exercise in checking the definition.) It's clearly the largest relation on $X$ that is a subset of both $R$ and $S$, so it's their greatest lower bound in $\mathscr{L}$.
Their least upper bound is a little more complicated. Let $\mathscr{T}$ be the set of all transitive relations $T$ on $X$ such that $R\cup S\subseteq T$; then it's not hard to show that $\bigcap\mathscr{T}$ is a transitive relation on $X$, i.e., that $\bigcap\mathscr{T}\in\mathscr{L}$. (In other words, it's not just the intersection of two transitive relations that is transitive: the intersection of any collection of transitive relations on a set is transitive.) Let $T_0=\bigcap\mathscr{T}$; then $T_0\subseteq T$ for each $T\in\mathscr{T}$, so $T_0$ is the smallest member of $\mathscr{L}$ containing $R\cup S$ and hence the smallest member of $\mathscr{L}$ containing both $R$ and $S$. ($T_0$ is called the transitive closure of $R\cup S$.)
A: Given any relation $R$ on a set $X$, we can define the transitive closure of $R$, usually denoted $R^+$, which is the intersection of all transitive relations containing $R$. This is well-defined because there is always at least one transitive relation containing $R$, namely $X \times X$. You can now check that this satisfies the following properties:


*

*$R^+$ is transitive, for any $R$.

*$R$ is transitive if and only if $R^+ = R$.

*If $A \subseteq B$ then $A^+ \subseteq B^+$.
What does this have to do with your problem? If $R$ and $S$ are transitive relations, we would like to show that $(R \cap S)^+$ is the greatest lower bound, and $(R \cup S)^+$ is the least upper bound. This should be a straightforward application of the above properties.
(In fact, $R \cap S$ will be transitive, so the greatest lower bound $(R \cap S)^+ = R \cap S$.)
