Fangen wir an mit einer Motivation.
Und die Motivation, die damals der Herr Wosch gewählt hatte, und die
eigentlich ganz interessant ist, ist die Geschichte der
Entschlüsselung der Hieroglyphen.
Die gelang damals nur mithilfe des Steins von Rosetta, einem
französischen Forscher und Linguisten.
Was war die Geschichte dahinter?
Die Geschichte dahinter war, man hatte in der Archäologie ganz viele
Hieroglyphen gefunden.
An Tempel geschrieben, auf Steinplatten gehauen, irgendwo hingemalt,
in Pyramiden etc.
Nur man konnte es nicht mehr entziffern.
Die Schrift selber war ausgestorben.
Die Kultur, die die Schrift verwendet hatte, war untergegangen.
Es wurden andere Schriften verwendet, andere Sprachen inzwischen
gesprochen etc., sodass man diese Hieroglyphen nicht mehr entziffern
konnte.
Man hat zwar gesehen, da sind anscheinend irgendwelche Zeichen, die
kommen aus einem Alphabet und diese Zeichen werden zusammengesetzt, um
damit Texte zu formen, aber man war absolut nicht in der Lage, das zu
entziffern.
Genauso erging es einem mit einer weiteren Schrift, dem Demotischen.
Auch mit dem Demotischen wurde das Altägyptisch geschrieben.
Auch diese Schrift konnte man nicht entziffern.
Altgriechisch, kein Problem, war etwas, was man kannte, was auch noch
sich in die Moderne gerettet hatte, was man jederzeit lesen konnte.
Und dann irgendwann hatte man Glück, dass man plötzlich eine
Steintafel gefunden hatte, die enthielt Text in drei verschiedenen
Schriften.
Die enthielt Text eben in Hieroglyphen, in Demotisch und in
Altgriechisch geschrieben.
Und dann fand man das ganz klasse und ist schon interessant.
Und dann kam irgendwer auf die Idee, naja, die Vermutung liegt nahe,
dass das vielleicht dreimal derselbe Text sein wird.
Und damit ist man dann sozusagen auf die zündende Idee gekommen, die
einem den Weg eröffnet hatte, die hieroglyphische Schrift dann auch zu
entziffern und umzusetzen.
Dass man zumindest die Worte und Zeichen, die auf dieser Steintafel
geschrieben waren, würde lesen können.
Viele haben sich versucht daran, das zu entziffern, indem man
Vergleiche gemacht hatte zwischen zum Beispiel der Form der
Schriftzeichen.
Man hat zum Beispiel versucht, die demotischen Schriftzeichen anhand
der Form vielleicht den Schriftzeichen im Altgriechischen zuzuordnen.
Das hatte nicht zum Erfolg geführt.
Prinzipiell ist sowas keine dumme Idee, weil viele moderne Alphabete,
die wir verwenden, haben sich sukzessive aus alten Schriften
entwickelt.
Aber in diesem Fall war es leider nicht erfolgreich.
Was letztendlich zum Erfolg geführt hatte, und das war die
Beobachtung, die auch der Herr Champollion gemacht hätte, das sieht
man leider hier nicht.
Da braucht man ein bisschen bessere Auflösung von dem hieroglyphischen
Text.
Im hieroglyphischen Text gab es Wortzeichenfolgen, Wörter, die in
einer Manentas-Kartusche drin waren.
Mit anderen Worten, da war so ein Kringel drum.
Und was entsprechend der Herr Champollion da richtig erraten hatte,
ist, dass diese Kartusche wohl dazu diente, um irgendwie etwas
Besonderes hervorzuheben, dass es ein besonderer Schmuck war.
Mit anderen Worten, so in einer Art Fett gedruckt oder in goldener
Schrift geschrieben.
Und dann war halt die Idee, das muss irgendwas Wichtiges sein.
Das ist der Name von Göttern oder wahrscheinlich Pharaonen.
Das müssen wichtige Namen sein.
Und dadurch, dass er das dann zugeordnet hat, den wichtigen Namen,
Pharaonen -Identitäten, die halt im Griechischen vorkamen, hatte er
einen ersten Fuß in der Tür gehabt, um dann hinterher diese Schrift zu
entschlüsseln.
Und was letztendlich er nichts anderes gemacht hat, das ist so eine
Art Kryptologie, Entschlüsselung von verschlüsselten Nachrichten.
Und das Gleiche konnte man mit dem Demotischen machen und dann hatte
man genügend Material, um auch ohne solchen parallelen Text die
Hieroglyphen und die demotische Schrift entziffern zu können, weil man
einfach ungemein viel Material schon hatte in der Sprache, halt keinen
Anker, um damit loszuwerden.
Auf dem Übungsblatt werden Sie auch ein kleines Beispiel,
Übungsaufgabe sehen, wie man heutzutage mit parallelen Texten umgeht,
nämlich im Bereich der maschinellen Übersetzung.
Was die maschinellen Übersetzungssysteme nämlich machen, sie lernen
Übersetzungen anhand solcher parallelen Texte.
Maschinelle Übersetzungssysteme, wenn ich von hieroglyphisch,
Altägyptisch, in Hieroglyphenschrift oder in demotischer Schrift nach
Altgriechisch übersetzen wollte, dann bräuchte ich ganz viele solcher
Rosettatafeln, ganz viele davon, und mache mir dann eben diese
parallelen Texte und lerne dann Statistiken, welche Zeichen, welche
Wörter, welchen anderen Wörtern zugeordnet werden, kann dann
Wahrscheinlichkeiten berechnen und für einen neuen Satz dann
entsprechend die wahrscheinlichste Übersetzung anhand dieser
Beobachtungen, die ich auf den Trainingsdaten gemacht habe,
hervorbringen.
Damit man das Ganze formell machen kann, im Rechner modellieren kann,
brauchen wir Mathematik.
Der Rechner ist eine mathematische Maschine.
Und was man bei Sprachen braucht, ist das Konzept der Mengen.
Das ist das Grundlegende, was den formalen Sprachen zugrunde liegt.
Kennt man auch schon aus der Schule, hat man auch schon Mengenlehre
genossen.
Einfaches Beispiel, man spricht von der Menge, die zum Beispiel die
Zahlen 1, 2 und 3 enthält.
Und nur die Zahlen 1, 2 und 3 und sonst nichts.
Das Erste, was man sich, wenn man eine Menge gegeben hat, in
irgendwelcher Form sich anschauen kann, wenn mir einer ein Objekt
zeigt, kann ich entscheiden, ist dieses Objekt in der Menge oder
nicht.
Völlig egal, warum und wieso und ob das denn so scharf immer möglich
ist, zu entscheiden, ob etwas in der Menge drin ist oder nicht.
Interessiert uns nicht, wir gehen davon aus, wenn uns einer ein Objekt
zeigt, können wir entscheiden, ist das in der Menge oder nicht.
Statt jetzt die Menge immer so ausführlich hinzuschreiben, gibt man
den Namen.
Man kann zum Beispiel eine Menge A nennen.
Und dann muss man nicht immer sagen, die Menge, die Zahlen 1 und 2 und
3 enthält und sonst nichts, sondern man definiert das einmal und wenn
man später von der Menge spricht, spricht man einfach von der Menge A.
Genauso wie Sie sich die Menge der natürlichen Zahlen, die Menge der
rationalen Zahlen, die Menge der reellen Zahlen definieren können und
hinterher einfach mit dem Namen oder auch dem Symbol, dem
doppelgestrichigen R, dem doppelstrichigen N oder dem verstärkten Z,
damit sprechen möchten.
Und dann kann man halt ganz schnell schreiben, in A ist 42 nicht
enthalten, wenn ich es halt vorher so definiert habe, dass nur 1, 2
und 3 entsprechend enthalten sind.
Auch das ist natürlich noch umständlich, das möchte man nun noch
besser mit der Notation machen.
Plus, man möchte nicht nur konkrete Ausgaben sprechen, sondern man
möchte auch allgemeingültige Aussagen, allgemeingültige Eigenschaften
über bestimmte Mengen definieren.
Zum Beispiel möchte ich sowas sagen wie, die Menge A enthält nur
Zahlen, die kleiner gleich 3 und größer gleich 1 sind.
Und dann ist es natürlich doof zu sagen, die Menge, das entweder als
Satz hinzuschreiben oder halt aufzuschreiben, die Menge enthält nicht
die Zahlen 3, 4, 5, 6 und so weiter und so fort.
Und deswegen fügt man Variablen ein, so wie Sie das auch im
Programmieren entweder schon kennen oder demnächst kennenlernen.
So wie Sie das in der Mathematik, in der Analysis, in der
Funktionenanalysis kennen werden.
Es gibt eine Variable und die Variable nennt man zum Beispiel x.
Und dann beschreibt man den Inhalt der Variable nicht konkret, sondern
abstrakt.
Man sagt, es sei x in A enthalten.
Und damit meine ich kein konkretes x, ich meine nicht das konkrete 1,
2 oder 3, ich meine irgendein beliebiges Objekt aus der Menge.
Und diese Aussagen kann man dann als wahr oder falsch einsehen, je
nachdem was ich in x einsetze.
Wenn ich in x 42 einsetze, ist das eine falsche Aussage.
Wenn ich in x 3 einsetze, ist das eine wahre Aussage.
Wenn ich sage, für alle x größer gleich 1 und kleiner gleich 42 sind
in der Menge enthalten, ist das eine falsche Aussage.
Die richtige Aussage wäre, alle x größer gleich 1, kleiner gleich 3
sind in der Menge enthalten.
Man nimmt also an dieser Stelle ein beliebiges Objekt her.
Und da muss man ein bisschen aufpassen, dass man hinterher auch, wenn
über etwas gesprochen wird, man sich immer darüber im Klaren ist,
sprechen wir über eine Variable oder sprechen wir über ein konkretes
Objekt.
Wenn ich ein konkretes Objekt machen will, dann kann ich zum Beispiel
sagen, sei jetzt x gleich 3.
Und dann alle anderen Aussagen, die ich treffe, wo x drin steht, da
nimmt man dann konkret an, dass x jetzt genau dem Objekt 3 entspricht.
Dann gibt es halt Notationen.
Wenn man halt sagen will, x ist in A enthalten, dann sagt man x
Element A, spricht man das aus, man hat dieses stilisierte E.
Und wenn man sagen will, dass x nicht in A ist, so wie man beim
Gleichheitszeichen, wenn man ungleich machen will, das durchstreicht,
streicht man halt dieses stilisierte E, das bedeutet Element von,
einfach durch.
Also es sei x ein Element der Menge A, kurz geschrieben es sei x
stilisiertes E A.
Für unsere Zwecke ist eine Menge immer bestimmt durch die sie
enthaltenen Objekte.
Wenn ich weiß, welche Objekte in einer Menge sind, ist diese Menge
eindeutig bestimmt.
Das bedeutet, dass zwei Mengen gleich sind.
Das Menge A gleich der Menge B ist, wenn daraus logischer Folge folgt,
wenn ich ein beliebiges x aus A hernehme, das Element A ist, dann muss
es auch Element B sein.
Und wenn ein beliebiges x Element B ist, dann muss es auch
notwendigerweise Element A sein.
Wenn das erfüllt ist, dann sind die beiden Mengen A und B gleich.
Dann kann man das Konzept der Teilmenge definieren.
Und der Obermenge.
Wir geben zwei beliebige Mengen A und B.
Wenn A eine Teilmenge von B ist, dann ist B eine Obermenge von A.
Man schreibt dann diesen speziellen Inklusionsinterparater als
Teilmenge von B.
Und das ist genau dann der Fall, wenn jedes x aus A auch ein Element x
aus B ist.
Aber es muss nicht notwendigerweise jedes x aus B auch ein x aus A
sein.
Das kann der Fall sein.
Aber wenn jedes Element von A auch Element von B ist, dann ist A
Teilmenge von B bzw.
B die Obermenge von A.
Und dann kann man den ersten kleinen Satz formulieren.
Dann kann man sagen, A ist gleich B, genau dann, wenn A Teilmenge von
B ist und B Teilmenge von A.
Mit der vorherigen Definition von Gleichheit von Mengen auf der
vorherigen Folie könnte man jetzt anfangen, diesen kleinen, einfachen,
trivialen Satz auch formell zu beweisen.
Wenn wir jetzt kleine Mengen aufschreiben wollen, die also
überschaubar viele Elemente haben, macht man das am einfachsten, indem
man einfach die Liste der Objekte, die in der Menge enthalten sind,
auflistet.
Und schreibt man meistens in geschweifte Klammern.
Geschweifte Klammern zeigen an, dass es sich hierbei jetzt um eine
Menge halten soll.
Und die Klassen der Menge sind durch Kommata gekrämt.
Das hat natürlich das Problem, was ist, wenn das Komma ein Teil der
Klasse sein soll.
Dann muss ich mir entweder einen anderen Trennoperator definieren oder
das Komma halt durch ein anderes Zeichen ersetzen.
Der Unterschied ist der gleiche Unterschied wie zwischen kleiner und
kleiner gleich.
So wie wir das hier definiert haben, kann es andere Mathebücher geben,
die das vielleicht anders definieren.
So wie wir Teilmenge definiert haben, kann auch sein, a gleich b und a
ist Teilmenge von b.
Dann notieren Sie das mit diesem Element.
Wenn a gleich b ist, können Sie nicht schreiben a Teilmenge von b ohne
das Gleichheitszeichen.
Man spricht dann manchmal auch von einer echten Teilmenge.
Das heißt, es muss mindestens ein Element in b geben, das nicht in a
enthalten ist.
Es gibt durchaus andere Mathematikbücher, die so Teilmengen
definieren.
Manchmal wird das dann angegeben mit diesem Wort echt, eine echte
Teilmenge.
So wie Sie sagen, 3 ist echt kleiner 4, aber 4 ist nur kleiner gleich
4.
Das ist der Unterschied.
Das ist etwas, das klingt jetzt hier in dem Fall trivial und einfach,
aber wenn Sie Literatur lesen, müssen Sie manchmal darauf achten, wie
diese Symbole oder auch diese Wörter Teilmenge definiert wurden.
Weil manche definieren es so, die anderen so.
Das Gleiche wie bei den natürlichen Zahlen.
Es gibt Leute, die definieren die natürlichen Zahlen so, dass 0
enthalten ist, und andere definieren die natürlichen Zahlen so, dass 0
nicht enthalten ist, und andere wiederum machen es dann explizit durch
Subskripte, so wie wir das hier machen, ob wir jetzt die natürlichen
Zahlen mit 0 oder ohne 0 meinen.
Also, zurück zu den kleinen Mengen.
Das Einfachste ist aufzählen, mit Kommata getrennt, in geschweiften
Klammern geschrieben.
Wenn jetzt das Komma Teil der Menge sein soll, muss man sich was
überlegen.
Insbesondere kann alles Teil einer Menge sein.
Also, da ist der Fantasie keiner gelaufen.
Sie können auch die Mengen mit den grünen, roten und blauen Vögeln
machen.
Sie müssen sich nur was überlegen, wie Sie das geeignet hinschreiben.
Deswegen, es müssen auch nicht die Objekte in einer Menge vom gleichen
Typ sein.
Sie können Zahlen und Vögel und Buchstaben und alles wild
durcheinander mischen.
Es gibt auch eine besondere Art der Menge, nämlich die Menge, die kein
Element enthält.
Die sogenannte leere Menge.
Und da gibt es auch zwei Möglichkeiten, das wieder zu notieren.
Die erste Möglichkeit, dass man einfach zwei geschweifte Klammern
nimmt und dazwischen ein Leerzeichen oder nichts.
Die andere Möglichkeit ist diese durchgestrichene Null.
Hier in den Folien wird meistens diese Notation genommen mit den zwei
geschweiften Klammern, wo nichts dazwischen ist.
Dann natürlich das Problem, was ist, wenn Sie die Menge hinschreiben
wollen, die das Leerzeichen enthält?
Dann muss man sich was überlegen, damit einem klar ist, dass man das
nicht mit der leeren Menge verwechselt.
Warum nimmt man die geschweiften Klammern hier und nicht häufig diese
durchgestrichene Null?
Wir sind Informatiker.
Wenn man auf alte Fondssätze guckt und alte typografische Schriften
und Niederschriften, damit man eine Null gut von einem O
unterschreiben kann, streicht man häufig die Null durch.
Dann weiß man, wenn man irgendwas gesetzt hat, dass das eine Null ist
und das andere ist ein O, wenn man Zahlen und Buchstaben durcheinander
wirft.
Gleichzeitig ist es die durchgestrichene Null, aber auch das Zeichen
für die leere Menge.
Da muss man sich auch immer darüber im Klaren sein, was ist mit den
Symbolen, die jetzt hier verwendet werden, wirklich gemeint?
Immer wieder überprüfen, ob das mit der eigenen Erwartung oder mit dem
eigenen Wissensstand übereinstimmt, von dem, was der Autor da gesagt
hat.
Sonst kommt es zu Missverständnissen.
Dann, ganz wichtig, die Elemente in einer Menge sind nicht geordnet.
Die haben keine Reihenfolge.
Es ist völlig egal, in welcher Reihenfolge Sie die Elemente angeben.
Das heißt, die Menge, in der steht 1, 2 und 3, ist die gleiche Menge,
wie die Menge, in der steht 3, 2 und 1.
Ergibt sich aus der Definition von Gleichheit.
Wir hatten gesagt, es ist gleich, wenn x Element a und x Element b und
3 ist Element der linken Menge, und 3 ist Element der rechten Menge.
Offensichtlich Gleichheit.
Auch das mehrfache Vorkommen von Objekten in einer Menge hat keinerlei
Auswirkungen.
Sie unterscheiden also nicht zwischen der ersten 1 oder der ersten 3,
die vorkommt, und der letzten 3, der vorkommt.
Auch diese Menge, diese 1, 1, 2, 3, 3, 2, 1, 3, 3, ist die gleiche
Menge wie die Menge 1, 2, 3.
Ergibt sich aus der Art und Weise, wie wir die Mengengleichheit halt
entsprechend definiert haben.
Das bedeutet insbesondere, Hinweis fürs Übungsblatt, wenn es plötzlich
auf die Reihenfolge bei irgendwas ankommt, dann reicht eine einfache
Menge nicht aus.
Dann müssen Sie sich einen Mechanismus überlegen, wenn Sie irgendwas
beschreiben wollen, und es kommt auf die Reihenfolge an, wie Sie auch
noch die Reihenfolge, die Position an das Objekt dran tun können.
Zu dem Mechanismus kommen wir noch nachher.
Große Mengen kann man natürlich nicht, insbesondere wenn es unendlich
große Mengen sind oder sehr, sehr große Mengen, kann man nicht durch
einfaches, konkretes Hinschreiben machen.
Die faule Art und Weise ist, das Ganze mit Pünktchen zu schreiben.
Also zum Beispiel die Menge der natürlichen Zahlen ohne 0 als n-plus
notiert ist gleich 1, 2, 3, 4, Pünktchen, Pünktchen, Pünktchen im
Sinne und immer so weiter.
Das Fiese ist dabei, man muss halt aufpassen, was bedeutet denn immer
so weiter, ist das klar?
In dem Fall hat man ja nur vier Beispiele.
Könnte ja auch die Menge sein, die heißt 1, 2, 3, 4, 6, 8, 10, 12, 14
und so weiter.
Man muss also aufpassen, dass dieses und so weiter also eindeutig klar
definiert ist, dass man den Rest der Menge wirklich daraus herleiten
kann.
Genauso die Menge der natürlichen Zahlen, die 0 enthält, n mit unter
Index 0, ist dann 0, 1, 2, 3, 4 und so weiter.
Und Pünktchen sind immer gefährlich.
Pünktchen, manchmal übersieht man irgendwas, dass es ein Muster gibt,
das auch da drin stecken kann und wahr ist und eine andere
Interpretation zulässt.
Hier mag das jetzt noch trivial sein und jeder vernünftig denkende
Mensch wird sofort sehen, was gemeint ist.
Was zum Beispiel fies ist, es gibt so einen Intelligenztest, der immer
die schöne Aufgabe, setzen Sie die Zahlenreihe fort.
Und dann sind das kompliziertere Zahlenreihen.
Und wenn Sie einen schönen Arithmetiker haben, jemand, der sich mit
Zahlentheorie betrifft, der kann Ihnen, wenn es eine halbwegs
hinreichend lange Menge ist, x-beliebige viele Vorschriften
hinschreiben, wie Sie genau diese Zahlen erreichen, sodass Sie im
Prinzip beliebig viele Möglichkeiten haben, um diese Zahlenreihe
fortzusetzen.
Das heißt, im Prinzip ist das ja bei dem Intelligenztest auch nichts
anderes.
Wir definieren eine Menge mit ein paar Beispielen und Pünktchen,
Pünktchen, Pünktchen und daraus soll folgen, wie es weitergeht.
Und dann versucht man halt abzuleiten, wenn jemand eine
Gesetzmäßigkeit heruntersitzt, dann ist er intelligent, und wenn
nicht, dann ist er halt weniger intelligent.
Wenn Sie aber richtiger Mathematiker sind, können Sie in vielen
Stellen dann denjenigen, der den Test entworfen hat, aufs Kreuz legen,
indem Sie ihm letztendlich zeigen können, dass es immer eine
Vorschrift gibt, dass Sie beliebig die Zahlreihe fortsetzen können,
wenn Sie nur ein oder zwei der nächsten Zahlen zeigen sollen.
Stattdessen wählt man lieber eine Notation oder Art und Weise, eine
Menge zu definieren, die nennt man Z-Comprehension.
Da gibt es keine schöne Aussage durch, keinen deutschen schönen
Begriff, der mir jetzt bekannt ist.
Man macht das mit Hilfe von Aussagen über beliebige Objekte der Menge
X.
Man sagt also, die Menge enthalte die Objekte X aus, meistens einer
Grundmenge, aus der sie sein kann, für die diese Aussage wahr ist.
Das heißt, ich brauche erstmal eine Grundmenge M, zum Beispiel die
natürlichen Zahlen, die Menge aller Vögel auf der Welt, die Menge
aller geometrischen Formen, und sage, aus dieser Grundmenge wähle ich
mir jetzt diejenigen Objekte X raus, für die meine Aussage P von X
erfüllt ist.
Und dann ist Y genau aus dieser Menge, wenn halt P von Y wahr ist.
Manchmal ist die Grundmenge auch klar, ergibt sich zum Beispiel aus
der Aufgabenstellung oder aus dem Ein-Bund-Meinen-Kontext, in dem man
jetzt über Mengen redet, dann kann man die Grundmenge auch weglassen
und dann sagt man einfach alle X für die, Bedeutung dieses senkrechten
Striches, alle X, für die P von X wahr ist.
Einfaches Beispiel, alle X aus der Menge der natürlichen Zahlen größer
gleich 1 und X soll ohne Rest durch 2 teilbar sein.
Nennen wir auch manchmal die geraden Zahlen.
Dann kann man Operatoren auf Mengen anwenden, so wie sie Zahlen
addieren können, multiplizieren können, dividieren können,
subtrahieren können, potenzieren können, können wir auch Sachen mit
Operationen mit Mengen machen.
Eine einfache Operation von Mengen ist die Vereinigung und eine andere
der Durchschnitt einer Menge.
Bei der Vereinigung einer Menge werfen sie salopp gesprochen die
Mengen zusammen.
Sie vereinigen die Objekte, die in den beiden Mengen sind, in eine
neue Menge.
Also das Ergebnis von A vereinigt B ist eine neue Menge und die Menge
enthält die Objekte X, wo entweder X aus A oder X aus B ist.
Also einfaches Beispiel hier, die Menge 1, 2, 3 und die Menge 3, 4, 5
vereinigt ist gleich der Menge 1, 2, 3, 4, 5.
Demgegenüber ist der Durchschnitt der Menge A geschnitten B.
So etwas, sie suchen die gemeinsamen enthaltenen Objekte aus den
beiden Mengen raus.
Das Ergebnis ist wieder eine neue Menge und die neue Menge enthält
alle Objekte X, wo X sowohl in A als auch in B ist, wo es in beiden
Mengen enthalten ist.
Was ist jetzt, wenn eine der beiden Mengen leer ist?
Die leere Menge enthält keine Elemente.
Das heißt, wenn ich irgendeine Menge habe, die nicht leer ist, dann
kann es in dieser nicht leeren Menge kein X geben, für das X Element
der leeren Menge ist.
Die leere Menge ist gerade so definiert, dass es eben kein X gibt, das
Element der leeren Menge ist.
Dementsprechend, wenn eine der beiden Mengen leer ist, dann ist der
Schnitt dieser beiden Mengen logischerweise auch immer die leere
Menge.
Es kann auch passieren, dass die Menge A und die Menge B keine
gemeinsamen Elemente enthalten.
Dann ist dementsprechend der Schnitt der beiden Mengen auch wieder die
leere Menge.
Und wir nennen diese beiden Mengen, wenn ich sie schneide und danach
leer sind, wenn der Schnitt der beiden Mengen leer ist, entsprechend
disjunkte Mengen.
So wie man für arithmetische Operationen Gesetze definieren kann, wie
Kommutativgesetz für die Addition oder das Distributivgesetz, kann man
auch Gesetze für den Schnitt und die Vereinigung bilden.
Das erste, was man sagen kann, nennt man die Idempotenz.
Wenn ich A mit sich selber schneide, A mit B schneide, kommt immer A
raus, Ergebnis.
Wenn ich A mit sich selber vereinige, kommt auch wieder A als Ergebnis
raus.
Dann gelten für Schnitt und Vereinigung das Kommutativgesetz.
Ob ich A mit B vereinige, hat das gleiche Ergebnis, als wenn ich B mit
A vereinige.
Und wenn ich A mit B schneide, ist es das gleiche, als ob ich B mit A
schneide.
Dann kann man auch sich überlegen, Assoziativgesetz.
Auch das Assoziativgesetz gilt für die Vereinigung und den Schnitt.
Also erst A mit B vereinigen und danach mit C vereinigen, ist das
gleiche, als wenn ich erst B mit C vereinige und dann mit A vereinige.
Oder halt für den Schnitt erst A und B schneiden und danach mit C
schneiden, ist das gleiche, als wenn ich erst B mit C schneide und
dann A schneide.
Damit Sie nicht glauben, dass jeder Operator, den wir hier kennen, so
etwas hat.
Es gibt auch Operatoren, für die diese Gesetze zum Beispiel nicht
gelten, insbesondere das Assoziativgesetz.
Das werden wir noch kennenlernen.
Dann gibt es auch das Distributivgesetz.
Und das funktioniert jetzt ein wenig anders, oder das funktioniert
recht ähnlich, wie wir das zu der Arithmetik mit Plus und Mal kennen.
Wenn ich A mit B vereinige und dann mit C schneide, dann ist es das
gleiche, als wenn ich erst A mit C schneide, B mit C schneide und dann
die Ergebnisse miteinander vereinige.
Und entsprechend umgekehrt, wenn ich jetzt erst A mit B schneide und
danach mit C vereinige, dann könnte ich auch alternativ erst A mit C
vereinigen und danach B mit C vereinigen.
Und logischerweise gilt, A ist immer eine Teilmenge von A vereinigt B
und A geschnitten B ist immer eine Teilmenge von A.
Und mit den Definitionen von Teilmenge und was es heißt, dass zwei
Mengen gleich sind und was es heißt, dass Objekte Teil sind einer
Menge, kann man das alles schön beweisen.
Wir tun das für die Inimpotenz, für die Vereinigung.
Also sei A eine Menge.
Hier, das ist ein triviales Beispiel, aber hier lernt man, wie man bei
Beweisen vorgehen muss.
Beweis besteht immer aus drei Schritten.
Erster Schritt, Voraussetzung.
Hier ist die Voraussetzung, es sei A eine Menge.
Das ist die einzige Voraussetzung, die wir haben.
Dann gibt es eine Behauptung, von der wir behaupten, dass sie wahr
ist.
Die Behauptung bedeutet, ist die Inimpotenz der Vereinigung.
Die Behauptung ist also, A ist gleich A vereinigt mit sich selber.
Und dann kommt der einzige Beweis.
Man muss also von der Voraussetzung ausgehend zeigen, dass die
Behauptung wahr ist.
Und dabei darf man durchaus auf Sachen zurückgreifen, die man vorher
schon bewiesen hat.
Man muss also nicht immer von einer ganz kleinen, ganz unten anfangen,
von der kleinsten Definition, sondern wenn man zwischendurch Sachen
bewiesen hat, die schon wahr sind, dann kann man davon ausgehen.
Und eine Sache, die wir zwar nicht bewiesen hatten, aber von der wir
trivialerweise behauptet haben, dass sie wahr ist.
Zwei Mengen sind dann gleich, wenn die eine Teilmenge der anderen ist
und die andere Teilmenge der ersten.
Angewandt auf uns heißt es, A ist gleich A vereinigt A, wenn A
Teilmenge von A vereinigt A ist.
Das heißt, jedes x-Element A ist auch ein Element von A vereinigt A.
Und zusätzlich muss gelten, A vereinigt A muss Teilmenge von A sein.
Das heißt, jedes x aus der Vereinigung A mit sich selbst ist auch ein
Element von A.
Das heißt, wir haben jetzt erstmal schon mal im Beweis eine sogenannte
Fallunterscheidung gemacht.
Wir haben jetzt, und das ist keine Fallunterscheidung, sondern
unterteilt in zwei Unterprobleme.
Es gibt zwei Unterprobleme, die wahr sein müssen, damit die zu
zeigende Behauptung wahr ist.
Das heißt, wir können jetzt separat erstens und zweitens beweisen und
haben damit dann die eigentliche ursprüngliche Behauptung bewiesen.
Also, kümmern wir uns als erstes um den Beweis von ersten.
Es sei x-Element A.
Das ist die Voraussetzung.
A ist eine Menge, x sei daraus.
Wenn dem so ist, dann ist auch, wollen wir zeigen, dass x auch aus A
vereinigt A ist.
Wenn wir das zeigen, haben wir erstens bewiesen.
Naja, also, wenn x aus A ist, dann ist x aus A oder x ist aus A.
Einfache Grundlagen der Logik.
Wenn das so ist, dann ist x auch aus A vereinigt A, weil das ist
gerade die Definition der Vereinigung.
Trivial, relativ leicht zu zeigen, aber hier formal mal
hingeschrieben, zu üben, was es heißt, wirklich formal etwas zu
beweisen.
Also, erstens haben wir abgehakt, müssen wir uns noch um zweitens
kümmern.
Wieder die Voraussetzung.
Es sei x aus A vereinigt A.
Die Voraussetzung.
Der linke Teil ist, was wir zu zeigen haben.
A vereinigt A, Teilmenge A.
Wir wollen hinkommen, dass x auch aus A ist.
Das ist der rechte Teil von zweitens.
Also A vereinigt A, heißt x ist aus A vereinigt A.
Dann ist x aus A oder x ist aus A.
Das ist die Definition der Vereinigung.
Und dann, einfache logische Schlussfolgerung, wenn x aus A ist oder x
aus A ist, dann ist logischerweise x aus A und das ist gerade die
Definition der Menge A, die wir haben.
Auf die Art und Weise haben wir relativ einfach erstens und zweitens
gezeigt und damit die Gesamtbehauptung.
Jetzt ist das Ganze trivial und dient jetzt nicht als intellektuelle
Herausforderung, sondern das ist einfach eine Fingerübung, damit man
hinterher kompliziertere Beweise auch gut, sauber, gut formuliert
hinschreiben kann und da nicht an Formfehlern scheitert oder sich
daran...
ich weiß, wie es geht, aber wie schreibe ich das denn jetzt hin?
Das ist so ein typisches Schema, wie man einen Beweis hinschreiben
kann.
Also, ich brauche immer Voraussetzung, Behauptung.
Dann ist es manchmal sinnvoll, das, was man zeigen möchte, zu zerlegen
in Unterprobleme.
Und wenn ich hier gezeigt habe, dass jedes Unterproblem wahr ist, dann
ist logischerweise auch das Hauptproblem wahr.
Und ich sollte zurückgreifen auf Sachen, von denen ich schon weiß,
dass die wahr sind, weil sie zum Beispiel in der Vorlesung bewiesen
wurden.
Was man häufig sieht bei solchen Sachen ist, wenn Mathematiker vor
sind oder auch Informatiker oder irgendjemand, der einen Beweis
hinschreibt, einfache Schlussfolgerung, wie man leicht sieht, wie sich
ergibt.
Als einfache Übung für zu Hause, ist etwas, was man Studenten häufig
sagt.
Werden Sie bei solchen Sachen immer hellhörig und gucken Sie noch ein
zweites Mal hin, ob es wirklich einfach zu sehen ist oder ob es
wirklich so einfach stimmt.
Es hat schon viele Beweise gegeben, die sich im Nachhinein als falsch
herausgestellt haben, weil da einer Ringen geschrieben hat, wie man
leicht ein leicht sieht.
Und dann hat sich herausgestellt, wenn man mal genau hingesehen hat,
war es dann doch anders.
Dann gibt es einen Operator der Mengendifferenz.
Seien A und B zwei Mengen.
Wir haben zwei Mengen.
Dann kann ich eine Art Minus-Operator, den Weg-Operator definieren.
Ich definiere mir A weg B als alle Objekte, die zwar in A sind, das
ist die Voraussetzung, nehmen wir alle Objekte aus A her und wähle nur
die aus, die nicht in B sind.
Das ist jetzt hier dieses Hinschreiben, wie wir es vorhin gelernt
haben.
Ich habe eine Grundmenge, die Grundmenge sei A, nehme mir alle x aus
dieser Grundmenge A raus und behalte nur diejenigen übrig, die nicht
in B sind.
Also einfaches Beispiel, wieder unsere Menge 1, 2, 3, weg 3, 4, 5,
bleiben die Elemente 1 und 2 übrig.
Dann kann ich mir einen Operator hernehmen, der mir die Größe einer
Menge misst.
Das nennt man dann die Kardinalität einer Menge.
Die Kardinalität ist die Anzahl ihrer Elemente und sei hier nur für
endliche Mengen definiert.
Man kann ein Konzept für Kardinalität auch machen für Mengen, die
unendlich groß sind.
Die kann man auch anhand ihrer Größe dann trotzdem noch irgendwie
anordnen.
Das ist aber nicht hier für uns relevant.
Das ist etwas, was wir bei den Mathematikern noch nehmen.
Die Kardinalität, die Größe einer Menge definieren wir immer mit so
senkrechten Strichen.
Und wichtig bei der Kardinalität, in der Regel betrachten wir die
Kardinalität einer Menge nur nachdem wir die Duplikate von Objekten
entfernt haben.
Also wenn ich diese Menge 1, 1, 1, 2, 2, 2, 3, 3, 3 habe, kann man
natürlich sagen, das sind mehr Elemente als nur 3.
Aber wenn man jetzt die Duplikate entfernt, kommt man dann bei der
Kardinalität 3 an.
Da muss man dann immer aufpassen, ob man vorher diese Duplikate
entfernt hat oder nicht, wenn man so Mengen explizit hingeschrieben
hat.
Für die Kardinalität gelten deswegen, weil man halt diese Duplikate
entfernt, nicht mehr so einfache Rechenregeln.
Also wenn eine Menge A3 groß ist und die andere Menge B5 groß ist,
dann ist die Vereinigung der Menge nicht notwendigerweise 8 Elemente
groß.
Sie kann 8 Elemente groß sein, sie kann aber auch kleiner sein.
Also hier das einfache Beispiel, die Menge 1, 2 und die Menge 2, 3
haben jeweils Kardinalität 2.
Wenn ich die Kardinalität zusammenzähle, komme ich zur Kardinalität 4.
Wenn ich die Mengen aber vereinige, erhalte ich nur die Menge 1, 2, 3
und die hat halt Kardinalität 3.
Da muss man aufpassen.
Grundsätzlich gilt für eine endliche Menge ist A eine nicht negative
ganze Zahl.
Also eine ganze Zahl größer gleich null.
Und wir reden bei Mengen nicht über ihre Kardinalität.
Das überlassen wir anderen in der höheren Mathematik.
Ist für uns nicht von Belang in dieser Vorlesung.
Das werden Sie in anderen Vorlesungen aber noch kennenlernen.
Gut.
Wenn wir jetzt Mengen haben, dann können wir uns jetzt vorarbeiten zu
etwas zu der Grundlage von formalen Sprachen.
Und das ist etwas, das nennen wir das Alphabet.
Ein Alphabet enthält Zeichen und mit diesen Zeichen werden wir dann
hinterher Wörter zusammensetzen.
Und wenn wir das haben, können wir Wörter wieder zu irgendwelchen
anderen Strukturen zusammensetzen, die wir entweder Sprachen nennen
oder wir können Wörter zu Nachrichten zusammensetzen.
Gut.
Wir kommen jetzt dazu, was ist ein Alphabet und was hat das mit der
ersten E-Mail zu tun, die in Deutschland eingetroffen ist.
Also, ein Alphabet ist eine nicht leere Menge von Zeichen oder
Symbolen.
Okay, da müssen wir ja erstmal definieren, was ein Zeichen oder ein
Symbol ist.
Das interessiert uns ja nicht.
Ein Zeichen ist das, was wir so intuitiv als Zeichen darstellen.
Das ist so, wie wir ein Signal abstrahieren können und darin Zeichen
sehen können, können wir auch ein Zeichen darsehen.
Das ist irgendwie ein elementärer Baustein, aus dem Inschriften, also
physikalisch gespeicherte Signale, aufgebaut sind.
Einfache Beispiele, das deutsche Alphabet oder einfach das Alphabet,
das nur einen senkrechten Strich enthält.
Das Alphabet, das aus Null und Eins zusammengesetzt ist, ein Alphabet,
das aus Zahlen und Buchstaben zusammengesetzt ist, können aber auch
ganz komplizierte Buchstaben sein, wie zum Beispiel so ein
Kopfstehendes Eins.
Sie haben schon die ersten Mathematikvorlesungen hinter sich.
Sie werden merken zum Beispiel, das griechische Alphabet wird auch
relativ wichtig sein.
Setzen Sie sich einfach mal in Ruhe hin und nehmen Sie sich eine Liste
der griechischen Buchstaben her, dass Sie auch die Zeichen kennen und
nicht hinterher, wenn Sie einer fragen, was steht denn da?
Ah, das ist irgendwas mit my, phu, nu, was weiß ich.
Es hilft ungemein.
Der Grund ist einfach, dass man viele solche Variablen und Platzhalter
und seltsame Sachen braucht, dass man halt mit dem reinen deutschen
Alphabet nicht auskommt, sondern auch dann aufs griechische Alphabet
zugreift.
Hat den Vorteil, wenn man es auf Deutsch oder auf Englisch schreibt
und plötzlich kommt ein griechischer Buchstabe, dann ist das so ein
Zeichen, oh, hier ist irgendwas anderes, hier ist irgendwie eine
Variable oder irgendwas Besonderes Mathematisches.
Ist unfair gegenüber den Griechen.
Ich hatte schon Griechen bei mir in der Prüfung, die hatten dann
Probleme damit, wenn man dann mit griechischen Buchstaben angekommen
ist, weil für die sind das nichts Besonderes, das ist halt für die ein
ganz normaler Buchstabe.
Der musste dann umdenken, dass das jetzt irgendwie was Besonderes ist.
So ein Zeichen kann aber auch abstrakter sein.
Und da kommt das Problem, ein Zeichen in einer formalen Sprache ist
nicht unbedingt das, was wir als Zeichen in unserer natürlichen
Umgangssprache sehen.
Ein Zeichen aus einer formalen Sprache kann zum Beispiel auch aus
Zeichen aufgebaut sein, wie wir sie in unserem deutschen Alphabet
haben.
Das heißt, hier unten, diese einfache Variablen-Deklaration in C oder
irgendeiner ähnlichen Programmiersprache, da betrachten wir als
formal, als Zeichen, alles, was in so einem blauen Kasten steht.
Das heißt, die Buchstabenfolge int besteht hier nicht aus drei
Zeichen, sondern die Buchstabenfolge int ist ein Zeichen.
Aus dieser formalen Sprache, aus dieser Programmiersprache.
Wenn man das so definiert, dann kann man gut Programmiersprachen
mithilfe von Alphabeten und formalen Sprachen beschreiben.
Ein ganz einfacher Zeichensatz ist der ASCII-Zeichensatz oder
moderner, der Unicode-Zeichensatz.
ASCII, American Standard Code for Information Interchange, war sehr,
sehr lange, aufgrund der Dominanz der USA in der Informatik und der
frühen Entwicklung von Computern, das Standardalphabet, mit dem man
Nachrichten übertragen hat.
Der besteht insgesamt aus 94 druckbaren und einigen unsichtbaren
Zeichen, insgesamt in 7-Bit-Codierbar.
Das heißt also, 2 hoch 7 Zeichen hatte man zur Verfügung.
Und die druckbaren Zeichen bestehen, wenn man sich die Buchstaben
anschaut, hauptsächlich eben aus den großen und kleinen Buchstaben des
lateinischen Alphabetes, so wie es für das Englische verwendet wird.
Solche Modifikationen, wie wir im Deutschen haben mit den Umlauten
oder dem ß, kommen darin nicht vor.
Theorische Buchstaben kommen darin nicht vor.
Irgendwelche Sachen mit Akzent, irgendwelche Ligaturen von einem O und
einem E zusammen, geschweige denn von solchen komplizierten Sachen wie
japanische Schriftzeichen oder auch die chinesischen Hansezeichen, all
sowas kommt in dem Alphabet nicht vor.
Das heißt, wenn man einen englischen Text damit übermitteln möchte,
ist das praktisch.
Wenn man einen kurillischen Text oder gar einen japanischen Text damit
übermitteln möchte, kommt man in Schwierigkeiten.
Das geht halt nicht.
Das trägt der Vielfalt an Alphabeten und Zeichen, die wir in der Welt
haben, leider nicht Rechnung.
Und deswegen ist man in einem langen und schmerzlichen Prozess bei
Unicode gelandet.
Unicode soll dazu dienen, als ein Zeichensatz, der mehr oder minder
alle Schriftzeichen, die es so auf der Welt gibt, versucht abzudecken.
Im Augenblick sowas wie ungefähr Größenordnung 100.000 Zeichen
definiert, es kommen regelmäßig noch neue Zeichen dazu.
Das sind auch solche komplizierten oder abstrakten Sachen wie
Länderflaggen, die halt abstrakt definiert sind, Emojis kommen da rein
und so weiter und so fort.
Also Unicode hat gegenüber ASCII den Vorteil, sehr, sehr großer
Zeichensatz, auch Zeichen, die nicht im englischen Alphabet vorkommen.
Zusätzlich gibt es außerdem noch andere Vorteile.
Jedes Zeichen wird auch durch einen Namen beschrieben.
Zum Beispiel kleines lateinisches C mit diesem Cedilla genannten
Diakritik, nennt man das, so eine kleine Modifikation unten drunter.
Es wird eine Sortierreihenfolge festgelegt von Buchstaben, die aber
sprachenabhängig ist.
In unterschiedlichen Sprachen wird das Alphabet, selbst wenn es sehr
ähnlich ist, teilweise unterschiedlich sortiert.
Jedem Großbuchstaben, wenn er denn einen kleinen Buchstaben hat, ist
diese Zuordnung auch explizit dargegeben.
Und es wird auch zum Beispiel so etwas festgelegt wie Schreibrichtung.
Nur weil man Englisch von links nach rechts schreibt, heißt das nicht,
dass andere Sprachen auch von links nach rechts geschrieben werden.
Hebräisch zum Beispiel von rechts nach links, Arabisch von rechts nach
links.
Andere Schriften kann man zum Beispiel von oben nach unten schreiben.
Hieroglyphen konnte man entweder von oben nach unten oder von links
nach rechts schreiben.
Diese Schreibrichtungen, Zeichen, die jetzt andeuten, welche aktuelle
Schreibrichtung für die nächsten Zeichen vorliegt, gibt es
dementsprechend auch im Unicode.
Und ganz, ganz, ganz viele mehrere andere Sachen.
Den ASCII-Zeichensatz kann man mehr oder weniger schön als Tabelle
hinschreiben, zumindest für die druckbaren Zeichen.
Jedes Zeichen hat eine Zahl.
Das ist die Tabelle der druckbaren Zeichen im ASCII-Kurzsatz.
Was Sie halt häufiger sehen, man will ja auch manchmal ein Leerzeichen
explizit darstellen.
Und da hatten wir ja schon das Problem, wenn ich jetzt die leere Menge
mit so geschweiften Klammern mache, wie unterscheide ich das denn von
der Menge, die das Leerzeichen enthält?
Gut, dann lässt man sich halt ein Zeichen einfallen, das halt explizit
sagen soll, hier, das hier ist ein Leerzeichen.
Da ist einfach nicht nur ein bisschen Platz, sondern da steht ein
echtes Leerzeichen.
Macht man mit diesem eckigen Eimer, dass man das macht.
Der ASCII-Zeichensatz ist nach wie vor an sehr, sehr vielen Stellen
von Bedeutung.
Deshalb sollte man den durchaus schon mal gesehen haben und sich damit
ein bisschen auskennen.
Und auch nicht gleich verwirrt werden, wenn man mal in Hexadezimal
oder in Binärdarstellung ASCII-Zeichen sieht, dass man die bauen kann.
Und wenn ich dann so ein Alphabet habe, dann kann ich anfangen, so
syntaktische Gebilde damit zu machen.
Und ein Beispiel für so ein syntaktisches Gebilde ist eben die E-Mail,
die es schon sehr, sehr lange gibt.
Also es ist nicht erst nur seitdem es das Internet mit TCP, IP gibt
und wie wir das alles kennen, sondern es gibt es viel, viel länger
schon.
Als es schon verknüpfte Rechner, die irgendwie über Netze miteinander
verknüpft sind, kamen halt auf die Idee, okay, es wäre sinnvoll, wenn
man Nachrichten, Briefe, elektronische Briefe hin und her schicken
könnte.
Das war die Erfindung dann der E-Mail.
Und die E-Mail ist spezifiziert in einem Dokument, das heißt RFC 5322.
Wer weiß, wofür RFC steht?
Genau, das RFC ist ein Request for Comments.
Und wenn man das jetzt übersetzt, heißt das nichts anderes.
Da hat jemand ein Dokument geschrieben und hätte jetzt gerne
Kommentare, will dazu Meinungen hören.
Und das ist halt etwas Besonderes in der Welt des Internets, dass man
da nicht wirklich mit ganz strikten, so wie man das kennt aus dem
Maschinenbau oder so, mit ganz strikten Normen arbeitet, dass man also
erst irgendwie einen Entwurf hat, dann kommt ein Gremium zusammen,
berät und modifiziert und dann wird noch dreimal beraten und
modifiziert und so weiter und so fort und dann wird irgendwann das
Dokument freigegeben, sondern hier heißen die Normen immer noch RFC,
Request for Comment.
Es gibt keinen, der so wirklich da immer die Hand drauf hat und sagt,
okay, jetzt ist es festgenagelt, so ist es gut, so ist es schlecht,
das nehmen wir.
Sondern das Ganze ist insbesondere am Anfang deutlich chaotischer
definiert gewesen.
Und solche Spezifikationen setzen sich qua Use durch.
Also etwas wird zum Standard, indem es zum de facto Standard wird,
indem es einfach genügend Leute gibt, die das verwenden und damit E
-Mails machen.
Und zur Folge, es gibt auch niemanden, der einem mit dem Knüppel
zwingt, dass man jetzt hier genau an den Standard hält.
Bestes Beispiel ist immer noch HTML.
Kennt vielleicht jeder, der schon mal Webseiten ein bisschen von Hand
noch gebaut hat.
Unterschiedliche Browser stellen die unterschiedlich dar und es gibt
und gab nach wie vor unterschiedliche Erweiterungen.
Der eine Browser kennt die Erweiterung und der andere Browser kennt
die Erweiterung.
Und beide Browser behaupten von sich her, sie stellen HTML dar.
Liegt einfach daran, dass es keinen gibt mit dem Knüppel, der sagt,
okay, du bist jetzt zertifiziert, du erfüllst den Standard
hundertprozentig.
Sondern es wird einfach, wenn einer Marktmarkt groß genug ist, der
Browser hat genügend große Verbreitung, dann baut man halt was dazu
und sagt den Leuten, okay, mein Browser kann jetzt auch das und dann
wird es plötzlich inoffiziell Teil von HTML oder was auch immer.
Gut, wie sieht das bei E-Mails aus?
Bei E-Mails gibt es einmal eine Spezifikation, dass eine E-Mail einen
Header haben soll.
Einen Kopf mit Verwaltungsinformation.
Da steht zum Beispiel drin, von wem es kommt und an wen es gehen soll.
Und dann gibt es die eigentliche Nachricht, den E-Mail-Rumpf, den E
-Mail -Body mit der eigentlichen Nachricht.
Und jetzt kommt das Interessante.
Warum ist das interessant?
Nach wie vor bei der reinen, puren E-Mail sind in diesem Body nach wie
vor immer nur ASCII-Zeichen erlaubt.
Ganz, ganz, ganz, ganz wirklich.
Also ernsthaft.
Jetzt werden Sie sagen, wieso?
Ich habe heute Morgen eine E-Mail geschrieben und da waren Umlaute
drin.
Oder sonst was für Inhalte.
Ich kann Hanse-Zeichen in eine E-Mail verschicken.
Ja, können Sie, aber nicht wegen der ursprünglichen E-Mail-Definition.
Die ursprüngliche E-Mail-Definition hat das nicht erlaubt.
Deswegen, wenn man sowas hat wie Umlaute oder irgendwie sowas, braucht
man irgendwelche Erweiterungen.
Wie das funktioniert, kommen wir zu einem Kapitel über Kodierung.
Da gibt es zum Beispiel eine Möglichkeit, wie man ASCII dazu verwenden
und umbiegen kann, dass man auch Umlaute darstellen kann.
Plus es gibt die sogenannten MIME-Verwaltungen.
Das sind so Multi-Purposes, Internet-Mail-Extensions.
Das ist wiederum Standards, mehrere Standards, auch wieder in RFCs
niedergehalten, die es einem erlauben, dann nicht nur ASCII-Text zu
schicken, sondern Inhalte so in ASCII-Text zu kodieren, dass ich halt
auch beryllischen Text verschicken kann, dass ich Bilder verschicken
kann, dass ich Audiodateien verschicken kann, dass ich irgendwelche
anderen Sachen verschicken kann.
Schluss.
Es gibt dann irgendwann eine RFC, die sich von dem ASCII löst, dass
man halt auch irgendwelche Multimedia-komplexen Inhalte nicht
notwendigerweise immer in ASCII kodieren muss.
Unicode selber funktioniert mithilfe solcher Codepoints.
Es gibt ein Alphabet, nennen wir es a-u, u wie Unicode.
Und dieses Alphabet enthalte alle Zeichen, die in dem Unicode-Alphabet
enthalten sind, die in Unicode enthalten sind.
Jedes dieser Zeichen in diesem Alphabet hat einen Codepoint.
Das ist nichts anderes als eine nicht-negative ganze Zahl, das ist
eine Nummer.
Die sind durchnummeriert.
Nicht für jeden möglichen Codepoint von 1 bis zum höchsten Codepoint,
dem ein Unicode-Zeichen zugeordnet ist, nicht jedem Codepoint, der
dazwischen liegt, ist auch ein Alphabet-Zeichen zugeordnet.
Da sind Lücken im Unicode.
Da sind Lücken, weil man halt sich gedacht hat, okay, bei ASCII haben
sie gedacht, da kann man alles mitmachen, und Hustekuchen war nicht
so.
Jetzt machen wir Unicode und wollen alles damit machen.
Wir behaupten aber nicht, dass man jetzt schon weiß, was Unicode alles
können muss.
Das heißt, man hat freien Platz, um halt regelmäßig neue Zeichen mit
hinzunehmen zu können, wenn man halt eine neue Sprache sieht oder
irgendein Phänomen entdeckt, das man nicht bedacht hatte bei der
Konstruktion von Unicode.
Deswegen sind da sehr viele Lücken sogar dran.
Zwischen so einem Unicode-Zeichen aus dem Alphabet aller Unicode
-Zeichen und den natürlichen Zahlen größer gleich null, für nicht
-negative, also null ist auch ein Codepoint, besteht eine Beziehung.
Und diese Beziehung nennt man jetzt in der Mathematik eine Relation.
Also jedes Zeichen A steht in irgendeiner Beziehung zu einer
natürlichen Zahl aus N0.
Umgekehrt, nicht jede natürliche Zahl aus N0 steht zu einer Beziehung
zu einem Unicodepoint.
Es gibt Lücken, irgendwo ist Ende, es gibt irgendwelche Zahlen, die
größer sind als alle möglichen Alphabete, die im Unicode enthalten
sind.
Aber im Unicode-Zeichen A besteht eine Verbindung zu nicht-negativen
ganzen Zahlen, eine Relation.
Und um eine Relation definieren zu können, brauchen wir jetzt das
Konzept des Paares.
Wir nehmen uns wieder her zwei Mengen, wir bauen alles auf Mengenlehre
auf.
Es gibt eine Menge A und es gibt eine Menge B.
Und jetzt nehmen wir uns ein Objekt klein a aus der Menge A und wir
nehmen uns ein Objekt klein b aus der Menge B und wir schreiben die
zusammen, wir koppeln die aneinander.
Aber nicht im Sinne, dass wir daraus ein Wort machen, sondern wir
bauen daraus ein Paar.
Das heißt, ich weiß, welches das Objekt A ist und welches das Objekt B
ist und schreibe die dann so in runde Klammern mit einem Komma
dazwischen und habe damit ein sogenanntes Tupel, ein Paar gebildet.
Besteht aus zwei voneinander identifizierbaren Komponenten.
Die verschmelzen nicht so, dass ich sie nicht voneinander
unterscheiden kann.
Ich weiß immer noch, was kam aus der ersten Menge, was kam aus der
zweiten Menge.
Die beiden Komponenten dürfen gleich sein.
Also A darf auch gleich B sein und ich darf Paare bilden, wo die erste
Komponente dasselbe Objekt ist wie die zweite Komponente.
Auch das ist ein Paar.
Und zwei Paare als Objekt gesehen sind genau dann gleich, wenn das
erste Element aus dem ersten Paar das gleiche ist wie das erste
Element aus dem zweiten Paar und wenn das zweite Element aus dem
ersten Paar mit dem zweiten Element aus dem zweiten Paar
übereinstimmt.
Das heißt also insbesondere, hier kommt es auf die Reihenfolge an.
Da ist jetzt anders als bei Mengen.
Wenn ich Mengen gleich einmache, kommt es nicht auf die Reihenfolge
der Elemente in der Menge an.
Hier kommt es auf die Reihenfolge im Paar an.
Das heißt, das Paar 1 und 2 ist nicht gleich dem Paar 2 und 1, sondern
die Objekte, die gleich sind, müssen auch an derselben Position
stehen.
Und wenn ich Paare habe, dann kann ich einen weiteren Operator
einführen bei Mengen.
Das sogenannte kathesische Produkt.
Und bei dem kathesischen Produkt definiere ich mir eine Menge, die
alle möglichen Paare enthält, die ich aus den Elementen der Menge a
und der Menge b zusammenbauen kann.
Also hier formal hingeschrieben, a Kreuz b ist gleich die Menge mit
den Paaren a, b, für die gilt a ist Element a und b ist Element b.
Das kann ich jetzt erweitern auf mehrere Mengen.
Ich kann also auch das kathesische Produkt aus drei Mengen machen.
Und wie kann ich das machen?
Naja, ich kann es erstmal als so eine Art Teleskopkette aufbauen,
mithilfe des binären kathesischen Produktes.
Ich kann also, wenn ich das kathesische Produkt dreier Mengen bilden
möchte, erstmal das kathesische Produkt aus m1 und das kathesische
Produkt aus m2 bilden.
Und das Ergebnis nehme ich her und baue mir dann damit das kathesische
Produkt aus m3.
Und dann bekomme ich solche Paare der folgenden Form, dass das erste
Element des Paares ist wieder ein Paar und das dritte Element ist
jetzt ein Objekt.
Also das erste Element des resultierenden Paares ist aus dem
kathesischen Produkt m1, m2, das die dritte Komponente ist aus der
Menge.
Und jetzt kommt das Schöne, diese Klammern können wir weglassen.
Machen haben keine Bedeutung mehr.
Wir können aus diesem Tupel, dessen erstes Element wieder ein Tupel
ist, einen Triple machen und können stattdessen einfach sagen, das
kathesische Produkt von m1 mit m2 mit m3 sind alle Triple, die halt
bestehen aus Elementen x1, x2, x3, sodass x aus Element der Menge m1
ist, x2 aus Element der Menge m2 und x3 aus Element der Menge m3.
Gut, kann ich für drei machen, kann ich für beliebig viele machen.
Angenommen, ich habe n Mengen, m sei eine natürliche Zahl, dann kann
ich das kathesische Produkt m1, m2 bis mn machen.
Schon wieder Pünktchen.
Wir hatten gesagt, Pünktchen sind blöd, Pünktchen sind verleiten zu
Missverständnissen, Pünktchen verleiten dazu, dass ich irgendwas
übersehe, irgendeine Feinheit, die nicht sofort offensichtlich war.
Schöner wäre es, wenn wir das Ganze ohne Pünktchen machen könnten.
Wie können wir das Ganze ohne Pünktchen machen?
Da kommen wir jetzt zu einem Konzept, das auch sehr wichtig ist bei
der Definition von Mengen.
Das ist dieses induktive Konzept.
Wir definieren jetzt induktive Definitionen von etwas.
Damit ich jetzt ohne Pünktchen das kathesische Produkt von n Mengen
definieren kann, und n sei dabei beliebig, das soll funktionieren für
drei Mengen, das soll funktionieren für fünf Mengen, das soll
funktionieren für eine Trillion dreitausendzweiundvierzig Mengen,
brauche ich als erstes eine Hilfsmenge.
Das ist so eine Art Indexmenge.
Ich definiere mir nicht nur eine Menge, ich definiere mir ganz, ganz
viele Mengen.
Und allgemein nenne ich diese Mengen p, n.
Und diese Mengen p, n, die Menge p, n, enthalten alle natürlichen
Zahlen größer gleich eins, die kleiner gleich dem Subscript, dem Index
n sind, der an dieser Menge p, n dasteht.
Das heißt, auf diese Art und Weise habe ich mir unendlich viele Mengen
definiert.
Ich kann in n reinsetzen, was ich möchte, solange es n eine Zahl
größer gleich eins ist, kann ich p1, p2, p3, p4, p5 und so weiter habe
ich damit definiert.
Und jetzt benutze ich das, um ein kathesisches Produkt von kleinen
Mengen zu definieren.
Und ich definiere mir das so.
Sei also n eine natürliche Zahl größer gleich eins und p, n
dementsprechend dieser Art Indexmenge, die ich mir definiert habe.
Und sei für jedes i aus dieser Indexmenge p, n eine Menge m, i
vorhanden.
Es gibt n Mengen, m1 bis m, n.
Die möchte ich mithilfe des kathesischen Produktes verarbeiten.
Dann definiere ich mir jetzt dieses kathesische Produkt über diese
Mengen m1 bis m so her, dass ich sage, gucken wir uns erstmal den Fall
1 an.
Also angenommen, i sei 1.
Dann sei das kathesische Produkt über die Menge m1, sei eben gerade
die Menge m1.
Und wenn ich jetzt ein beliebiges n hernehme, dann sage ich das
kathesische Produkt für den Fall i aus p, n plus 1 über die m, i.
Das sei eben gerade das kathesische Produkt über die i aus den p, n
und davon das kathesische Produkt definiert mit m, n plus 1.
Und jetzt ist die Frage, habe ich auf die Art und Weise wirklich ein
kathesisches Produkt für beliebiges n definiert?
Rechnen kann man damit relativ einfach.
Also wenn ich m1 habe, kathesisches Produkt für i gleich 1 ist m1.
Und für jedes beliebige n, das ich habe, kann ich was einsetzen.
Also wenn ich für p2 habe, dann habe ich halt das i aus p1, mi,
kathesisches Produkt mal m2.
Naja, i Element p1 und darüber das kathesische Produkt über die mi ist
ja gerade definiert als die Menge m1.
Dann vereinfacht sich das zu m1 kathesisches Produkt 2.
Wenn das i3 wäre, dann brauche ich halt einmal dieses kathesische
Produkt über i aus p2, mi, mal mit kathesischem Produkt m3.
Das ist gerade die Definition.
Jetzt habe ich Glück, kathesisches Produkt über i Element p2, mi, habe
ich ja gerade eine Zeile darüber ausgerechnet, kann ich also
einsetzen.
Und so kann ich mich immer weiter vortangeln.
Wenn ich das für p4 mache, dann sehe ich, in der Definition brauche
ich das für p3, habe ich die Zeile vorher ausgerechnet, kann ich
einsetzen und komme dann damit zu einem kathesischen Produkt für m1
bis m4.
Und dieses Zurückfallen, dass ich etwas definiere, basierend auf
etwas, das irgendwie eine Instanz kleiner ist, das nennt man die
induktive Definition, induktiv vorzugeben.
Man muss sich erstmal explizit einen Anfangsfall definieren.
Ich brauche irgendwas Konkretes, von dem ich loslaufen kann.
Das ist in unserem Fall für n gleich 1, habe ich mir definiert, dieses
kathesische Produkt aus i Element p1, mi soll gerade m1 sein.
Und dann definiere ich mir, wie ich einen Schritt weitergehe.
Ich definiere das für den Fall n plus 1.
Und damit habe ich etwas für alle m definiert.
Warum ist das so?
Sagt uns die Mathematik.
Angenommen, wenn ich irgendeine Menge m habe, und die enthält nur
positive ganze Zahlen, und es gilt, 1 ist Teilmenge von m, und für
jedes n aus den natürlichen Zahlen gilt, wenn n aus m, dann ist auch n
plus 1 aus m.
Und wenn das der Fall ist, dann ist m gleich die Menge der natürlichen
Zahlen.
Das ist zum Beispiel die induktive Definition der natürlichen Zahlen n
plus.
Und auf diese Art und Weise kann man halt zeigen, dass man dann
wirklich auch etwas für alle natürlichen Zahlen definiert hat, weil
das ist die Definition der natürlichen Zahlen.
Wenn ich also sowas mache, dann habe ich etwas für alle natürlichen
Zahlen definiert, und oben das Vorgehen war ja gerade so analog
hierzu.
Ich habe etwas für 1 definiert, und danach habe ich etwas für m plus 1
definiert.
Und wenn das dazu führt, dass die natürlichen Zahlen auf die Art und
Weise aufgebaut werden, dann ist logischerweise auch die Definition
drüber, die auf diese Art und Weise aufgebaut ist, auch über diese
Indexmenge der natürlichen Zahlen definiert.
Frage ich die Frage, was ist das kritisische Produkt einer Menge mit
sich selbst?
Sei also m eine Menge und sei n eine natürliche Zahl größer gleich 1,
dann tun wir so analog, wie bei einer Potenzierung das ist.
Wir schreiben dann das kathesische Produkt mit i Element pn über die
Menge mit sich selber, also jedes m1 gleich m2 gleich m3 gleich und so
weiter mn, als m hoch n.
Wir bauen also n lange Elemente auf, die sämtliche Kombinationen aus
den Elementen aus m mit sich selber enthalten.
Die Menge pn ist jetzt benutzt, Sie müssen das nicht jedes Mal
definieren.
Sie können also jetzt jederzeit schreiben, das ist gerade auf die Art
und Weise haben wir definiert, wenn man kathesisches Produkt m1,
kathesisches Produkt m2, kreuz m3, kreuz m4 und so weiter, können Sie
einfach das Kreuz schreiben, brauchen Sie jetzt diese Indexmenge nicht
mehr.
Okay, also wenn ich also ein kathesisches Produkt mehrmals einer Menge
mit sich selber bringe, ist das so ähnlich wie Potenzieren bei den
Zahlen, wir nennen das m hoch n.
Man darf sich da nicht verwirren lassen, das ist so ähnlich wie beim
Potenzieren, das heißt aber nicht notwendigerweise, dass das immer die
gleichen Eigenschaften haben muss.
Dieser Weckstrich zum Beispiel hat man so vom Gefühl her, könnte ja
eine Art Minus sein, von der Schreibweise her ist es so etwas
Ähnliches wie Bruchbildung, aber hat nicht notwendigerweise die
gleichen Eigenschaften wie zum Beispiel die Subtraktion oder die
Division bei natürlichen Zahlen.
Und auch beim kathesischen Produkt darf man jetzt nur, wenn man es m
hoch n anschreibt, nicht die gleichen Gesetze anwenden, die man bei
reellen Zahlen oder bei ganzen Zahlen anwenden dürfte.
Man darf nur die Gesetze anwenden, die wir auch wirklich bewiesen
haben.
Von allen anderen Gesetzen wissen wir nicht, ob sie überhaupt stimmen.
Und es gibt durchaus Gesetze, die dann nicht stimmen.
Mithilfe dieser Paare, des Konzepts von Paaren und mit dem Konzept von
kathesischen Produkten, können wir jetzt formell diese Relation von
Unicode -Zeichen und ihren Code-Points entsprechend definieren.
Wir geben einfach alle Paare an.
Auf der linken Position steht halt ein a aus dieser Menge a Unicode, a
Element au, und rechts steht halt die Zahl n, sein Code-Point.
Und wir nehmen jetzt alle die Möglichkeiten a und n her, wo wirklich a
Element au ist, und n der zugehörige Code-Point.
Und auf die Art und Weise haben wir dann das Unicode-Alphabet
definiert.
Das heißt halt zum Beispiel konkret, das große a, wie Sie schon in der
ersten Vorlesung viele gewusst haben und gesehen haben, entspricht zum
Beispiel dem ASCII-Zeichen 65.
Das sz im Deutschen hat den Code-Punkt 223, ein griechisches kleines
Alpha 945.
Das Symbol für die natürlichen Zahlen ist irgendwo bei 8400.
Dieser Operator für alle hat dann ein Code-Zeichen, der Operator für
das kathesische Produkt hat ein Code-Zeichen und so weiter und so
fort.
Wenn man diese alle in einer Menge u zusammenführt, u sei jetzt
Unicode, dann gilt die Beziehung, dass das Teilmenge ist des
kathesischen Produkts von au mit den natürlichen Zahlen.
Es ist nur eine Teilmenge, weil es Lücken gibt im Unicode.
Es gibt also durchaus auch Kombinationen, natürliche Zahlen, wo eine
Lücke ist, wo keine Definition ist und insbesondere ist auch jedem
Unicode -Zeichen a nur ein einziger Code-Punkt zugeordnet.
Das kathesische Produkt ordnet jedem Unicode-Zeichen aus dem Alphabet
au jeden möglichen Code-Punkt zu.
Das würde ja keinen Sinn ergeben.
Ich brauche ja gerade diese Eindeutigkeit der Relation, dass jedem
Unicode -Zeichen nur ein Code-Punkt zugeordnet ist.
Das heißt, ich habe hier etwas, das ist eine Teilmenge dieses
kathesischen Produktes und eine Teilmenge aus einem kathesischen
Produkt, das nennt man dann eine Relation R.
Eine Relation R ist immer eine Teilmenge eines kathesischen Produktes.
In diesem Fall ist es genau genommen eine binäre Relation.
A steht in Bezug zu B, wenn ich A mit B ein kathesisches Produkt
bilde.
Also zum Beispiel A und 65 ist Teil, Element dieser Relation Unicode,
die durch die Unicode-Relation definiert wird.
Das Paar B und 4711 ist eben kein Element dieser Relation.
Welches B mit welcher Zahl wäre ein Element der Relation Unicode?
Das kann man ja mal raten.
B66.
B66 wäre dadurch wiederum ein Element aus Unicode, weil halt das B
direkt auf das A folgt bei den Code-Points.
Abbildungen sind definiert als eine spezielle Form der Relation.
Wenn so Relationen bestimmte Eigenschaften aufweisen, dann sind sie
eine Abbildung.
Und an der Unicode-Relation kann man diese Eigenschaften schön
aufzeigen, weil sie diese schönen Eigenschaften besitzt.
Links haben wir eine Menge A dargestellt mit drei Elementen.
Das sind so Punkte.
Wie die jetzt genau heißen, ist egal.
Das sind Platzhalter für drei Elemente.
Rechts ist eine Menge B.
Die hat auch drei Elemente.
Die Pfeile sollen die Relation anzeigen, sollen also zeigen, welcher
Punkt aus A mit welchem Punkt aus B ein Paar formt.
Wenn also für jedes Element aus der Menge A es auch ein N gibt, sodass
dieses A mit dem N aus der Menge B in Beziehung gibt, wenn also jedes
Element A in der linken Position eines Paares aus der Relation
vorkommt, dann nennen wir diese Relation linkstotal.
Kann man schreiben als für jedes A-Element B gibt es ein B-Element B,
mit dem A, B Element dieser Relation ist.
Das heißt, das, was da mit dem roten Kreuzchen angedeutet ist, das
darf nicht vorkommen.
Das ist keine linkstotale Abbildung, dass dieser linke Punkt in A, der
da mit dem Kreuz durchgestrichen ist, der muss auch auf irgendwas
abgebildet werden.
Da muss man noch irgendein Pfeil nach B reinzeichnen, damit das Ganze
linkstotal ist.
Es macht keine Aussagen darüber, dass nur ein anderes Element
abgebildet werden kann.
Der erste Punkt zum Beispiel, der wird auf zwei Punkte in B
abgebildet, ist für Linkstotalität komplett zulässig.
Alles in Ordnung.
Es geht nur darum, dass wirklich für jedes A mindestens eine dieser
Abbildungen, mindestens ein Pfeil vorhanden ist.
Dann kann man sich darum gucken, was ist, wenn man so mehrere Pfeile
hat?
Was ist, wenn man das nicht will?
Was ist, wenn man will, dass jedem Element aus A maximal ein Element
aus B zugeordnet ist?
Wenn das der Fall ist, dann heißt die Relation rechts eindeutig.
Wenn ich das linke Element des Paares kenne, dann ist das rechte
Element des Paares eindeutig bestimmt.
Folgt eindeutig aus A.
Das ist dann rechts eindeutig.
Also das mit den zwei Pfeilen, was beim Linkstotal durchaus vorkommen
darf, dass ein Element auf zwei Elemente abgebildet wird, darf bei
rechts eindeutig vorkommen.
Nur weil etwas rechts eindeutig ist, ist das aber noch lange nicht
Linkstotal.
Das heißt, jetzt ist es vollkommen zulässig, dass es in A da ein
Element gibt, das auf kein Element in B abgebildet wird.
Es ist auch vollständig in Ordnung, dass es in B ein Element gibt, das
mit keinem Element aus der Menge A in Relation steht.
Das ist auch vollständig in Ordnung.
Wenn ich jetzt eine Abbildung habe, die sowohl Linkstotal ist als auch
rechts eindeutig, dann nenne ich diese Relation eine Abbildung.
Also die Definition einer Abbildung ist, eine Abbildung ist eine
Relation, die linkstotal und rechts eindeutig ist.
Und das kommt halt so häufig vor und braucht man halt so häufig, dass
man halt eine eigene Schreibweise hat.
Man definiert dann diese Abbildung R, Doppelpunkt, bildet ab von der
Menge A in die Menge B.
Und links ein kleines Bildchen, das halt eine zulässige Abbildung ist.
Jedes Element aus A wird den Elementen B zugeordnet.
Und wenn ich A habe, wenn ich das linke Element A kenne, dann weiß ich
automatisch, welches das rechte Element B ist.
Also ein linkes Element aus A ist nicht mehreren Elementen aus B
zugeordnet.
Aber es ist durchaus zulässig bei einer Abbildung, dass ein Element
aus B mit mehreren Elementen aus A in Verbindung steht.
Und es ist bei einer Abbildung auch zulässig, dass es Elemente in B
gibt, die nicht irgendwie in Relation zu einem Element aus A stehen.
A nennt man bei einer Abbildung dann entsprechend den
Definitionsbereich und B nennt man den Zielbereich.
Und jetzt kommen wir zu der Schreibweise.
Das kennen Sie alle aus der Schule.
Wenn Sie Funktionen schreiben, schreiben Sie das genauso.
Eine Funktion ist nämlich auch eine spezielle Form der Abbildung.
Man sagt dann, wenn A und B miteinander in Relation stehen gemäß
dieser Abbildung, dann gilt R von A gleich B.
B heißt dann der Funktionswert an der Stelle A.
Gelegentlich wird es in der Mathematik auch passieren, dass Sie mit
Funktionen oder mit Abbildungen arbeiten, für die nicht jedes Element
aus A in einer Relation vorkommt.
Das nennt man dann partielle Funktionen.
Das kommt vielleicht ganz am Ende der Vorlesung vor.