Meine Damen und Herren, ich möchte Sie dann ganz herzlich zur zweiten Vorlesung Theorie der

Programmierung begrüßen. Heute das letzte Mal mit mir, wahrscheinlich, ab nächste Woche macht

das dann der Professor Schröder, der eigentlich auch im Plan steht. Bevor es losgeht, noch eine

Ankündigung organisatorischer Art und zwar möchte ich alle diejenigen Teilnehmer, die sich für eine

der Freitagsübungen angemeldet haben, bitten doch nach der Vorlesung noch mal hier zu bleiben. Der

Herr Rauch wird dann noch mal kommen und diese wenigen Leute, weil es zu wenig sind, um die Übung

zu füllen, für die gucken wir, ob wir sie woanders eingliedern. Also alle die Freitags sich angemeldet

haben, bitte mal nach der Vorlesung hier bleiben. Gut, ansonsten sind wir mitten in den Mathematik-

preliminarien und da waren wir beim letzten Mal also im Relationen-Kalkül stecken geblieben und da

machen wir also noch ein bisschen weiter Wiederholung, sollte das eigentlich sein. Ich erinnere noch mal

kurz daran, wo wir ungefähr standen. Also momentan befassen wir uns jetzt gerade mit binären

Relationen auf einer Menge oder zwischen zwei Mengen, also eine binäre Relation. Das ist ja

eine Teilmenge von x Kreuz y, wobei x und y irgendwelche Mengen sind, ja also zum Beispiel

Personen und wenn x gleich y ist, dann sagt man auch, dass es eine Relation auf einer Menge ist.

So, dann hatten wir uns Relationen-Konstruktionen angeguckt, nämlich einmal die Identitätsrelation.

Das ist eigentlich nicht wirklich eine richtige Konstruktion, aber eine sehr wichtige Relation

oder auch die Gleichheitsrelation. Das ist also die Relation, wo ich jedes Paar zu sich selbst in

Beziehung setze und weiter nichts. Dazu muss ich jetzt natürlich auf einer Menge arbeiten.

Das ist dann eine Relation auf einer Menge, das heißt hier x ist gleich y. Und wir hatten uns noch

angeguckt, eine Komposition von Relationen. Also wenn ich zwei Relationen habe, r und s,

eine geht von x nach y, eine von y nach z. Dann gibt es eben diese Verknüpfung von

Relationen s Kringel r, die im Prinzip besteht aus allen den Paaren x, z, für die es ein y in der

Mitte gibt, also y in y mit x, r, y und y, s, z. Wir hatten da auch so hübsche grafische Bilder

gemalt, was das bedeutet, nämlich dass man also so entlang dieser Pfeile durch die mittlere Menge

durchgehen kann auf irgendeinem Weg. Das macht hier dieses Irgendein, das macht das es gibt hier an

der Stelle. Und das ist eben die Verkettung oder Komposition. Und wenn man das machen kann, also

so multiplizieren kann man auch Potenzen bilden. Und das ist jetzt wieder für eine Relation auf

einer Menge. Und da hatten wir also zunächst gesagt r hoch 0, das ist die Diagonalrelation

oder Identitätsrelation, dieses Delta. Und für irgendeine natürliche Zahl n, wenn ich schon r

hoch n habe, dann definiere ich r hoch n plus 1 dadurch, dass ich r verkette mit r hoch n. Also

das heißt dann insgesamt ist das dann hier die n plus 1 fache Komposition von r mit sich selbst.

Oder für n ist es dann die n fache. Was brauchen wir noch? Ach ja, r ob. Also wenn wir wieder eine

Relation haben zwischen zwei Mengen, dann ist die Umkehrrelation die, die dadurch entsteht,

dass man die Pfeile umdreht, wenn man die Paare in so einer Relation als gerichtete Pfeile ansehen

will. Das heißt, das sind alle die Paare y, x mit x, y. Also umgekehrte Reihenfolge liegen die in r.

Und das ist dann natürlich eine Teilmenge von y Kreuz x. Des Weiteren hatten wir noch für

Relationen auf einer Menge, binäre Relationen auf einer Menge, drei wichtige Eigenschaften

wiederholt, nämlich Reflexivität, Symmetrie und Transitivität, die wir jetzt nicht nochmal

anschreiben. Aber wir waren dann zu einem Hilfsatz, zu einem Lämmer gekommen, dass eben diese drei

Eigenschaften mit Hilfe von Verkettung und Identitätsrelationen charakterisiert. Und da

waren wir bis zum Statement gekommen. Und jetzt kommt halt noch der Beweis. Also für jede Relation

r auf einer Menge x gelten erstens, r ist reflexiv, genau dann, wenn die Identitätsrelation in r

enthalten ist, also Teilmenge ist als Menge von geordneten Paaren. Zweitens, r ist symmetrisch,

ich kürze das mal ab, Symmepunkt, genau dann, wenn r ob Teilmenge ist von r und Transitiv,

r ist Transitiv und das kürze ich mal mit Transpunkt ab, genau dann, wenn die Verkettung

von r mit sich selbst wieder in r enthalten ist. So, das war das Lämmer und jetzt geht's neu

weiter mit dem Beweis davon. Aber zunächst mal noch eine Beobachtung, nämlich hier bei dem zweiten

Punkt kann man die Teilmengebeziehung auch einfach äquivalent durch ein Gleichheitszeichen ersetzen

und das liegt daran, dass wenn ich ob zweimal durchführe, also diese ob Konstruktion hier,

dann kriege ich wieder die ursprüngliche Relation raus. Vielleicht schreiben wir das da noch mal als