Partielle Ordnungen, Vereinigung, Durchschnitt


0

Hallo ihr Rockstars,

hier habe ich noch eine Aufgabe zu den partiellen Ordnungen!

Wer kann mir helfen? 

Es seien R1 und R2 partielle Ordnungen auf der Menge A. Ist auch R1∪R2 immer eine partielle Ordnung auf A? Geben Sie einen Beweis oder ein einfaches Gegenbeispiel. Ist auch R1 ∩ R2 immer eine partielle Ordnung auf A? Geben Sie einen Beweis oder ein einfaches Gegenbeispiel.

Danke vielmals!

Eva

 

gefragt vor 4 Monate
e
evatsigkana,
Student, Punkte: 50
 
Kommentar schreiben Diese Frage melden
1 Antwort
0

Hallo,

auch hier wären deine Gedanken dazu sehr interessant gewesen. 

Wie ist denn eine partielle Ordnung definiert? Überlege dir nun für jede Eigenschaft einzelnd, was passieren würde wenn wir zwei Relationen schneiden bzw vereinigen würden. 

Grüße Christian

geantwortet vor 4 Monate
christian strack, verified
Sonstiger Berufsstatus, Punkte: 14903
 

Hallo Christian,

auch bei dieser Aufgabe habe ich sämtliche Definitionen niedergeschrieben und versucht zu einem Schluss zukommen. Meine Überlegung ist, dass die Reflexivität erfüllt wird, aber die Transitivität nicht, aber ich kann kein Gegenbeispiel geben. Somit kann die Vereinigung bzw der Schnitt nicht eine partielle Ordnung sein.
Kannst du meine Gedanken auf die richtige Spur bringen bitte?
  -   evatsigkana, kommentiert vor 4 Monate

Für die Vereinigung stimmt es nicht.
Die Antisymmetrie bleibt nicht immer erhalten
Nimm die beiden antisymmetrischen Relationen \( R_1 := \{ (1,1) , (1,2) , (2,2) \} \) und \( R_2 := \{ (1,1) , (2,1) , (2,2) \} \). Warum ist \( R_1 \cup R_2 \) keine partielle Ordnung?

Der Schnitt zweier partieller Ordnungen ist wieder eine partielle Ordnung. Gehen wir die Eigenschaften einmal durch.
Stell dir die Realtionen wieder als Menge von Zahlenpaaren vor. Vielleicht ist es dann leichter vorstellbar
Reflexivität bedeutet dargestellt als Zahlenpaar
\( \forall x \in M : \ (x,x) \in R \)
Antisymmetrie
\( \forall x,y \in M : \ (x,y) \in R \land (y,x) \in R \Rightarrow x=y \)
Transitivität
\( \forall x,y,z \in M : \ (x,y) \in R \land (y,z) \in R \Rightarrow (x,z) \in R \)
Warum kann der Schnitt keine dieser Eigenschaften verletzen?

Grüße Christian
  -   christian strack, verified kommentiert vor 4 Monate

Vielen Dank, Christian! Du hilfst mir ganz schon viel die Aufgaben und die Logik zu verstehen.   -   evatsigkana, kommentiert vor 3 Monate, 4 Wochen

Sehr gerne :)

Ist dir denn klar warum \( R_1 \cup R_2 := \{ (1,1) , (1,2) , (2,1) (2,2) \} \) nicht antisymmetrisch ist?

Und ist dir klar geworden warum der Durchschnitt diese Regeln nicht verletzt?

Grüße Christian
  -   christian strack, verified kommentiert vor 3 Monate, 4 Wochen

Ehrlich gesagt, es ist etwas durcheinander in meinem Kopf. Ich versuche zu verstehen, warum diese Vereinigung nicht antisymmetrisch ist. Insgesamt diese Eigenschaft fällt mir am schwierigsten, obwohl ich die Definition kenne..
  -   evatsigkana, kommentiert vor 3 Monate, 4 Wochen

Ist sie antisymmetrisch, weil wir in der Menge (1,2) und (2,1) haben? Sie sollte nur z.B. (1,2) enthalten?   -   evatsigkana, kommentiert vor 3 Monate, 4 Wochen

Zum Verständnis: Eine Relation zwischen zwei Mengen \( A \) und \( B \) ist in der Mathematik in erster Linie erstmal nur eine Teilmenge des kartesischen Produktes \( A \times B := \{(a,b) | a \in A , b \in B \} \).
Dabei sagt man das \( a \) in Relation zu \( b \) steht.
Nun nehmen wir zum Beispiel die Mengen \( A=B= \{1,2\} \) und basteln da die oben genannten Relationen \( R_1 \) und \( R_2 \) raus.
Überprüfen wir mal für \( R_1 \) ob die Relation eine partielle Relation ist
\( R_1 := \{ (1,1) , (1,2) , (2,2) \} \)
Reflexivität ist erfüllt, da die Tupel \( (1,1) \) und \( (2,2) \) in unserer Relation enthalten sind. Das bedeutet nämlich so viel wie, das 1 in Realtion zu 1 steht und 2 in Relation zu 2 steht.
Antisymmetrie ist auch erfüllt, da 1 zwar in Realtion zu 2 steht (\((1,2)\)), aber 2 steht nicht in Realtion zu 1 (\((2,1) \notin R_1 \)). Deshalb ist die Antisymmetrie sofort erfüllt.
Die Transitivität ist ebenfalls sofort erfüllt, da die Menge \( \{1,2\} \) keine drei Elemente enthält und somit sofort transitiv ist.
Analog können wir zeigen das \( R_2 \) eine partielle Relation ist.

So nun nehmen wir die Vereinigung von unseren partiellen Relationen
\( R_1 \cup R_2 = \{(1,1) , (1,2) , (2,1) , (2,2) \} \)
Aus den selben Gründen wie bei \( R_1 \) können wir die Reflexivität und Transitivität argumentieren.
Der Knackpunkt ist nun die Antisymmetrie.
\( (1,2) \in R_1 \cup R_2 \), das bedeutet das 1 in Realtion zu 2 steht. Nun ist aber auch \( (2,1) \in R_1 \cup R_2 \), das bedeutet aber das 2 in Relation zu 1 steht.
Jetzt bedeutet Antisymmetrie genau das wenn a in Realtion zu b steht und b in Realtion zu a, so muss a gleich b sein.
Das würde aber bedeuten das \( 1 = 2 \) gelten würde und dies ist nicht der Fall.
Also genau wie du es gesagt hast.

Ist es nun etwas verständlicher was man sich unter einer Realtion vorstellt?
Eine wirklich Bedeutung erhält die Relation erst wenn wir ihr auch eine zuweisen. Zum Beispiel in dem wir die Eigenschaft der reellen Zahlen nutzen das diese geordnet sind und als Relation die größe des Wertes vergleichen (also die Realtion > ). Daraus könnten wir nun auch solche Zahlenpaare ableiten. Aber in unserer Vorstellung ist es eben leichter wirklich die größe der Zahlen zu bewerten als sich die Mühe zu machen alle Paare aufzuschreiben. Deshalb lernt man Realtionen erstmal anders kennen.

Nun zum Schnitt. Auch hier musst du über diese Zahlenpaare argumentieren. Beide Relationen sind über der selben Zahlenmenge.
Zuerst zur Reflexivität.
Dies ist eigentlich ziemlich trivial. Beide Relationen müssen für jedes \( x \in A \) das Tupel \( (x,x) \) enthalten (da beide Relationen selbst reflexiv sind), Somit muss der Schnitt auch diese Tupel enthalten.
Schaffst du die anderen beiden Eigenschaften?
Als Tipp: der Schnitt erhält die Eigenschaft entweder weil die Paare in beiden Realtionen vorkommen, oder eben nur in einer und somit auch die Konsequenz nur in einer also kommt es eben nicht im Schnitt vor.

Grüße Christian
  -   christian strack, verified kommentiert vor 3 Monate, 4 Wochen

So toll wie du alles erklärt hast, kann ich natürlich nicht. Aber ich habe verstanden und hoffe, dass ich die Klausur am 22.7. bestehen werde. Wie erwähnt, ich bin Philologin und finde Mathe faszinierend.
Nun ist die Transitivität auch erfüllt, weil die Menge nur zwei Elemente erhält. Ich dachte bisher, dass wir unbedingt drei Elemente brauchen, damit wir die Transitivität zeigen können.
Zu der Antisymmetrie, kommen nicht beide Tupel (1,2) und (2,1) vor? Ich habe nicht verstanden, warum nur das eine Paar vorkommen kann?
Beste Grüße
Eva
ps. Verzeihe bitte die naiven Fragen
  -   evatsigkana, kommentiert vor 3 Monate, 4 Wochen

Kein Problem. Immer alle Fragen heraus :)

Die Transitivität bedeutet nur, das wenn wenn ein Element a mit dem Element b in Relation steht und b in Relation zu c steht auch a in Realtion zu c stehen muss.
Nun ist die Negation der Aussage aber: Wenn ein Element a mit einem Element b in Realtion steht, und b mit c in Relation steht, dann ist die Relation nicht transitiv, wenn a nicht zu c in Relation steht.
Da diese Situation nicht ensteht für ungleiche a,b und c ist jede Relation auf einer Menge mit 2 Elementen auch transitiv.
Wenn du dir diese Eigenschaft bei der größer gleich Relation vorstellst, ist sie dafür da um eine eindeutige Ordnung herzustellen. Da die 4 größer als die 3 ist und die 3 größer als die 2 ist die 4 auch größer als die 2.
Diese eindeutige Ordnung haben wir ja auch auf der Menge \( \{1,2\} \) auch wenn nur zwei Elemente drin sind.

Vielleicht wird es klar wenn ich die Antisymmetrie etwas anders darstelle.
Nehmen wir nochmal die größer gleich Relation
Wenden wir diese Relation auf eine Zahlenmenge an. Dann bedeutet Antisymmetrie, das wenn \( a \geq b \) und \( b \geq a \) natürlich \( a=b \) gelten muss. Das liegt daran, da keine Zahl größer und kleiner als eine andere Zahl sein kann. Also müssen sie gleich sein.
Beziehen wir uns nun auf eine Menge von Häusern und vergleichen die Höhe von Häusern einer Straße
Sagen wir das erste und das zweite Haus sind gleich groß. Das bedeutet das Haus 1 in Relation zu Haus 2 steht und umgekehrt auch. Allerdings sind dies zwei unterschiedliche Häuser, also ist die Gleichheit nicht erfüllt.
Auf der Menge der Häuser ist die Relation also nicht Antisymmetrisch.
Nun auf unser Beispiel bezogen, wir können sagen das die Relation \( R_1 \) die Relation \( \leq \) ist, auf der Menge \( \{1,2\} \). Nun gilt \( 1 \leq 1 , \ 1 \leq 2 , \ 2 \leq 2 \). Andere Zusammenhänge stimmen nicht. Wir erhalten also die Zahlenpaare \( R_1 = \{(1,1) , (1,2), (2,2) \} \).
Nun machen wir das selbe mit der Relation \( R_2 := \geq \). Wir erhalten \( R_2 = \{(1,1) ,(2,1) , (2,2) \} \)
\( R_1 \cup R_2 = R_3 = \{ (1,1) , (1,2) , (2,1) , (2,2) \} \)
schauen wir uns die Vereinigung an, so haben wir größen von Zahlen verglichen. Da jetzt sowohl \((1,2) \in R_3 \) als auch \( (2,1) \in R_3 \) liegt, würde die Antisymmetrie bedeuten, das die Zahlen 1 und 2 die gleiche größe besitzen. Aber das sind sie natürlich nicht.

Grüße Christian
  -   christian strack, verified kommentiert vor 3 Monate, 4 Wochen

Vielen Dank, Christian! DIe Beispiel mit den Zahlen und den Häusern waren ziemlich hilfreich ;) Ich muss weiter üben. Ich werde morgen mit Mathe weitermachen und eventuell kommen Fragen. Jetzt lerne ich C++ ..

Herzlichen Gruß
Eva
  -   evatsigkana, kommentiert vor 3 Monate, 4 Wochen

Das freut mich sehr :)
Melde dich einfach. Viel Erfolg

Grüße Christian
  -   christian strack, verified kommentiert vor 3 Monate, 4 Wochen
Kommentar schreiben Diese Antwort melden