Find transitive sub-relations of a non-transitive relation

55 Views Asked by At

Given a relation $R$ that is not transitive, I want to find subsets of $R$ that are actually transitive. What is the name of this operation and how this can be done?

1

There are 1 best solutions below

3
On

Well order $R = \{ a_{xi} : xi <|R| \}$. Let $R_0$ = $R$. Given $R_{xi} \subseteq R$,
define $R_{(xi+1)} = R_{xi} - \{ a_{xi} \}$ if $R_{xi}$ isn't transitive, $= R_{xi}$ otherwise.
For limit ordinal $\eta$ with for all $xi < \eta$, $R_{xi}$ is defined, define, $R_{\eta} = \bigcap{ R_x : xi < \eta }$. $R_{|R|}$ is a transitive subset of $R$.