Befinden sich zwei Elemente immer in einer Beziehung innerhalb einer teilweise geordneten Menge?

7

Kann ich in einem teilweise geordneten Satz immer zwei beliebige Elemente aus dem Satz bestellen? Oder ist es möglich, dass zwei Elemente innerhalb der Menge keine Ordnungsbeziehung zueinander haben?

Wenn zum Beispiel drei Elemente und und , muss dann entweder oder gelten?{a,b,c}abacbccb

Ich brauche dies, um die Fixpunkttheorie für die Semantik von Programmiersprachen (Bezeichnung von while-Schleifen) zu verstehen.

großmütig
quelle
Ich weiß, dass das Tag wahrscheinlich falsch ist, aber ich habe keine Ahnung, welches Tag ich wählen soll. Könnte jemand, der besser informiert ist, die Frage bitte wiederholen? Ich bin mir auch nicht sicher, ob dies überhaupt hier passt oder lieber nach math.SE verschoben werden sollte. Wenn ja, bitte umziehen. :)
Magnattic
2
Die Frage ist hier in Ordnung. Teilaufträge werden in CS häufig verwendet.
Dave Clarke
Missbrauch eines Kommentars von Jeffe: Manchmal ist ein roter Hering buchstäblich ein Hering.
Raphael
4
Insbesondere hat jede Menge eine triviale Teilreihenfolge, in der kein Paar unterschiedlicher Elemente vergleichbar ist. Es wird normalerweise mit = bezeichnet.
JeffE

Antworten:

8

In einem teilweise geordneten Satz kann es Mitglieder geben, die nicht vergleichbar sind. Eine Teilreihenfolge, in der alle Elemente vergleichbar sind, wird als Gesamtreihenfolge bezeichnet .

Wir sagen a und b sind vergleichbar, wenn mindestens eine der folgenden Bedingungen erfüllt ist:

  • ab,
  • ba.
Kaveh
quelle
7

In einem teilweise bestellten Set (kurz Poset) können Sie habenab und ac ohne b und c vergleichbar sein (dh auch nicht bc Noch cbhält). Das macht es zu einer Teilbestellung und nicht zu einer Gesamtbestellung . Mathematiker meinen oft eine Gesamtreihenfolge, wenn sie "Ordnung" sagen, weil das Hauptbeispiel einer geordneten Menge die reellen Zahlen (oder Teilmengen wie die natürlichen ganzen Zahlen) sind; Informatiker verwenden mehr Teilordnungen auf elementarer Ebene. Nehmen Sie in CS also Teilordnungen an, sofern nicht insgesamt angegeben.

Ein typisches Beispiel für Poset ist Set Inclusion: {x}{x,y} und {x}{x,z}, aber keiner von {x,y} und {x,z} ist eine Teilmenge des anderen.

In der Denotationssemantik entstehen häufig Posets , die eine Menge Wissen über ein Programm darstellen.ab bedeutet, dass b ist eine bessere Annäherung an das Verhalten des Programms als a. Zum Beispiel wenna ist "das Programm ist eine Funktion aus den ganzen Zahlen, die für alle Eingaben endet", b ist "das Programm berechnet die Nachfolgerfunktion" und c ist dann "das Programm berechnet die Doppelfunktion" ab und ac aber b und c sind nicht vergleichbar.

Gilles 'SO - hör auf böse zu sein'
quelle