Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Wir fangen an mit zwei Erinnerungen.

Eine Erinnerung an mathematisches Grundwissen, die kommt jetzt.

Wir fangen an mit der Binnere-Relation.

Es folgt eine Binnere-Relation zum Thema Terme und Substitution.

Was ist eine Binnere-Relation?

Eine Binnere-Relation ist ein Tier dieser Form.

Eine Teilmenge des Kreuzprodukts zweier Mengen.

Das ist eine Binnere-Relation zwischen X und Y.

Oft wollen wir Relationen gerne in infix Schreibweise schreiben.

Wenn R so eine Teilmenge ist, dann wollen wir X, R, Y schreiben.

Das ist eine abkürzende Schreibweise dafür, dass das X, Y ein Element von R ist.

Wir machen gleich ein Beispiel.

Man sieht, warum eine Teilmenge des Kreuzprodukts eine Relation ist.

Wir nehmen die Gleichrelation auf natürliche Zahlen.

Das ist eine Binnere-Relation. Ich vergleiche zwei Zahlen.

Die Mengen X und Y sind gleich.

Auf beiden Seiten des Gleichzeichens steht eine natürliche Zahl.

Welche Teilmenge ist das? Das kann man tautologisch schreiben.

Das ist die Menge aller Paare N, N aus N Kreuz N.

In dem Sinne, den wir uns normalerweise vorstellen, N kleiner gleich M ist,

ist nach der Schreibweise, die wir vorhin eingeführt haben, eine tautologische Gleichung.

Kleiner gleich ist die Menge derjenigen Elemente von N Kreuz N, die Elemente von kleiner gleich sind.

Genau dahin expandiert diese Schreibweise gemäß dieser Konvention.

Das besagt überhaupt nichts, was da steht. Es soll Ihnen nur intuitiv klar machen, warum eine Relation eine Teilmenge des Kreuzprodukts ist.

Das ist anders, typischerweise auf natürlichen Zahlen induktiv.

Deswegen setzen wir das mal in Anführungsstriche. Es ist eine absolut richtige Gleichung. Sie sagt nur nichts.

Dann gucken wir uns an Eigenschaften, die eine binäre Relation haben kann.

Die meisten binären Relationen, um die es uns gehen wird, werden solche Relationen sein, bei denen links und rechts vom Relationszeichen derselbe Typ steht.

Wir reden dann auch von einer binären Relation auf x und definieren ein paar Eigenschaften, die die haben kann oder auch nicht haben kann.

Zum Beispiel kann eine solche Relation reflexiv sein. Das heißt das Folgende.

Für alle x gilt x r x. Ich lasse den Bereich des Quantas jetzt mal weg. Das meint natürlich für alle x aus dieser Grundmenge groß x, sonst macht die Aussage gar keinen Sinn.

Jedes Element steht in Relation zu sich selbst. Was noch?

Eine Relation kann symmetrisch sein. Symmetrisch heißt, für alle x und y, natürlich wieder aus x gilt, wenn x in Relation r zu y steht, dann

dann auch umgekehrt. Dann steht auch y in Relation r zu x. Man fragt sich kurz, warum ich hier nicht ein Äquivalenzzeichen hinschreibe.

Warum also nicht x in Relation r zu y steht, genau dann, wenn y in Relation r zu x steht. Die einfache Antwort ist die Umkehrung. Die folgt natürlich.

Wenn ich hiermit anfange, dann kann ich natürlich da genauso gut diesen Quantor darauf spezialisieren, indem ich die Variablen gerade andersrum substituiere und bekomme dann dieselbe Implikation in der umgekehrten Richtung.

So, dann. Eine Relation kann transitiv sein. Das heißt, muss ich jetzt über drei Elemente reden, für alle x, y und z gilt,

wenn ich so eine Zweierkette habe, also x steht in Relation r zu y und y steht in Relation r zu z, dann kann ich die abkürzen. Das heißt, es gilt bereits x r z.

So, dann kommt jetzt der einzige Begriff, den Sie vielleicht noch nicht kennen. Wir nennen r eine Präordnung, wenn eine Kombination dieser Eigenschaften gilt, nämlich

wenn r reflexiv und transitiv ist, dann nennt man r eine Präordnung. Was wir hier zunächst mal eingangs jedenfalls nicht brauchen werden, ist der Begriff der Ordnung.

Der ist schärfer als der der Präordnung, deswegen heißt das Präordnung bei einer Ordnung kommt noch Antisemitrie dazu, wenn zwei Elemente gegenseitig vergleichbar sind, sind sie schon gleich.

Das ist also genau der Unterschied hier, nicht an einer Präordnung kann es passieren, dass wenn ich die jetzt mal kleiner gleich nenne, x kleiner gleich y ist und y kleiner gleich x und y und y aber trotzdem verschieden sind.

Deswegen heißt das eine Präordnung. So, dann. So, und letztens r heißt eine Äquivalenz oder wenn das missverständlich ist länger eine Äquivalenzrelation.

Wenn r alle drei Eigenschaften hat, also symmetrisch, reflexiv und transitiv ist.

Mit anderen Worten, so eine Äquivalenzrelation fängt ein unsere Intuition über Gleichheit. Jedes Ding, also Gleichheit oder Ununterscheidbarkeit.

Jedes Ding ist gleich sich selbst, wenn ein Ding gleich einem anderen ist, dann auch umgekehrt und wenn zwei Dinge einem dritten gleich sind, dann auch untereinander.

So. Ja, das wie gesagt Erinnerung, der nächste Teil vermutlich neu.

Ein paar Konstruktionen auf Relationen, die nützlich sind.

Ja, einmal hier, nun das ist nicht so sehr eine Konstruktion auf Relation, sondern ist die Definition einer Standardrelation, nämlich der Gleichheitsrelation.