Binär-Sitzungen

Eine binäre Sitzung ist eine spezielle Art von Sitzung mit Arität zwei. Typische binäre Relationen sind weniger als, Gleichheit, Teilbarkeit, größer als, usw.

Beispiele

Eine binäre Relation ist eine der typischen und am häufigsten vorkommenden Relationen. Sie hat auch einige interessante Eigenschaften, die wir hier beschreiben werden.

Ein Beispiel für eine binäre Relation kann sein: die Relation "Vater-Sohn", das Paar "Fahrzeug - Anzahl der Räder" oder die allgemeinere Relation "Objekt - Eigenschaft des Objekts". Das Objekt kann ein Tier sein, und die Eigenschaft kann die Anzahl der Beine, die Lebenserwartung, die Anzahl der Haare auf dem Kopf und so weiter sein.

Die binäre Relation R zwischen den Mengen M₁ und M₂ kann wie folgt definiert werden: R ⊆ M₁ × M₂ Eine binäre Beziehung ist also eine Menge von Paaren, wobei diese Menge eine Teilmenge des kartesischen Produkts der beiden Mengen ist, zwischen denen wir die Beziehung herstellen. Eine Vater-Sohn-Beziehung kann also eine Beziehung zwischen Mengen aller Menschen, zwischen Mengen aller Menschen in Europa oder in Prag sein. Wir können die Menge auch in eine andere Richtung einschränken, wir können sagen, dass wir die Beziehung zwischen den Mengen aller Menschen definieren, nicht der Menschen im Allgemeinen.

Für binäre Relationen verwenden wir normalerweise eine spezielle Notation. Anstelle von [a, b] ∈ R können wir aRb schreiben. Anstelle von [3, 1] ∈ > können wir beispielsweise 1 > 3 schreiben. Ähnlich verhält es sich mit anderen Sitzungen. Die Schreibweise aSb ist also äquivalent zur Schreibweise [a, b] ∈ S.

Inverse Sitzungen

Eine inverse Sitzung ist eine der aktuellen Sitzung entgegengesetzte Sitzung (nicht zu verwechseln mit einer Komplement-Sitzung). Was ist der Kehrwert einer Sitzung kleiner als? Wenn die Sitzung weniger als das Element [4, 7] enthält, d. h. 4 < 7, dann ist das inverse Element das Gegenteil von: 7 > 4, das Inverse von [7, 4] in der inversen Sitzung.

Wenn wir eine Sitzung R ⊆ M₁ × M₂ haben, dann konstruieren wir die inverse Sitzung R⁻¹, indem wir alle Elemente von [a, b] ∈ R nehmen und ihr Inverses in R⁻¹ einfügen. Wenn also die Sitzung R das Element [a, b] enthält, dann muss die Sitzung R⁻¹ das Element [b, a] enthalten. Umgekehrt gilt: Wenn R⁻¹ das Element [b, a] enthält, dann muss die Sitzung R das Element [a, b] enthalten.

Wenn wir dies definieren, dann ist die Sitzung R⁻¹ die Umkehrung von R, wenn sie gerade zutrifft:

$$\forall a\in M_1,\forall b\in M_2:\quad [a, b]\in R \Leftrightarrow [b, a]\in R^{-1}$$

6 < 8 gilt nur dann, wenn 8 > 6. Ähnliches gilt für andere Paare.

Falten von Sitzungen

Wir können binäre Sitzungen miteinander stapeln. Nehmen wir an, wir haben zwei Sitzungen, die erste, R, wäre "der Vater meines Sohnes sein" und die zweite, S, wäre "der Bruder meiner Schwester sein". Die Sitzung R enthält also die Paare [otec, syn], und die zweite Sitzung enthält die Paare [bratr, sestra].

Versuchen wir nun, die Sitzungen zusammenzufügen. Wir erhalten eine neue Sitzung, nennen wir sie $R \circ S$, und diese Sitzung enthält das Element [a, c] ebenso wie [a, b] ∈ R und gleichzeitig [b, c] ∈ S. Beachten Sie, dass beide Elemente b enthalten, einmal an der zweiten Position und dann an der ersten Position des Paares. Dies ist eine Art verbindendes Element der Faltung.

Beispiel: R = {[Tonda, Marek], [Petr, Jakub]} und S = {[Marek, Jana], [Marek, Lenka], [Jakub, Lucie]}. Tonda ist der Vater von Mark, Peter ist der Vater von James. Marek hat Schwestern Jana und Lenka und Jakub hat eine Schwester Lucia.

Nun werden wir die Sitzung $R \circ S$ zusammenstellen. Wir suchen nach einem solchen Paar aus R, das jemanden anstelle eines Sohnes hat, der in der Sitzung S als Bruder aufgeführt ist. Zum Beispiel diese beiden Paare: [Tonda, Marek] und [Marek, Jana]. Mark ist ein verbindendes Element, wir brauchen es nicht mehr, und wir erstellen ein neues Paar aus den übrigen Namen: [Tonda, Jana] Die Sitzung $R \circ S$ enthält also das Paar [Tonda, Jana]. Marek hat eine weitere Schwester, Lenka, und wir fügen sie der zusammengesetzten Sitzung hinzu: [Tonda, Lenka]. Schließlich bleibt uns noch der Sohn Jakub. Er hat eine Schwester Lucia. Wir haben also zwei Paare: [Petr, Jakub] und [Jakub, Lucie]. Dadurch entsteht ein weiteres Element: [Petr, Lucie].

Das Ergebnis ist die Sitzung: $R \circ S = {[Tonda, Jana], [Tonda, Lenka], [Petr, Lucie]}$. Wie könnten wir diese Sitzung nennen? Wahrscheinlich "ein Vater für seine Tochter sein".

Noch einmal die gesamte Definition:

$$[a, c] \in (R \circ S) \Leftrightarrow \exists b\quad [a, b] \in R \wedge [b, c] \in S$$

Hinweis: Manchmal wird die umgekehrte Schreibweise verwendet, d. h. für dieselbe Definition würde man $S \circ R$ anstelle von $R \circ S$ verwenden.