Partialordnung

13.12.2004, 14:55

sunset85

Partialordnung

hi,

ich habe folgende frage: was ist eine partialordnung und wie wende ich sie auf folgendes bsp an:

betrachte die Relation "x tielt y" auf der Menge {1,2,3,6,12,18}, ich soll zeigen, dass dies eine partialordnung definiert und einen dazugehörigen graphen zeichnen....??????

wie geht das??

13.12.2004, 15:07

Tobias

Auf diesen Beitrag antworten »

Wir sagen $\begin{eqnarray*} M := \big\{ 1,2,3,6,12,18 \big\} \end{eqnarray*}$

Eine Ordnung $\begin{eqnarray*} R \subseteq M \times M \end{eqnarray*}$ ist partiell, wenn sie reflexiv, antisymmetrisch und transitiv ist. Dabei dürfen aber auch Elemente aus $\begin{eqnarray*} M \times M \end{eqnarray*}$ existieren, die nicht Element der Ordnungsrelation sind.

Du musst also zeigen:

Jedes Element teilt sich selber (reflexiv).
Wenn für ungleiche a, b gilt "a teilt b", dann gilt nicht "b teilt a" (antisymmetrisch).
Wenn gilt "a teilt b" und "b teilt c", dann auch "a teilt c". (transitiv).

Im Graphen repräsentieren Knoten (Ecken) die Elemente aus M. Es existiert eine Kante von x nach y, wenn (x, y) in der Ordnungsrelation steckt. Bei einer reflexiven Relation kann man sich dann noch überlegen, ob man jeweils eine Schlinge an jeden Knoten malt.

13.12.2004, 18:45

sunset85

Auf diesen Beitrag antworten »

ok, mal langsam....

ich hab bei diesem bsp mehrere aufgaben, zunächst soll ich die geordneten paare (x,y) der relation angeben.

ist das: (1,2) (2,3) (3,6) (6,12) (12,18)??????

dann ist die frage welche vorgänger hat 6?

soll das 1,2,3 sein??? oder 1,2,3,4,5???? ich denk mal nur die, die in der menge vorkommen oder versteh ich das falsch??

und dann noch welchen unmittelbaren vorgänger 6 hat? das wäre dann 3???

und jetzt kommt: zeige, dass dies eine partialordnung definiert!

reflexiv: es sind alles natürliche zahlen, also teilen sie sich selbst, also richtig!

antisymmetrisch: 1 teilt 2, aber 2 nicht 1
2 teilt 3 nicht und umgekehrt auch nicht
aber 3 teilt 6, 6 aber nicht 3
6 teilt 12, aber 12 nicht 6
12 teilt nicht 18, und 18 nicht 12

ist es trotzdem antisymmetrisch??? obwohl es bei 2 elementen nicht stimmt??

transitiv: 1 teilt 2, 2 teilt nicht 3, aber 1 teilt 3???

aber hier: 3 teilt 6, 6 teilt 12 und 3 teilt 12 also richtig!

17.03.2014, 12:05

Kollege

Auf diesen Beitrag antworten »

Gemeint sind glaube ich die geordneten Paare bezüglich der Relation.
Also wenn 'x teilt y' deine Relation ist und die Menge {1,2,3,6,12,18}, dann wären zum Beispiel (1,1), (2,6) oder (6,18) geordnete Paare (1 teilt 1, 2 teilt 6, 6 teilt 18 usw)

Wenn du deine geordneten Paare hast, nennt sich das x zu einem y Vorgänger (2 teilt 12, also ist 2 ein Vorgänger zu 12, x = 2, y = 12)
Ein unmittelbarer Vorgänger bedeutet nur, dass es keine weitere Vorgänger zwischen dem Vorgänger und dem dazugehörigen y gibt. (z.B. 6 teilt 12, 6 wäre kein unmittelbarer Vorgänger, 12 teilt 12, 12 ist ein unmittelbarer Vorgänger)

Was die Halbordnung angeht:
Antisymmetrie bestimmst du wie einen logischen Schluss. Wenn alle Prämissen stimmen muss auch der Schluss stimmen. In deinem Fall stimmt das: Antisymmetrie besteht wenn
x p y ^ y p x -> x = y
Das bedeutet: WENN (!) x p y UND y p x zutrifft, dann sind x und y ein und dasselbe Augenzwinkern