Relation zu einer Ordnungsrelation machen

Question

Ich habe folgende Relation:

R = {(1,1),(1,2),(1,3),(2,2),(2,3),(2,4),(4,4)}

Die Relation R soll eine Ordnungsrelation sein. Das heisst sie muss reflexiv, antisymmetrisch und transitiv sein. Welche Symbole müssen Sie hinzufügen.

Mein Vorgehen:

Damit sie reflexiv ist, muss folgendes Symbol hinzugefügt werden

(3,3)

Damit sie transitiv ist, müsste meiner Meinung nach folgende Symbole hinzugefügt werden:

(1,4) und (3,4)

Laut den Lösungen benötigt es (3,4) nicht. Warum ist dies so?

x = 2
y = 3
z = 4

(2,3) ∈ R und (2,4) ∈ R, dann müsste meiner Meinung (3,4) auch hinzugefügt werden?

Vielen Dank im Voraus!

MfG
Lenovo

Comments

Mein Ratschlag wäre, für eine solche Aufgabe in erster Linie einen Graph (mit den Knoten 1,2,3,4) zu zeichnen. Die Aussage  (a,b)∈R wird durch einen Pfeil von a nach b dargestellt. Die Eigenschaften Reflexivität, Transitivität und Antisymmetrie lassen sich anhand der eingezeichneten Pfeile sehr gut überblicken und dann der Graph vervollständigen.

---

Genau, und für ein Hasse-Diagramm entfernt man dann alle Pfeilspitzen (ungerichteter Graph) und die reflexiven und transitiven Relationen.

Answer 1

Du brauchst $(3,4)$ nicht, da für $x=y=2$ und $z=4$ gilt: $(2,2)\in R\land (2,4)\in R \implies (2,4)\in R$. Die Definition der Transitivität erlaubt auch $x=y$ und $x=y=z$ und deshalb ist sie für die Elemente $2$ und $4$ erfüllt.

Ein kleines Beispiel:
Die Relation $R':=\{(2,2)\}$ auf der Menge $M'=\{2\}$ ist reflexiv, transitiv, symmetrisch und antisymmetrisch, weil gilt:
$R'$ ist reflexiv: $(2,2)\in R'$
$R'$ ist transitiv: $(2,2)\in {R'} \land (2,2)\in R' \implies (2,2)\in R'$
$R'$ ist symmetrisch: $(2,2)\in R' \implies (2,2)\in R'$
$R'$ ist antisymmetrisch: $(2,2)\in R' \land (2,2)\in R \implies 2=2$
Merke: Da die Menge $M'$ in meinem Beispiel einelementig ist, reicht hier der Beweis der Eigenschaften der Relation mit nur einem Element.

Comments

Das verstehe ich nicht genau. Warum benötige ich dann überhaupt noch (1,4)? Wann weiss ich, dass ich jetzt eine Verbindung hinzufügen muss und wann nicht (z.B. bei der Relation unten)?

R = {(1,2),(1,3)}

Vielen Dank im Voraus!

MfG
Lenovo

---

(1,4) brauchst du damit (1,2) und (2,4) => (1,4) gilt.

Deine Beispielrelation ist transitiv. Die Aussage verlangt ja nur, dass wenn es xRy und yRz gibt dann muss es auch xRz geben. In deinem Fall gibt es (2,1),(3,1) oder (3,2) nicht und deswegen wird die Transitivität nicht verletzt.

---

Danke für die Antwort. Ich bin nun einfach verunsichert, wie ich herausfinden kann, ob ich ein Symbol hinzufügen muss oder keines? Wie gehen Sie in diesem Fall vor? Warum haben Sie das gesehen, dass ich (3,4) nicht benötige?

Ich sehe eben den Unterschied zwischen der Gruppe {(1,2),(1,3),(1,4)} und der Gruppe {(2,3),(2,4)} nicht. Ich dachte eben, dass ich dies so wie in Gruppen aufteilen kann und dann sehen kann, was ich noch benötige

MfG
Lenovo

---

Hallo Lenovo,

ich habe gesehen, dass 2 in Relation zu sich selbst steht (2R2 oder man kann auch (2,2) ist in der Menge R schreiben). Außerdem steht 2 aber auch in Relation zu 4 (2R4). Ich habe also xRy und yRz, wobei x=y ist: 2R2 und 2R4. Nun muss aber laut Transitivität gelten: "Für alle x,y,z aus der Menge M gilt, dass wenn xRy und yRz, folgt auch xRz". Das haben wir aber auch schon erfüllt: 2R2 und 2R4 => 2R4. Das Tupel (2,4) ist aber schon in unserer Menge und demnach brauchen wir (3,4) nicht mehr um die Transitivität zu gewährleisten. Ich gucke also immer erstmal durch die Menge und prüfe: Finde ich Tupel in der Relationsmenge, wo es die Tupel xRy UND yRz gibt, aber NICHT das Tupel xRz? Genau diese Tupel müssen wir dann noch hinzufügen, damit die Relation transitiv ist. Wenn es aber zu jedem xRy UND yRz schon das zugehörige xRz gibt, musst du nichts mehr hinzufügen. Das Gleiche gilt auch, wenn es gar keine Tupel gibt, die xRy UND yRz erfüllen.

---

In Sachen Transitivität haben deine Beiden Beispielmengen auch keinen Unterschied. Sie sind beide transitiv, denn es gibt einfach keine Elemente, für die xRy und yRz gilt. Da in einer Implikation die Aussagen $\operatorname{falsch} \implies \operatorname{falsch}$ und $\operatorname{falsch} \implies \operatorname{wahr}$ wahr sind, ist das auch in unserem Fall so. Also die Relation {(1,2),(1,3),(1,4)} und die Relation {(2,3),(2,4)} auf der Menge M={1,2,3,4} sind beide transitiv.

---

Entschuldige, eventuell stelle ich mich jetzt richtig blöd an. Ich hab es nicht so ganz verstanden. Aber wenn mir nochmals die Relation von oben genauer betrachten. Ich hab sie hier nochmals in zwei einzelne Relation gebracht.

R1: {(1,1),(1,2),(1,3)} → warum benötigen wir hier dann (2,3)

dies ist für mich analog zu:

R2:{(2,2),(2,3),(2,4)} → da müssten wir doch auch (3,4) dann einfügen.

Was ist der Unterschied zwischen R1 und R2, dass ich weiss, warum ich (3,4) nicht hinzufügen muss?

Vielen Dank im Voraus!

MfG
Lenovo

---

Huhu,

Zu R1:
Wir benötigen (2,3) nicht! Die Aussage $\forall x,y,z \in M: xRy \land yRz \implies xRz$ ist wahr für alle $x,y,z$. Denn es gibt die Tupel (1,1) und (1,3) und folglich auch (1,3). [Setze x=1, y=1, z=3 in die Definition ein.] Außerdem gibt es (1,1) und (1,2) und daraus folgt, dass es auch (1,2) gibt. [Setze x=1, y=1, z=2 in die Definition ein.] Mehr Tupel gibt es nicht, die die Bedingung $xRy \land yRz$ erfüllen. Deshalb ist die Aussage wahr und die Relation ist damit transitiv.

Zur R2:
Wir brauchen (3,4) nicht! Gleiche Argumentation wie oben.

Grüße

---

Danke vielmals. Jetzt habe ich es glaub verstanden. Hätten wir in der Relation R1 das Symbol (1,1) nicht, dann müssten wir (2,3) haben oder?

R1: {(1,1),(1,2),(1,3)}

Abgesehen, dass wir dann nur 2 Symbole hätten, dann wäre es durch die Aussagelogik wieder richtig.

MfG
Lenovo

---

Nein, das ist hier ein Sonderfall: Wir finden keine Tupel, die die Bedingung $(x,y)$ und $(y,z)$ aus der Definition der Transitivität erfüllen. Deshalb ist die Aussage aber trotzdem wahr, weil die Implikation eine wahre Aussage liefert, selbst wenn $0\implies 0$ oder $0\implies 1$ gilt. In unserem Falle für [x=1, y=2, z=3] ist die Bedingung auf der linken Seite der Implikation $1R2 \land 2R3$ nicht erfüllt, die Aussage auf der rechten Seite der Implikation aber schon: (1R3) Also anders ausgedrückt gilt hier $0\implies 1$ und das ist laut Definition der Implikation wahr bzw. (1). Das gleiche passiert für [x=1, y=3, z=2].
Für alle anderen Kombinationen der Elemente aus M ist die Aussage sowieso wahr, weil auf beiden Seiten der Implikation Falschaussagen stehen. z.B. für x=3 y=2 z=1: Wir haben keine Tupel (3,2),(2,1) in der Relation, deswegen ist die linke Seite nicht erfüllt. Genauso gibt es aber auch kein Tupel (3,1). Daher ist auch die rechte Seite der Implikation nicht erfüllt. Bei einer Implikation $a\implies b$ für zwei Aussagen $a,b$ ist die Aussage aber wahr, wenn $a,b$ nicht wahr sind. Deshalb ist unsere Relation schon transitiv.

EDIT: Ja, wenn wir das mit der Definition der Implikation ignorieren, dann hast du Recht. Dann müssten wir (2,3) hinzufügen um die Transitivität zu erreichen.

---

Hallo Lenovo,

ich habe meine Antwort an dein bearbeitetes Kommentar angepasst.

PS: (1,1) ist kein Symbol, sondern ein Tupel. In unserem Fall bedeutet "(1,1)", dass 1 in Relation zu 1 steht.

Grüße

---

Super danke vielmals. Entschuldige den ganzen Aufwand!

Oder wäre das wie in diesem Beispiel B = {1,2,3,4,5,6}:

R = {(1,1),(1,2),(2,2),(2,3),(2,4),(3,4),(4,4),(6,3)}

Aus dieser Relation müssten wir nun wieder eine Ordnungsrelation erstellen.

Das heisst, damit sie reflexiv ist, müssten wir folgendes hinzufügen:

(3,3),(5,5),(6,6)

Damit Sie transitiv ist müssten wir folgendes hinzufügen:

(1,4)

x=1
y=2
z=4

und

(1,3)

x=1
y=2
z=3

---

Gerne, gerne :)

zu R: stimmt

zu T: Ja, die beiden brauchst du. Du hast aber noch (6,4) vergessen, sonst fehlt für 6R3 und 3R4 das Tupel (6,4) und die Relation wäre damit nicht transitiv. Ich hoffe, ich habe jetzt kein Tupel vergessen.

PS: Die Ordnungsrelation ist übrigens auch antisymmetrisch und erfüllt mit den zugefügten Elementen (3,3),(5,5),(6,6),(1,4),(1,3),(6,4) die Eigenschaften einer Halbordnung.

---

Hast du noch Fragen?

---

Entschuldigen Sie für die späte Antwort. Nein im Moment ist dies mir klar.

Danke vielmals nochmals!

MfG
Lenovo

---

Super. Ich habe mich nur gewundert, warum du nichts auf meinen vorigen Kommentar geschrieben hast. Deswegen habe ich mich dann gefragt, ob du verstanden hast, warum das Tupel (6,4) noch dazukommen muss.

---

Nein, danke das ist mir klar.

Ich habe nur hier noch eine Frage bezüglich der Transitivität:

Sei R ⊆ Z × Z gegeben durch (x, y) ∈ R ⇔ x + y = 9 (Z sind die ganzen Zahlen)

Ist diese Relation nicht transitiv, da hier die Reflexivität fehlt. Oder gibt es hier einen anderen Grund?

Zum Beispiel sind die Tupel (5,4) und (4,5) sind ja in der Relation. Da habe ich zuerst gedacht, da hier die Bedingung gar nicht erfüllt werden kann, dass dies Transitiv sein muss (durch Aussagelogik).

Vielen Dank im Voraus!

MfG
Lenovo

---

Nein, du hast Recht. Es liegt hier daran, dass z.B. $(5,5)\notin R$ ist:

Da $(5,4)\in R$ und $(4,5)\in R$ jeweils Elemente von $R$ sind, muss auch $(5,5)$ Element von $R$ sein. Widerspruch! $5+5\neq 9$ und demnach gilt $(5,5)\notin R$. Die Relation ist nicht transitiv.

---

Danke vielmals für die schnelle Antwort. Ist das in meiner Schreibweise ungefähr so:

x=5
y=4
z=5

(5,4) ∈ R und (4,5) ∈ R, dann müsste (5,5) auch in R sein. Ist es jedoch durch die Bedingung nicht.

Vielen Dank

MfG und einen schönen Abend!
Lenovo

---

Hallo Lenovo!

Ja, aber beachte, dass du die Definition von Transitivität auch dazu schreibst und dann formulierst: Setzt man in die Definition von der Transitivität x=5,y=4,[...] ein, dann ergibt sich folgendes Gegenbeispiel [...]. Sonst kann man nicht nachvollziehen, woher du x,y,z nimmst.

---

Danke für die Information. Das heisst ich muss die Definition der Transitivität auch hinschreiben. Also so ungefähr:

(x,y) ∈ R und (y,z) ∈ R, dann auch (x,z) ∈ R

MfG
Lenovo

---

Transitivität, wenn $M$ und $R$ wie oben gegeben sind: $$\forall x,y,z\in M: (x,y)\in R \land (y,z)\in R \implies (x,z)\in R.$$ Die Definition gilt aber nur für deine Aufgabenstellung. Wenn die Menge natürlich anders heißt (z.B $K$) und die Relation dadurch anders definiert ist, dann musst du es gegebenenfalls ändern.

---

Ah ok, danke vielmals.

MfG und einen schönen Abend!
Lenovo

---

Gerne! Dir auch einen schönen Abend bzw. eine gute Nacht :D