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.