4b. Relationen (Lösungen)

Übung 1

Seien (A, <) und (B, <) lineare Ordnungen. Weiter sei C = A × B. Wir definieren eine Relation < auf C durch

(a₁, b₁) < (a₂, b₂), falls a₁ < a₂ oder a₁ = a₂ ∧ b₁ < b₂

(a)	Welche Relation ergibt sich für A = { 1, 2 } und B = { 1, 2, 3 } mit den üblichen Ordnungen 1 < 2 auf A und 1 < 2 < 3 auf B? (Listen Sie die Elemente von C = A × B konkret in der Form … < … < … auf.)

(b)	Zeigen Sie, dass < eine lineare Ordnung auf C ist.

(c)	Wo begegnen Ihnen eine derartige Ordnung und allgemeinere Versionen im Alltag? (Stichworte und kurze Beispiele genügen.)

Bemerkung: Die Ordnungen auf A, B und C werden zur Vereinfachung der Notation gleich bezeichnet. Genauer wäre <_A, <_B, <_C.

Lösung zur Übung 1

zu (a): Wir erhalten die Anordnung:

(1, 1) < (1, 2) < (1, 3) < (2, 1) < (2, 2) < (2, 3)

zu (b):

Irreflexivität: Sei (a, b)  ∈  A × B. Annahme, (a, b) < (a, b). Nach Definition der Ordnung auf C gilt

a < a oder a = a ∧ b < b

Der erste Fall ist nach Irreflexivität von < auf A ausgeschlossen. Analog ist der zweite Fall nach Irreflexivität von < auf b ausgeschlossen. Insgesamt ergibt sich also ein Widerspruch.

Transitivität: Seien (a₁, b₁), (a₂, b₂), (a₃, b₃)  ∈  C mit (a₁, b₁) < (a₂, b₂) und (a₂, b₂) < (a₃, b₃). Dann gelten:

(1A) a₁ < a₂	oder	(1B) a₁ = a₂ ∧ b₁ < b₂
(2A) a₂ < a₃	oder	(2B) a₂ = a₃ ∧ b₂ < b₃

Damit sind vier Fälle möglich:

Gilt (1A) und (1B), so gilt a₁ < a₃ nach Transitivität von < auf A. Folglich gilt (a₁, b₁) < (a₃, b₃).

Gilt (1A) und (2B), so gilt a₁ < a₃ und damit (a₁, b₁) < (a₃, b₃).

Gilt (1B) und (2A), so gilt a₁ < a₃ und damit (a₁, b₁) < (a₃, b₃).

Gilt (1B) und (2B), so gilt a₁ = a₃ und b₁ < b₃ nach Transitivität von < auf B. Damit gilt auch in diesem Fall (a₁, b₁) < (a₃, b₃).

In jedem Fall gilt also (a₁, b₁) < (a₃, b₃).

Vergleichbarkeit: Seien (a₁, b₁), (a₂, b₂)  ∈  C. Nach Vergleichbarkeit in A gilt:

a₁ < a₂ oder a₁ = a₂ oder a₂ < a₁

In ersten Fall gilt (a₁, b₁) < (a₂, b₂), dritten (a₂, b₂) < (a₁, b₁). Es gelte also a₁ = a₂. Nach Vergleichbarkeit in B gilt

b₁ < b₂ oder b₁ = b₂ oder b₂ < b₁

Im ersten Fall erhalten wir (a₁, b₁) < (a₂, b₂), im zweiten (a₁, b₁) = (a₂, b₂), im dritten (a₂, b₂) < (a₁, b₁). In allen Fällen sind also die beiden Elemente von C vergleichbar.

zu (c): Tabellarische Anordnung nach Haupt- und Nebenkriterium. Zum Beispiel bei Sportergebnissen.

Der Ordnungstyp entsteht, wenn gewisse Objekte nach einem Hauptmerkmal tabellarisch angeordnet werden und bei übereinstimmendem ersten Merkmal nach einem zweiten. Dabei wird vorausgesetzt, dass sich je zwei Objekte in mindestens einem Merkmal unterscheiden. Beispiel: Anordnung einer Ergebnisliste nach der Klausur-Note und bei übereinstimmender Note nach der Matrikelnummer. Allgemein ist der Typ als „lexikographische Ordnung“ bekannt, wobei hier endliche Tupel durch schrittweisen Vergleich der Einträge angeordnet werden und nicht nur Paare (im Lexikon jeweils nach A bis Z). Beispiel Fußball: Erzielte Punkte, Tordifferenz, Anzahl der geschossenen Tore, direkter Vergleich, Losentscheid.

Übung 2

Wir betrachten die übliche lineare Ordnung < auf den natürlichen Zahlen ℕ und definieren eine Relation ≼ auf ℕ² = ℕ × ℕ durch

(a, b) ≼ (c, d), falls a + b ≤ c + d

(a)	Welche Eigenschaften (reflexiv, irreflexiv, symmetrisch, antisymmetrisch, transitiv, Vergleichbarkeit) gelten für die Relation ≼ und welche sind verletzt? Begründen Sie Ihre Antworten durch einen Beweis oder ein Gegenbeispiel.

(b)	Visualisieren Sie die Relation mit Hilfe eines Diagramms.

Lösung zur Übung 2

Im Folgenden seien (a, b), (c, d) usw. stets Elemente von ℕ².

zu (a):

Reflexivität: Gültig. Für alle (a, b) gilt (a, b) ≼ (a, b), da a + b ≤ a + b.

Irreflexivität: Nicht gültig. Gegenbeispiel: (0, 0) ≼ (0, 0).

Symmetrie: Nicht gültig. Gegenbeispiel:

((0, 0) ≼ (0, 1), non((1, 0) ≼ (0, 0)).

Antisymmetrie: Nicht gültig. Gegenbeispiel:

(0, 1) ≼ (1, 0), (1, 0) ≼ (0, 1), (0, 1) ≠ (1, 0)

Transitivität: Gültig. Ist (a, b) ≼ (c, d) und (c, d) ≼ (e, f), so ist a + b ≤ c + d ≼ e + f, sodass (a, b) ≼ (e, f).

Vergleichbarkeit: Gültig. Seien (a, b), (c, d) beliebig. Dann gilt

a + b ≤ c + d oder c + d ≤ a + b.

Im ersten Fall ist (a, b) ≼ (c, d), im zweiten (c, d) ≼ (a, b).

Bemerkung: Für eine lineare Ordnung fehlt die Irreflexivität. Identifizieren wir Paare mit gleicher Komponentensumme (über die Äquivalenzrelation (a, b) ∼ (c, d), falls a + b = c + d), so erhalten wir eine lineare Ordnung auf den Äquivalenzklassen.

zu (b):

Die Tupel (a, b) mit gleicher Komponentensumme bilden Diagonalen im (ℕ × ℕ)-Gitter. Die Relation ≼ ordnet (mit obiger Bemerkung) die Diagonalen nach aufsteigender Komponentensumme an.