Gerichteter Graph/Symmetrisch/Vorgängermenge/Aufgabe/Lösung

Wir zeigen, dass die Negationen der beiden Eigenschaften zueinander äquivalent sind.

Es sei zuerst die Relation nicht symmetrisch. Dann gibt es ${}x,y$ mit ${}xRy$, aber ${}yRx$ gilt nicht. Dann ist ${}y$ kein Vorgänger von ${}x$ und daher ist ${}y\in M\setminus \operatorname {Vorg} {\left(\{x\}\right)}$. Es ist somit ${}x\in \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(\{x\}\right)}\right)}$ und also ${}x\notin M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(\{x\}\right)}\right)}$. Daher gilt die Vorgängereigenschaft für

${}T=\{x\}\,$

nicht.

Es sei nun die Vorgängereigenschaft nicht erfüllt, es gebe also eine Teilmenge ${}T\subseteq M$ mit

${}T\not \subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,.$

Dann gibt es ein ${}x\in T$ mit ${}x\in \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}$. Dies bedeutet, dass es ein ${}y\in M\setminus \operatorname {Vorg} {\left(T\right)}$ mit ${}xRy$ gibt. Wegen ${}y\notin \operatorname {Vorg} {\left(T\right)}$

ist insbesondere nicht ${}yRx$, also ist die Relation nicht symmetrisch.

Zur gelösten Aufgabe