Ordnungsrelationen auf X={1,2,3}

[mezger]

Hallo,

wie finde ich alle Ordnungsrelationen auf X. Haben diese definiert als antisymmetrisch, reflexiv und transitiv.

XxX sind
(1,1) (1,2) (1,3)
(2,1) (2,2) (2,3)
(3,1) (3,2) (3,3)

Die Relationen sind also Teilmengen davon.

Auf Grund der Reflexivität müssen alle Ordnungsrelationen die Paare (1,1) (2,2) und (3,3) enthalten.

Also ist die erste mögliche Relation 1: (1,1) (2,2) (3,3)

Dann gibt es Relation 2 (<=):
(1,1) (1,2) (2,2) (2,3) (3,3)

Relation 3 (>=):
(3,3) (3,2) (2,2) (2,1) (1,1)

Was ist mit Relation 4?:
(2,2) (2,1) (1,1) (1,3) (3,3)

Ist doch reflexiv, transitiv und antisymetrisch, oder?

Und was ist mit Relation 5?:
(3,3) (2,2) (1,1) (1,3) (1,2)
Geht doch auch?

Viele Grüße

mezger

[Gunnar Bittersmann]

@@mezger:

nuqneH

wie finde ich alle Ordnungsrelationen auf X. Haben diese definiert als antisymmetrisch, reflexiv und transitiv.

Hm, ich hätte von einer Ordnungsrelation auch erwartet, total zu sein. Aber laut Wikipedia unterscheidet man zwischen Halbordnung und Totalordnung.

XxX sind
(1,1) (1,2) (1,3)
(2,1) (2,2) (2,3)
(3,1) (3,2) (3,3)

X × X ist eine Menge, also schreib das bitte auch so: X × X = X² = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}

Auf Grund der Reflexivität müssen alle Ordnungsrelationen die Paare (1,1) (2,2) und (3,3) enthalten.

Also ist die erste mögliche Relation 1: (1,1) (2,2) (3,3)

Als Menge geschrieben wäre es OK.

Dann gibt es Relation 2 (<=):
(1,1) (1,2) (2,2) (2,3) (3,3)

Nein, {(1,1), (1,2), (2,2), (2,3), (3,3)} ist keine Ordnungsrelation; sie erfüllt nicht alle gestellten Bedingungen.

Aber hübsch der Reihe nach. Warum gehst du nicht systematisch vor und fügst {(1,1), (2,2), (3,3)} _ein_ Element aus X² hinzu?

Nehmen wir (1,2): Erfüllt {(1,1), (1,2), (2,2), (3,3)} die geforderten Eigenschaften? Wenn ja, hättest du eine weitere Halbordnung.

Und kannst statt (1,2) natürlich jedes andere Element (x₁,x₂) aus X² mit x₁ ≠ x₂ zu {(1,1), (2,2), (3,3)} hinzufügen.

Und dann weiter: Zu {(1,1), (1,2), (2,2), (3,3)} ein weiteres hinzufügen. Geht (1,3)?

Geht (2,1)? Offensichtlich nicht, weil das die Antisymmetrie verletzt.

Dass (2,3) _allein_ nicht geht, hatte ich oben schon gesagt.

So kannst du deine gefundenen Ordnungsrelationen Schritt für Schritt erweitern, bis du schließlich alle hast.

Qapla'

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

nuqneH

Also ist die erste mögliche Relation 1: (1,1) (2,2) (3,3)

Warum sollte das die erste sein? Wie wär’s mit {(1,1)} etc.?

Qapla'

[mezger]

Hi,

Warum sollte das die erste sein? Wie wär’s mit {(1,1)} etc.?

Auf der Menge M={1,2,3} wäre doch die Relation {(1,1)} keine Ordnungsrelation, da nicht jedes x aus M zu sich selbst in Relation steht, das ganze wäre also nicht reflexiv?

Grüße

[Gunnar Bittersmann]

@@mezger:

nuqneH

Auf der Menge M={1,2,3} wäre doch die Relation {(1,1)} keine Ordnungsrelation, da nicht jedes x aus M zu sich selbst in Relation steht, das ganze wäre also nicht reflexiv?

Stimmt.

Also ist {(1,1), (2,2), (3,3)} doch ein guter Anfang.

Qapla'

[mezger]

Hi,

Dann gibt es Relation 2 (<=):
(1,1) (1,2) (2,2) (2,3) (3,3)

Nein, {(1,1), (1,2), (2,2), (2,3), (3,3)} ist keine Ordnungsrelation; sie erfüllt nicht alle gestellten Bedingungen.

Es müsste auch das Paar (1,3) Element der Menge sein, richtig? Wegen der Transitivität?

Aber hübsch der Reihe nach. Warum gehst du nicht systematisch vor und fügst {(1,1), (2,2), (3,3)} _ein_ Element aus X² hinzu?

Also ist dies doch die "erste" bzw. der Grundbaustein für die anderen Relationen?

Nehmen wir (1,2): Erfüllt {(1,1), (1,2), (2,2), (3,3)} die geforderten Eigenschaften? Wenn ja, hättest du eine weitere Halbordnung.

Ja.

Und kannst statt (1,2) natürlich jedes andere Element (x₁,x₂) aus X² mit x₁ ≠ x₂ zu {(1,1), (2,2), (3,3)} hinzufügen.

Ja, wären also schonmal 12 weitere Ordnungsrelationen, richtig?

Und dann weiter: Zu {(1,1), (1,2), (2,2), (3,3)} ein weiteres hinzufügen. Geht (1,3)?

Geht zusätzlich (1,3)?

Wie ist denn die Anzahl der gesamt möglichen Ordnungsrelationen?

Grüße

[Gunnar Bittersmann]

@@mezger:

nuqneH

Nein, {(1,1), (1,2), (2,2), (2,3), (3,3)} ist keine Ordnungsrelation; sie erfüllt nicht alle gestellten Bedingungen.

Es müsste auch das Paar (1,3) Element der Menge sein, richtig? Wegen der Transitivität?

So isses.

Und kannst statt (1,2) natürlich jedes andere Element (x₁,x₂) aus X² mit x₁ ≠ x₂ zu {(1,1), (2,2), (3,3)} hinzufügen.

Ja, wären also schonmal 12 weitere Ordnungsrelationen, richtig?

?? Wie kommst du auf 12? X² enthält doch nur 9 Elemente, und nur für 6 davon gilt x₁ ≠ x₂.

Und dann weiter: Zu {(1,1), (1,2), (2,2), (3,3)} ein weiteres hinzufügen. Geht (1,3)?

Geht zusätzlich (1,3)?

Das frag ich dich doch. Ist die Relation {(1,1), (1,2), (1,3), (2,2), (3,3)} antisymmetrisch, reflexiv und transitiv?

Wie ist denn die Anzahl der gesamt möglichen Ordnungsrelationen?

Das könnte ich glatt als kleine Denksportaufgabe mal auszählen … Aber ich will nicht deine Hausaufgaben machen.

Qapla'