Ordnungsrelation beweisen

Hallo Forum,

ich habe diese Aufgabe:
aRb :<=> a + b = a
R sei eine Relation und auf der Boolesche Algebra (B,+,*) definiert. Zeigen Sie das R eine Ordnungsrelation ist.

1. Leider habe ich in der Vorlesung gefehlt, so dass ich nicht genau weiß was die Eigenschaften einer Ordnungsrelation sind. Im Wiki sind ja eine Menge Ordnungsrelationen: http://de.wikipedia.org/wiki/Ordnungsrelation
Und die Anzahl der Eigenschaften sind auch nicht wenige: http://mo.mathematik.uni-stuttgart.de/inhalt/aussage/aussage82/
Oder anders gefragt: Wenn der Mathematiker Ordnungsrelation sagt, welche meint er dann?

2. Wie werden da die Elemente geordnet?
Wenn ich mir Transitivität nehme:
aRb und bRc muß aRc folgen.
aRb=a und bRc=b, aber aRc=a. Was passiert hier?

Vielen Dank

Luigi

Jester

typischerweise fordert man das was Halbordnung heißt: Reflexivität, Transitivität und Antisymmetrie. Der Prototyp davon ist <= etwa auf den reellen Zahlen.

Also die 3 Eigenschaften. Könntest Du mir einen Tip geben wie diese Ordnungsrelation funktioniert? Also wenn ich eine Liste aus 3 Booleschen Variablen habe: {a, b, c} wie werden die geordnet?

Bashar

Wieso willst du eine Liste ordnen? Sowas kommt in den Eigenschaften einer Halbordnung nicht vor. Du musst einfach die drei Eigenschaften prüfen.

Jester

Exakt, Du vergleichst immer nur Paare. Außerdem ergibt sich nicht immer eine Totalordnung, es müssen also nicht alle Elemente miteinander vergleichbar sein. Ein beliebites Beispiel dafür ist Teilbarkeit auf den natürlichen Zahlen.

Also ist es eine Ordnungsrelation. Trotzdem sind bezüglich dieser Ordnungsrelation beispielsweise 3 und 5 nicht vergleichbar, es gilt weder 3|5 noch 5|3.

Hm, durchs Internet habe ich immer die Analogie zu >= auf R im Kopf.

Würde ich die Antisymmetrie so zeigen:
Wenn aRb und bRa gilt folgt daraus a=b
1. Da aRb gilt muß b gleich Null sein, wegen a + b = a
2. Da bRa gilt muß a gleich Null sein, wegen b + a = b
3. Folglich gilt dann immer a=b.

Bashar

Luigi_X schrieb:

1. Da aRb gilt muß b gleich Null sein, wegen a + b = a

Nein, siehe http://de.wikipedia.org/wiki/Boolesche_Algebra

Nach Deinem Link ist es Neutralitätsgesetz 5'.
Wenn a + x = a für ein beliebiges a gelten soll, dann muß x das neutrale Element der Addition sein. Und dieses ist 0.

Bashar

Aus a+0=a folgt doch nicht, dass a+b=a nur für b=0 gilt. Außerdem ist + hier keine Addition.

Das kam wohl auch in der Vorlesung, in der nicht da warst.

Ok, habs mir nochmal überlegt.
Vielen Dank Jester und Bashar.