Изменения
→Алгоритм для антисимметричных отношений
Докажем, что <tex> \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} \subseteq E^- </tex>:
Предположим, что <tex> k \underset{G}{\to} m </tex> и <tex> \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex>. Докажем, что <tex> k G^- m </tex>, от противного. Предположим, что <tex> (k, m) \notin E^- </tex>. Поскольку <tex> G </tex> ацикличен, <tex> k \neq m </tex> и поэтому <tex> k (\underset{G^-}{\overset{+}{\leadsto}} m </tex>. Поскольку <tex> (k, m) \notin E^- </tex>, существует вершина <tex> l </tex> такая, что <tex> k \underset{G^-}{\leadsto} l \wedge l \underset{G^-}{\leadsto} m </tex> и <tex> k \neq l \neq m </tex>, поэтому <tex> k \underset{G}{\overset{+}{\leadsto}} l \wedge l \underset{G}{\overset{+}{\leadsto}} m </tex>. Поскольку <tex> G </tex> ацикличен, существует вершина <tex> l' \neq k </tex>, для которой выполняется <tex> k \underset{G}{\overset{+}{\leadsto}} l' \wedge l' \underset{G}{\to} m </tex>, что противоречит нашему предположению.
Так как множества <tex> E^- </tex> и <tex> \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, что и требовалось доказать.
