Question

Komplement einer transitiven zweistelligen Relation auch transitiv?

Aufgabe:

Es sei M eine Menge, R ⊆ M × M eine zweistellige Relation auf M. R ̄ist Komplement(M × M) \ R.

Folgt aus der Transitivität von R stets die Transitivität von R ̄? Geben Sie einen Beweis oder ein Gegenbeispiel.

Problem/Ansatz:

Nach einigem Rumprobieren mit konkreten Beispielen würde ich sagen, dass R ̄auch transitiv ist (wobei ich mir nicht zu 100% sicher bin).

Wie formuliere ich den Beweis?

Answer 1

Ist vielleicht $R=\{(m,m):\; m\in M\}$ mit $|M|>1$ ein Gegenbeispiel?

Answer 2

Transitivität von $\overline{R}\subseteq M\times M$:

        $(a,b)\notin R \wedge (b,c)\notin R \implies (a,c)\notin R$.

Das sieht schon unglaubwürdig aus.

Es gibt ein Gegenbeispiel mit $|M|=3$.

Comments

Es gibt ein Gegenbeispiel mit $|M|=3$.

Sogar schon mit $|M|=2$ ;-)

---

Jetzt habe ich die Gegenbeispiele auch gefunden, vielen Dank für die Antworten! Da habe ich wohl zu einfach gedacht.