0 Daumen
189 Aufrufe

Guten Abend zusammen

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

von

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.

1 Antwort

0 Daumen
 
Beste Antwort

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.

von 2,1 k

Guten Abend Doesbaddel

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.

Guten Abend Doesbaddel

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.

Guten Abend Doesbaddel

Entschuldige, evtl. 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

Guten Abend Doesbaddel

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?

Guten Abend Doesbaddel

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.

Guten Abend Doesbaddel

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.

Guten Abend Doesbaddel

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.

Guten Abend Doesbaddel

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.

Guten Abend Doesbaddel

Ah ok, danke vielmals.

MfG und einen schönen Abend!
Lenovo

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community