So, nehmen Sie Platz.
Schönen guten Tag.
Und dann lassen Sie uns mal anfangen mit der dritten Vorlesung
Grundbegriffe der Informatik.
Wir hatten angefangen jetzt mit dem dritten Kapitel mit so ersten
kleinen Schritten Richtung konkreter Dinge, konkrete Definitionen, zum
Beispiel eine Relation ist eine Teilmenge, also jetzt eine binäre
Relation des kathesischen Produkts von zwei Mengen A und B.
Sie erinnern sich, A kreuz B ist die Menge aller Paare.
Erste Komponente aus A, zweite Komponente aus B und eine Teilmenge,
wenn man nur manche von den Paaren nimmt, dann hat man halt eine
Relation im Allgemeinen.
Und wenn Sie jetzt insbesondere für jedes Element aus A, jedes Element
klein A aus A genau ein Element klein B aus groß B haben, dann nennt
man so eine Relation auch eine Abbildung.
Und zum Beispiel bei Unicode haben Sie eine Abbildung jedem Symbol
eindeutig zuordnet.
Eine Nummer, diesen sogenannten Code Point und diese Abbildung ist
sogar injektiv.
Verschiedene Symbole haben verschiedene Code Points.
Also Relation, Abbildung, das haben wir irgendwie und dafür braucht
man irgendwie Mengen.
Und wo geht es jetzt weiter?
Wir sind, glaube ich, bis hierhin gekommen.
Und jetzt zum Abschluss die letzten drei, vier Folien nochmal.
So ein bisschen zusätzliche Notationen, die dann auch auf dem
Übungsblatt auftauchen.
Zu der dann auch in der großen Übung gleich noch was gesagt wird.
Ich habe Ihnen ja letzte Woche gesagt, also in Zukunft dann immer erst
das Viertel große Übung und danach drei Viertel des Blocks Vorlesung.
Heute machen wir es noch umgekehrt, weil jetzt am Anfang mit den
Tutorien und alles so ein bisschen anders.
Aber dann demnächst läuft das immer so, wie ich es behauptet habe.
Gut, also erstens wundern Sie sich nicht, dass also zum Beispiel die
Elemente einer Menge irgendwie auch etwas Kompliziereres als einfach
nur Zahlen oder so sein dürfen.
Das können auch selber zum Beispiel wieder Mengen sein.
Also diese Menge hier, die erste, die hier oben hingeschrieben ist,
enthält sieben Elemente, ein Element ist die Eins, ein Element ist die
Menge, ein Element ist die Menge, die zwei und drei enthält, ein
Element ist die vier, die fünf, die sechs, ein Element ist diese
Menge, die drei Zahlen sieben macht, neun enthält und die leere Menge,
die da als letztes steht, ist auch noch ein Element dieser Menge.
Und bitte auch die Menge, die die leere Menge als Element enthält,
enthält ein Element und ist selbst nicht leer.
Innen drin, das ist die leere Menge, aber die Menge, wo das drin ist,
die Menge ist nicht mehr leer.
Also Analogien sind gefährlich, aber in dieser Tüte ist eine leere
Tüte drin und deswegen ist die äußere Tüte nicht mehr leer.
Also passen Sie immer ein bisschen auf.
Dann ist es manchmal bequem, eine Notation zu haben, wenn man zwei
Mengen A und B hat und man will reden über die Menge aller Abbildungen
mit Definitionsbereich A und Zielbereich, Zielmenge B.
Dafür schreiben wir B hoch A.
Also B hoch A ist die Menge aller Funktionen F von A nach B.
Und warum schreibt man da B hoch A in dieser etwas, vielleicht im
ersten Moment überraschenden Anordnung?
Das kommt vielleicht, ich weiß es nicht, daher, dass das Folgende
gilt, wenn A und B endliche Mengen sind, dann die Anzahl der
Abbildungen von A nach B, also die Größe, die Kardinalität der Menge B
hoch A, das ist gerade die Kardinalität von B, wie viele Elemente gibt
es im Zielbereich hoch, die Kardinalität von A, wie viele Elemente
gibt es im Definitionsbereich.
Und das steht ja auch als Hinweis, glaube ich, bei einer Aufgabe auf
dem ersten Aufgabenblatt.
Also das ist die Anzahl der Abbildungen in unserem Sinne, totale
Abbildungen, links total und rechts eindeutig.
Und dann gibt es ja diese eine Aufgabe auf dem Aufgabenblatt, wo man
angeben soll, wie viele partielle Abbildungen irgendetwas gibt es.
Und da steht das hier für die totalen Abbildungen nochmal als Hinweis.
Und eine Frage, die tauchte das letzte Mal nach der Vorlesung gleich
wieder auf.
Und gestern, als ich mich mit den Tutoren besprochen habe, tauchte die
Frage auch gleich wieder auf.
Es gibt halt öfter mal die Situation, dass sie da sitzen und sich dann
fragen, wie soll ich das denn beweisen.
Da gibt es so ein paar elementare Vorgehensweisen, die man immer mal
angucken kann.
Und wenn Sie die Aufgabe haben, irgendwie die Anzahl partieller
Abbildungen zu zählen mit irgendwelchen Eigenschaften, und es wird
Ihnen als Tipp gegeben, das ist die Anzahl der totalen Abbildungen,
dann versuchen Sie halt mit einer großen Keule den allgemeinen Fall
partielle Abbildungen zurückzuprügeln auf den Fall totale Abbildungen.
Also ab und zu muss man halt auch mal eine Idee haben.
Aber einen komplizierteren Fall zurückführen auf einen einfacheren
Fall oder auf etwas anderes, was man schon kann, das kommt halt öfter
mal vor.
Und das andere, ich weiß nicht, manche von Ihnen haben vielleicht
schon mal versucht, aus vielen kleinen Teilchen so puzzelmäßig ein
großes Bild zusammenzusetzen.
Wenn Sie da vor dem großen Haufen kleiner Bildteilchen stehen oder
sitzen, dann raufen Sie sich ja auch nicht die Haare und wühlen da
planlos drin herum und fragen sich, was soll ich jetzt tun, sondern
also tendenziell, glaube ich, ist eine übliche Vorgehensweise, man
sucht sich erst mal die Teilchen, die am Rand von dem Bild liegen
sollen, weil man die leicht erkennt, weil der Rand gerade
abgeschnitten ist.
Und dann hat man ja schon mal viel weniger Teilchen und kann sich
vielleicht erst mal den Rahmen legen und dann hat man schon was, an
das kann man sich dran aufhängen und dann wird es leichter.
Und dann weiß man vielleicht, was am Ende als Bild rauskommen soll und
wenn man dann sieht, in der Ecke oben links ist irgendwie viel Rot,
dann sucht man vielleicht erst mal Teilchen mit viel Rot und versucht,
die da oben links in der Ecke hinzukriegen.
Und bei Beweisen ist es ja auch so, also suchen Sie sich erst mal
einen Rahmen, was sind die Voraussetzungen, was soll am Ende
rauskommen und dann fragen Sie sich, naja, haben Sie ja auch so ein
bisschen so eine Idee, so einen Plan, von wo nach wo, wie könnte man
sich da langhangeln, wenn da irgendwelche komplizierten Zeichen oder
Begriffe vorkommen, was ist denn die Definition von den Dingern,
schreiben Sie sich die mal hin und dann so nach und nach füllt sich
das Blatt mit sinnvollen Dingen meistens.
Gut, also B hoch A, die Menge aller Abbildungen von A nach B.
Was anderes, was oft vorkommt, oder ja oft, was man ab und zu brauchen
kann, ist das folgende, Sie haben gegeben eine Menge, Groß M
meinetwegen, und Sie wollen jetzt irgendwie reden über alle Teilmengen
von Groß M.
Und Sie wollen gerne einen Namen haben für die Menge aller Teilmengen
von Groß M.
Und diese Menge aller Teilmengen, die heißt Potenzmenge von M, und da
gibt es zwei mehr oder weniger gängige Schreibweisen, wir benutzen
zwei Hoch M, andere schreiben so irgendwie Fraktur P oder so, das ist
ein großes P von M.
Also zwei Hoch M, die Potenzmenge von M per Definition sind alle
Teilmengen A von M.
Also meinetwegen, wenn M nur ein Element, meinetwegen die Zahl 1,
enthält, dann die Potenzmenge dieser Menge, die nur die 1 enthält, das
sind also alle Teilmengen dieser Menge, die nur die 1 enthält.
Eine Teilmenge haben Sie immer, das ist die leere Menge.
Das ist hier das, was als erstes hingeschrieben ist.
Die zweite Teilmenge, die Sie immer haben, ist einfach ganz banal
alles, ganz M, ist hier auch hingeschrieben.
Und wenn Sie nur ein Element in der Menge haben, so Teilmengen mit
einer Größe irgendwo dazwischen, gibt es halt gar nicht.
Also die Potenzmenge dieser Menge, die nur die 1 enthält, enthält zwei
Elemente, die leere Menge und die ganze Menge.
Und wenn Sie eine Menge 1, 2, 3 haben, dann die Potenzmenge enthält
natürlich mehr, also wieder die leere Menge natürlich und die ganze
Menge 1, 2, 3, aber jetzt eben auch die Teilmengen, die nur ein
Element, eins oder zwei oder drei enthalten, oder die zwei von den
drei Elementen enthalten.
Und einfach per Definition, eine Menge ist in 2 hoch M in der
Potenzmenge von M genau dann, wenn A Teilmenge von M ist.
Dann kann man sich jetzt auch wieder fragen, wo kommt denn diese
Schreibweise 2 hoch M her?
Naja, das eine ist, dass Sie vielleicht mal zählen, wie viele Elemente
hier in diesen Beispielen in der Potenzmenge drin sind.
Und das andere ist, dass Sie sich mal fragen können, also stellen Sie
sich mal fast vor, die 2, die steht hier nur so symbolisch für eine
Menge mit zwei Elementen, nämlich für die Menge, die 0 und 1 enthält.
Und tatsächlich, wenn man natürliche Zahlen einführt in der
Mathematik, dann kann man das zum Beispiel so machen, dass die 2 per
Definition einfach die Menge ist, die 0 und 1 enthält.
Darum kümmern wir uns hier aber nicht.
Also versuchen Sie sich mal den Zusammenhang zwischen Potenzmenge von
M und 0,1 hoch M herzustellen.
0,1 hoch M, das hatten wir gerade auf der Folie vorher, das ist die
Menge aller Abbildungen von M in die Menge 0,1.
Malen Sie sich Bildchen, also die Menschen sind verschieden, ich liebe
Bildchen.
Malen Sie sich Bildchen für diese Dinge und dann merken Sie vielleicht
was.
Gut.
Und das dritte, was man manchmal brauchen kann, ist so eine
Verallgemeinerung von Vereinigungen von zwei Mengen.
Also für zwei Mengen haben wir einfach gesagt, in der Vereinigung sind
alle Elemente mit der Eigenschaft, das Element ist in der einen Menge
oder das Element ist in der anderen Menge.
Oder beides.
Jetzt, wenn man mehr Mengen hat, womöglich unendlich viele, dann will
man also ungern wieder Pünktchen, Pünktchen, Pünktchen in irgendwas
hinschreiben und Hände wedeln.
Das darf nur ich in der Vorlesung.
Also stellen Sie sich vor, wir haben Mengen M, I für jedes I aus
irgendeiner Menge von Indizes.
Also stellen Sie sich vor, groß I ist so eine Menge, die enthält
vielleicht die Zahlen nur 1 und 2 oder vielleicht alle nicht-negativen
ganzen Zahlen, was auch immer.
Und für jedes klein I aus dieser Indexmenge groß I haben wir so eine
Menge groß M Index I.
Und dann definiert man hier so zwei Schreibweisen, die eine mit einem
zu groß geratenen Vereinigungszeichen und die andere mit einem ganz
groß geratenen Durchschnittszeichen und schreibt dahinter M I und
unter das Zeichen klein I Element groß I und im Falle des großen
Vereinigungszeichens soll das eine Menge sein, die folgende Elemente
enthält.
Alle Elemente X mit der Eigenschaft also es gibt ein klein I und mit
anderen Worten dann also eine Menge M Index I und Klammer auf
mindestens eine, es dürfen auch mehrere sein, wo dieses Element drin
ist.
Also die Elemente, die in mindestens einer Menge M I drin sind, die
sind auch in dieser großen Vereinigung und der große Durchschnitt ist
so definiert, da sind nur die Elemente drin mit der Eigenschaft die
sind in jeder Menge M I, also für jedes I aus groß I muss X Element
von M I sein, nur dann ist X in dem großen Durchschnitt.
Und wenn Sie sich das ausschreiben und irgendwie eine Zeile umformen,
dann sehen Sie, wenn Sie nur Indexmenge 1,2 haben, die große
Vereinigung der M I ist einfach die normale Vereinigung M 1 vereinigt
M 2 und der große Durchschnitt ist einfach M 1 geschnitten M 2.
Und hier drin versteckt, wenn also I unendlich ist, groß I, diese
Indexmenge unendlich ist, hier drin ist irgendwie versteckt Pünktchen
für irgendetwas.
Vereinigt, vereinigt, vereinigt, Pünktchen, Pünktchen, Pünktchen.
Und dann ist das weg und das ist eine präzise Definition, was hier
steht für große Vereinigung der M I, großer Durchschnitt.
Das kommt im nächsten Kapitel auch gleich vor.
Und das war es.
Das ist noch der Rest von diesem Kapitel gewesen.
Also der Punkt ist, wir wissen jetzt, was eine Relation ist, wir
wissen, was Abbildungen sind, injektiv, surreaktiv.
Sie haben schon mal irgendwie das Unicode-Alphabet gesehen, in
Anführungszeichen, also nicht wirklich, das sind 100.000 Zeichen.
Aber gut.
Und Sie können so ein bisschen rumrantieren mit diesen Gebilden, auch
auf den Aufgaben.
Sie sollen halt so ein bisschen rechnen, arbeiten mit diesen
Begriffen.
Und wir haben angefangen, so einfache Argumentationen, Beweise
durchzuführen, wie A ist Teilmenge von A vereinigt A, was wir das
letzte Mal hatten.
Und daran müssen Sie sich gewöhnen, dass man in der Informatik nicht
nur irgendwelche Dinge tut, sondern sich auch Gedanken darüber macht,
warum das sinnvoll ist.
Warum ein Programm genau das tut, was man gerne möchte, dass es tun
soll.
Nicht nur einfach was tun, sondern auch verstehen, warum es
funktioniert.
Gut.
So viel noch kurz zu Mengen.
Und dann kommen wir jetzt zu Wörtern.
Sie alle wissen, was man so im Deutschen oder Englischen als ein Wort
bezeichnet.
Das ist halt so eine Folge von Zeichen, einfach hintereinander
geschrieben.
Und um sowas soll es jetzt gehen.
Einfach mehrere Symbole hintereinander.
Und jetzt machen wir also irgendwie ein bisschen was mit Wörtern.
Und dann im übernächsten Kapitel werden Sie sehen, machen wir das dann
noch ein bisschen allgemeiner und betrachten dann Mengen von Wörtern.
Nochmal völlig losgelöst von was bedeuten diese Wörter vielleicht.
Einfach Mengen von Wörtern, das nennt man dann formale Sprachen.
Aber eben formal, weil es nicht um umgangssprachliche und inhaltliche
Dinge geht, sondern einfach ein Haufen Wörter.
So.
Der Fahrplan für dieses Kapitel ist ungefähr der.
Also Ausgangspunkt, jeder hat ein Verständnis davon, was ist ein Wort
im Deutschen, Englischen, was auch immer.
Einfach eine Folge von Zeichen.
Trotzdem werden wir irgendwie eine formale Definition hinschreiben für
was ist ein Wort.
Jetzt nicht, um es besonders umständlich zu machen oder besonders oft
Formeln hinschreiben zu können, sondern um was zu üben.
Und weil Sie alle schon wissen, was ein Wort ist, ist dann der Rest,
also wenn es ums Üben geht von irgendwelchen Dingen, für Sie leichter
nachvollziehbar, weil Sie immer wissen, dass Sie sich vorstellen
können, ach so, das sind ja einfach nur Wörter, ich weiß ja, was hier
passiert.
Und man kann sich dann auf das konzentrieren, was neu ist und muss
nicht erst noch versuchen, im Kopf ein Gebilde zu konstruieren, ein
Gefühl dafür zu kriegen, was soll denn hier eigentlich definiert
worden sein, mit dem wir jetzt hier rumhantieren.
Im Laufe der Zeit, im Laufe der Semester werden Sie dann merken, hier
und da öfter mal, da geht es dann genau anders rum, da kommt auf
einmal eine Definition an, geflogen auf der Folie und man denkt
erstmal, was ist jetzt das genau und man kann noch nichts so richtig
damit verbinden.
Und dann muss man erst damit arbeiten und in Gedanken im Kopf sich
eine Vorstellung verschaffen, was ist denn so jetzt eine gute
Sichtweise für diese Dinge, mit denen da jetzt rumhantiert wird.
Das können wir uns hier sparen.
Jeder weiß, was ein Wort ist.
Gut.
Und dann definieren wir die Konkatenation von Wörtern.
Das ist auch ganz einfach.
Man nimmt einfach zwei Wörter und schreibt sie hintereinander.
Man nimmt das Wort Apfel, schreibt das Wort Mus dahinter, hat man
Apfelmus.
Der zweite Grund, weshalb ich das hier so formal mache, ist
tatsächlich, dass eine Konkatenation von Wörtern völlig banal, das hat
jeder gerade sofort geschluckt.
Klar, zwei Wörter hintereinander schreiben, gibt ein längeres Wort.
Aber tatsächlich gibt es da eine Stelle, also ich habe mich damals im
ersten Semester irgendwie ein kleines bisschen unwohl gefühlt und
irgendwas war da nicht so, wie ich mir das so vorgestellt habe.
Und vielleicht hilft ja diese formale Definition, also mir hätte sie
geholfen, da irgendwas ein bisschen besser zu verstehen.
So.
Und dass das alles irgendwie nützlich ist, naja, schauen wir mal kurz
auf den Aufbau von E-Mails.
Nicht, dass das klausurrelevant wäre.
Also ich werde Sie nicht in der Klausur fragen, wie viele Zeichen
dürfen maximal in einer Zeile einer E-Mail stehen.
Interessiert keine.
Klammer auf, es sind übrigens 998 Zeichen, Klammer zu.
Sowas müssen Sie nicht wissen.
Aber einfach als Beispiel, dass Sie sehen, dass man irgendwie
sinnvolle Dinge aussagen kann.
So.
Ja, und dann kommt so ein bisschen noch verallgemeinerte Dinge am Ende
des Kapitels und insbesondere schon mal, was ist eine formale Sprache.
Gut.
Also, Wörter.
Naja, wie gesagt, ein Wort ist einfach eine Folge von Zeichen.
Vorausgesetzt, es ist irgendwie klar, wir haben hier ein Alphabet,
groß A, und ein Alphabet ist einfach eine Menge von Zeichen, ja, also
kleines A bis kleines Z und großes A bis großes Z oder was auch immer,
ja, eine endliche Menge von Zeichen und wir setzen darauf, dass wir
alle das richtige Verständnis von Alphabet und Zeichen haben.
Gut.
Also, Apfelmus ist ein Wort.
Das schreibt man dann so nebeneinander hin.
Vorausgesetzt, das Alphabet enthält jetzt, sagen wir mal, alle
Buchstaben, die es im Deutschen so gibt.
Es ist auch nicht verboten, dass ein Symbol mehrfach vorkommen darf,
ja, das ist durchaus legal.
Die müssen nicht alle paarweise verschiedene sein.
So was sind Wörter.
Gut.
Jetzt definieren wir das mal genau.
Ach so, und bevor wir das tun, noch kleiner Hinweis.
Nicht, dass es wichtig wäre, darauf werde ich jetzt auch in der
Vorlesung nicht groß rumreiten, das stößt Ihnen vielleicht irgendwann
nochmal kurz in der Vorlesung über Compilerbau auf oder wenn Sie mal
selber Programme schreiben müssen, die überhaupt irgendwie Texte
verarbeiten.
Das, was man so Leerzeichen nennt, was so im allgemeinen Text, also
zum Beispiel in der Überschrift dieser Folie, da haben ja manche Paare
von Buchstaben einen größeren Abstand als andere, deutlich größer.
Da ist so eine Art Leerzeichen, nennen wir das mal.
Wir tun mal so im Zweifelsfall, als wäre das auch einfach ein Zeichen.
Übrigens, diese Leerzeichen, das macht man heutzutage, dass man das
irgendwie einstreut.
Vor, ich weiß nicht, ein paar hundert Jahren hat man das, also auch
deutschen, mitteldeutschen, was weiß ich für einen Text, ohne
Leerzeichen einfach hintereinander weggeschrieben.
Und es gibt auch heutzutage, also wenn Sie einen Text auf Japanisch
angucken oder so, da werden Sie nicht viele Leerzeichen finden.
Das ist jetzt auch nichts, was global schon immer und überall gilt.
Also im Zweifelsfall, dieser größere Abstand zwischen zwei Buchstaben
ist im Zweifelsfall auch einfach nur ein Zeichen, wie andere auch.
Und wenn man darüber reden will und klar machen will, hier meine ich
jetzt ein Leerzeichen, dann malt man mal doch was hin, was nicht das
Leerzeichen ist, damit man es deutlich sieht.
Dann merken Sie, dass man da irgendwie so zwei Ebenen hat.
Und im Zweifelsfall wäre also Hallo Leerzeichen-Welte wäre für uns ein
Wort aus zehn Zeichen.
Aber ist nicht wichtig.
Was das mit der Überreihe soll, habe ich Ihnen gerade schon gesagt,
warum wir da jetzt formal definieren, was es heißt, da stehen mehrere
Symbole nebeneinander.
Was ist denn das Wesentliche?
Naja, man hat eine Reihenfolge.
Und das Natürlichste, wo man eine Reihenfolge hat, sind Zahlen.
Das heißt, man könnte, wenn man ein Wort hat, auch sagen, hier habe
ich die Symbole und die sind irgendwie durchnummeriert.
Was steht an erster Stelle, an zweiter Stelle, an dritter Stelle?
Und dann muss man irgendwo mit dem Durchnummerieren anfangen und dann
steht man vor der schweren Aufgabe, fängt man bei 1 an oder fängt man
bei 0 an.
Und ich habe an vielen Stellen hier in der Vorlesung dann gesagt, ich
fange bei 0 an, weil das zum Beispiel in Java, also für Indizierung
von Arrays oder so, werden Sie sehen oder haben Sie vielleicht schon
gesehen, man fängt halt bei 0 an.
Das ist halt so in vielen Programmiersprachen oder jedenfalls in
manchen.
Es gibt auch welche, da geht es bei 1 los, es gibt auch welche, da
können Sie das einstellen, ob Sie ab 0 oder ab 1 durchnummeriert haben
wollen.
Wir nehmen das hier jetzt mal ab 0.
Also so ein bisschen deutlicher, das Wort Milchreis, das sind also
diese neuen Buchstaben und die haben eine Reihenfolge, die sind
durchnummeriert von 0 bis 8.
Und also für jedes Wort brauchen wir dann die Zahlen von 0 bis
Anzahlsymbole in dem Wort, minus 1.
Und dafür führen wir gleich noch eine Abkürzung ein.
Ich schreibe so ein großes Z mit so einem Doppelstrich und Index n und
n der Index ist so eine nicht negative ganze Zahl, also so 0, 1, 2, 3
und dieser Index n gibt an, wie viele Zahlen in der Menge Zn drin sind
und es sind die Zahlen i aus N0, die größer gleich 0 sind, na klar,
und echt kleiner n.
Also in Z4 sind die Zahlen, die natürlichen Zahlen, die echt größer
gleich...
die größer gleich 0 sind und echt kleiner 4, also 0, 1, 2 und 3.
Diese 4 Zahlen sind in Z4.
Und in Z1 sind die Zahlen größer gleich 0 und echt kleiner 1.
Das ist nur die 0.
Und in Z0 sind die nicht negativen ganzen Zahlen, die größer gleich 0
sind und echt kleiner 0.
Das gibt es nicht.
Also Z0 ist die leere Menge.
Werden wir gleich noch benutzen.
So, und dann steht hier jetzt irgendwie formal die Definition von was
ist ein Wort über einem Alphabet A?
Also das Alphabet muss vorher irgendwie festgelegt sein oder
vielleicht ist es auch einfach mal klar.
Also formal ein Wort, wollen wir sagen, über einem Alphabet A ist eine
surreaktive Abbildung, nennen wir sie mal klein w, von einer dieser
Mengen Zn, also von Menge der Indizes 0 bis n-1 auf surreaktiv auf
eine Teilmenge B des ganzen Alphabets.
Surreaktive Abbildung heißt, jedes Element in der Menge B ist auch
tatsächlich funktionswert.
Also in B sind nur die Symbole drin, die wirklich vorkommen in dem
Wort.
Und um die anderen kümmert man sich nicht.
Überflüssig?
Ja, Punkt.
Und Abbildung, also für jede Zahl von 0 bis n-1 ist genau festgelegt,
welches Symbol steht anstelle i.
Das ist ein Wort.
Und dieses n hier, das ist ja wie gesagt auch die Anzahl der Elemente
in Zn, also zumindest in diesen Beispielen und das glaubt man dann
auch, wenn man sich so ein bisschen anguckt, das beweisen wir nicht.
Das nennen wir auch die Länge des Wortes.
Und wenn es sich erstmal nur Wörter vorstellen, die mindestens Länge 1
haben, also aus einem Symbol bestehen oder aus 2 oder aus 3 oder 4,
ist recht.
Gut.
Und dann wäre also das, was man einfach als Hallo hinschreiben würde,
formal eine Abbildung, hier stehen 5 Symbole, also eine Abbildung von
Z5 auf die Menge aller Symbole, die hier irgendwo vorkommen in dem
Wort, also A, H, L und O.
Und dann muss man eben noch die Funktionswerte festlegen, also sprich
anstelle 0 steht ein H, anstelle 1 ein A, anstelle 2 ein L, anstelle 3
noch ein L und anstelle 4 ein O.
Ja, das ist Hallo.
Und so können Sie das natürlich für alle Wörter machen.
Und wie man sieht, dieser Formalismus ist viel aufwendiger als einfach
Hallo hinzuschreiben.
Also das lohnt sich nur, wenn man noch irgendwas Erleuchtendes damit
tun kann, sonst lässt man es einfach.
Gut.
Ja.
Und wir werden gleich was Sinnvolles damit tun.
Ja, und dann weiß man also, was ein Wort ist und dann möchte man
manchmal reden über die Menge aller Wörter, die man aus den Symbolen,
die in irgendeinem Alphabet sind, bilden kann.
Und wenn A ein Alphabet ist, dann schreiben wir A mit einem Sternchen
oben dran für die Menge aller Wörter, die nur Zeichen enthalten, die
in dem Alphabet A vorkommen.
Aber nicht unbedingt alle.
Also einfach, das ist, A-Stern ist sozusagen die Menge aller
subjektiven Abbildungen, wie es hier unten steht, von irgendeinem ZN
auf eine Teilmenge B von A.
Die Menge aller Wörter.
Und wenn meinetwegen das Alphabet nur klein a und klein b enthält,
welche Wörter können Sie dann hinschreiben?
Naja, kurze und längere Wörter.
Kurze Wörter wären erstmal z.B.
die mit Länge 1, also ein einzelnes A hin.
Da können Sie dann auch sagen, ja, das ist ein Wort, das hat Länge 1.
Und was weiß ich, wenn Sie im Englischen gucken, dann finden Sie das
Wort sogar im Wörterbuch.
Aber das ist sozusagen Zufall.
Und das andere Wort der Länge 1, wir halten einzelnes B.
Und dann können Sie die Wörter hinschreiben der Länge 2.
A, A, A, B, B, A und B, B.
Und bitte, A, B und B, A sind verschiedene Wörter.
Also erstmal anschaulich und auch formal.
Also wenn Sie das als Abbildungen ansehen, bei dem einen Funktionswert
an der Stelle 0 ist klein a, beim anderen Funktionswert an der Stelle
0 ist klein b.
Für das gleiche Argument, verschiedene Funktionswerte, das sind
verschiedene Abbildungen, das sind verschiedene Wörter.
Das ist konsistent.
Naja, und dann Wörter der Länge 3, der Länge 4, der Länge 5 und so
weiter.
Und was in A-Stern auch mit dabei ist, kommen wir gleich noch genauer
dazu, ist das sogenannte Leerewort.
Das hat Länge 0.
Das besteht aus 0 Symbolen.
Unabhängig davon, also Wörter der Länge 1, 2, 3, 4.
Also offensichtlich, man hat ja mindestens ein Symbol in so einem
Alphabet.
Man kann unendlich viele Wörter hinschreiben.
Ja, mindestens eins der Länge 1, mindestens eins der Länge 2,
mindestens eins der Länge 3.
Immer das gleiche Symbol, N mal hintereinander.
Also es gibt dann immer unendlich viele Wörter in A-Stern.
Aber bitte Vorsicht, jedes einzelne Wort ist endlich lang.
Sie können die Länge aber halt nicht beschränken.
Gut.
Ja, das Leerewort.
Naja, da gewöhnt man sich dran.
So wie Sie sich auch an die 0 gewöhnt haben.
Wenn man irgendwann anfängt, als Kind zu zählen, da gibt es natürlich
erst mal nur einen Apfel, zwei Äpfel, drei Äpfel und noch nicht Null
Äpfel.
Aber irgendwann naja, kommt die Null halt auch noch dazu.
Und wie Sie gemerkt haben im Laufe Ihres Lebens, Null ist ganz
nützlich.
Und genauso macht man das bei den Wörtern.
Da gibt es dann eben auch noch das Leerewort.
Das besteht aus Nullsymbolen.
Das hat die Länge 0.
Da stehen Nullsymbole, was es leider sehr schwierig macht, das
Leerewort zu sehen.
Deswegen wieder für uns eine Ebene höher, damit wir es nicht
übersehen.
Man schreibt etwas anderes hin und vereinbart, also wenn wir das
hinschreiben, wir meinen immer das Leerewort.
So, und jetzt gibt es leider auf der Welt zwei Hälften.
Die eine Hälfte schreibt für das Leerewort ein kleines griechisches
Epsilon, wie wir auch.
Die andere Hälfte schreibt Lambda, ein kleines griechisches Lambda.
Keine Ahnung, woher das kommt, aber es ist halt so.
Also wenn Sie irgendwann mal irgendeine Arbeit lesen, gucken Sie, wenn
da von dem leeren Wort die Rede ist, wie das bezeichnet wird.
Zu allem Überfluss gerade das kleine Lambda, das werden Sie später
auch nochmal sehen, wird auch noch in anderer Bedeutung gerne mal
benutzt in der Informatik.
Also passen Sie ein bisschen auf.
Man kann es nicht verwechseln, aber es kommt halt vor.
Also wir schreiben ein kleines Epsilon und meinen damit in dieser
Vorlesung immer das leere Wort.
In höherer Mathematik ist das Epsilon meistens eine nicht negative,
reelle Zahl und die Vorstellung ist immer klein.
Hier nicht.
Das leere Wort, was ist das?
Also da hilft vielleicht auch der Formalismus noch so ein bisschen.
Oder vielleicht ist das auch noch ein bisschen Übung in Formalismus.
Also was ist formal das leere Wort?
Das ist also, wenn wir mal akzeptieren, das soll ein Wort sein der
Länge Null, dann muss das also formal eine surreaktive Abbildung sein
von Z Null auf die Menge aller Symbole, die im leeren Wort vorkommt.
Da kommen aber gar keine Symbole vor.
Also die Zielmenge muss die leere Menge sein.
Und also Z Null, weil das ja die Länge Null haben soll und Z Null
haben wir gerade gesehen, das ist die Menge aller Zahlen, größer
gleich Null und kleiner Null, das ist auch die leere Menge.
Also der Formalismus sagt, das leere Wort ist eine Abbildung von der
leeren Menge auf die leeren Menge.
Das finden Sie jetzt vielleicht auch ein bisschen befremdlich, weil da
gibt es gar keine Argumente, die man in die Abbildung reinstecken
kann.
Aber das soll uns nicht jucken.
Wir haben gesagt, Abbildungen das sind spezielle Relationen.
Ja, gucken wir uns das mal an.
Also welche Relationen gibt es hier?
Mit einer Menge ist leere Menge, andere Menge ist leere Menge.
Das wären also Teilmengen von leere Menge kreuz leere Menge.
Was ist das?
Das sind alle Paare, wo die erste Komponente aus der ersten leeren
Menge ist und die zweite Komponente aus der zweiten leeren Menge.
Solche Paare gibt es wieder gar nicht.
Also leere Menge kreuz leere Menge ist einfach die leere Menge.
Also Relationen sind Teilmenge der leeren Menge.
Da gibt es nur eine, nämlich die Relation, wo gar nichts drin ist, die
leere Menge.
Das ist die einzige Relation und folglich das leere Wort, diese
Abbildung, das ist eine spezielle Relation, das muss dann auch formal
die leere Menge sein.
Jetzt wird es vielleicht etwas verwunderlich, aber alles ist
konsistent.
Gucken Sie sich mal die Definitionen an, von links total, rechts
total, rechts eindeutig.
Sie werden merken, die leere Menge aufgefasst als Abbildung, also als
spezielle Relation.
Hat alle diese Eigenschaften, das ist einfach eine Abbildung.
Einfach eine sehr spezielle.
Aber wie Sie sehen, es gibt nur eine solche Abbildung.
Das heißt, das leere Wort ist wirklich das leere Wort, es gibt nur
eins, nicht verschiedene.
Und passen Sie auf, also das leere Wort ist etwas, auch wenn es die
Länge Null hat und wenn man nicht Epsilon schreiben würde, wäre es
ganz schlecht zu sehen, aber es ist etwas, ein Objekt, das in einer
Menge drin sein kann.
Also wenn Sie die Menge nehmen, wo das leere Wort drin ist, so ein
Wort der Länge 4 und eins der Länge 8, dann ist die Kardinalität
dieser Menge drei, da sind drei Wörter drin.
Eins ist halt sehr kurz.
Und die Menge, die nur das leere Wort enthält, enthält etwas, das
leere Wort.
Und die Kardinalität dieser Menge ist eins, das ist nicht die leere
Menge, da ist was drin.
Nicht durcheinander bringen.
Die leere Menge, da ist gar nichts drin, die hat Kardinalität Null,
das ist was anderes.
Also das leere Wort ist nicht komplett nichts, man sieht es nur
schlecht.
Irgendwie abstrakt ist es doch etwas.
So wie Null auch eine Zahl ist, obwohl da gar keine Äpfel sind.
Damit haben Sie auch kein Problem.
Und mit dem leeren Wort ist es genauso.
Es ist etwas, wenn auch schwer zu sehen.
So, jetzt manchmal will man vielleicht etwas genauer nicht nur über
die Menge aller Wörter reden, sondern über die Menge aller Wörter der
Länge 3 oder 5 über irgendeinem Alphabet.
Und dafür schreibt man dann A hoch eine nicht negative ganze Zahl.
Also A hoch N soll sein die Menge aller Wörter der Länge N über dem
Alphabet A.
Also wenn wir klein a, klein b haben, dann A hoch 0 enthält alle
Wörter der Länge 0.
Da gibt es nur 1, das leere Wort.
A hoch 1 enthält alle Wörter der Länge 1.
Da gibt es in diesem Beispiel 2, nämlich ein a und ein b.
A hoch 2 enthält alle Wörter der Länge 2.
A hoch 3 alle der Länge 3 und so weiter.
Anders gesagt, A-Stern, die Menge aller Wörter überhaupt ist sozusagen
A hoch 0 vereinigt A hoch 1 vereinigt A hoch 2.
Pünktchen, Pünktchen, Pünktchen.
Und für diese Pünktchen, Pünktchen bei einer großen Vereinigung haben
wir gerade eine Abkürzung vorhin kennengelernt.
Da kann man einfach schreiben, große Vereinigung aller A hoch i für i
aus N0.
Das ist A-Stern.
Also wenn solche Notationen vorkommen, an sowas müssen Sie sich
einfach gewöhnen und lesen und verstehen.
Irgendwie ein Bild haben, Wörter der Länge 0, 1, 2, 3 und so weiter
und alle zusammen.
Genau, also große Vereinigung der A hoch i per Definition.
Das sind alle Wörter mit der Eigenschaft, in mindestens einem A hoch i
ist das W drin.
Jetzt in diesem Beispiel, so A hoch 2 und A hoch 3, diese beiden
Mengen, die sind disjunkt.
Es gibt kein Wort, das in zwei solchen Mengen drin ist.
Jedes Wort hat nur eine Länge.
Das heißt, es gibt mindestens ein i mit W ist in A hoch i.
Das in diesem Fall wird es zu, es gibt genau eins, weil die Mengen ja
disjunkt sind.
Aber im Allgemeinen die Definition ist mindestens eins.
Gut.
Okay.
Einmal durchschnaufen für Sie und für mich.
Jetzt wissen wir alle, hoffentlich immer noch, was ein Wort ist.
Also jetzt kommen wir an den Punkt, wo mir im ersten Semester eine
formale Definition des Begriffs vielleicht ein bisschen geholfen hat.
Schauen wir mal, ob ich Glück habe und Ihnen hilft es vielleicht auch.
Also was machen wir jetzt?
Wir definieren eine Verknüpfung auf der Menge der Wörter.
Also so wie Sie bei Zahlen, Multiplikation haben, Addition, solche
Dinge, macht man jetzt halt auch was mit Wörtern.
Und sozusagen, das nennt man dann die Konkatenation von zwei Wörtern
und da oben steht schon, was es sein soll, anschaulich.
Die Wörter werden einfach hintereinander geschrieben und es wird zu
einem Wort.
Und als Operationssymbol schreibt man typischerweise den Punkt und
das, was mich vor langer Zeit verwirrt hat, war, dass man halt auch
manchmal den Punkt einfach weglässt.
Es ist eigentlich völlig harmlos, aber gut, schauen wir mal.
Also stellen Sie sich vor, Sie haben zwei Wörter, Schrank und
Schlüssel.
Dann können Sie in zwei Reihenfolgen hintereinander schreiben.
Also das Wort Schrank zuerst und dann konkateniert mit dem Wort
Schlüssel, gibt das Wort Schrankschlüssel.
Einfach die Symbole hintereinander weggeschrieben.
Oder umgedreht, erst das Wort Schlüssel und dann dahinter dran
konkateniert das Wort Schrank, gibt halt das Wort Schlüsselschrank.
Das erste, was man sofort sieht, also wenn man die Wörter jetzt mal
auf Deutsch interpretiert, das sind verschiedene Dinge.
Ein Schrankschlüssel ist ein Schlüssel, den können Sie in ein Schloss
strecken und drehen.
Und ein Schlüsselschrank ist ein Schlüsselschrank, den können Sie
aufmachen und da drin liegen oder hängen irgendwelche Dinge.
Also Reihenfolge bei der Konkatenation ist wichtig.
Es ist nicht wie bei Zahlen, 3 mal 5 ist 5 mal 3.
Reihenfolge ist wichtig.
Es ist mehr so wie bei Subtraktionen.
3 minus 5 ist was anderes als 5 minus 3.
Gut.
Also anschaulich war es das schon wieder, mehr ist Konkatenation
nicht.
Also auch wirklich natürlich haben Sie schon wieder ein Verständnis
davon, was hier passiert.
Man schreibt zwei Wörter direkt hintereinander, macht ein drittes
draus, das dann länger ist.
Oder jedenfalls nicht kürzer.
So.
Und wenn man sich das anguckt, so ein bisschen als das Bildchen für,
wir haben hier surrektive Abbildungen von einer Indexmenge auf eine
Teilmenge des Alphabets.
Wenn Sie meinetwegen das Wort Apfel nehmen und das Konkatenieren mit
dem Wort Mousse, dann kommt das Wort Apfelmousse raus.
Und also sozusagen die beiden Argumente, die Sie Konkatenieren, das
ist also eine Abbildung hier, das Wort Apfel, die Buchstaben sind
durchnummeriert von 0 bis 4 und das Wort Mousse, die Buchstaben sind
durchnummeriert von 0 bis 2 und draus kommt das Wort Apfelmousse, das
sind 8-Symbole und die sind also durchnummeriert von 0 bis 7.
So und wenn man sich das so hinmalt, dann sieht man jedenfalls schon
mal so, also manche Zahlen ändern sich.
Hier oben beim Mousse stehen ursprünglich die Indizien 0 bis 2 drüber
und hinterher jetzt in dem neuen Wort haben Sie andere Nummern
gekriegt.
Also etwas passiert da schon.
Nichts Aufregendes, aber etwas.
Und das machen wir jetzt formal.
Also stellen Sie sich vor, wir haben zwei Wörter, also zwei
surreaktive Abbildungen.
Ein Wort W1 von irgendeiner Menge ZM auf eine Menge A1 und M ist die
Länge des Wortes W1 und wir haben Wort W2 von ZN auf A2 und N ist die
Länge von W2.
Das kann die gleiche Länge sein wie W1, kann aber natürlich auch eine
andere sein.
Sie hier oben.
Und dann definieren wir etwas, dafür schreibt man W1 und dann so ein
Punkt dazwischen und dann W2 und also sagen wir mal so, jetzt habe ich
da erstmal was auf die Folie geschrieben.
Folien sind geduldig, die wehren sich nicht, da kann man alles
Mögliche und Unmögliche hinschreiben, auch großen Unfug.
Gucken wir erstmal, was hier steht und wir werden uns dann davon
überzeugen, dass es sinnvoll ist.
Also W1 konkretisiert W2, soll eine Abbildung sein von ZM plus N oder
in eine Menge A1 vereinigt A2 und dann muss ich also für jedes Element
aus ZM plus N sagen, für jede Stelle, was ist der Funktionswert?
Und dann steht hier also an Stelle I der Funktionswert, also das
Symbol, das da steht, ist hier so eine Fallunterscheidung.
Scheuen Sie sich nicht davor, so eine Fallunterscheidung auch
hinzuschreiben.
Also ich erinnere mich auch an mein erstes Semester Programmieren, da
sollte man auch mal irgendwas machen und Fallunterscheidungen haben
mir nicht so gefallen, dann habe ich alles in einen großen
arithmetischen Ausdruck gepackt, der war irgendwie drei Zeilen lang.
Das wurde nicht so gutiert.
Fallunterscheidungen sind nicht böse.
If-then-else darf man ruhig verwenden, wenn es die Sache verständlich
macht.
Also Fallunterscheidung und dann steht hier, dass angeblich an der
Stelle I der Funktionswert ist W1 von I, falls 0 kleiner gleich i
kleiner M und es angeblich W2 von I minus M, falls n kleiner gleich i
kleiner M plus N ist.
Jetzt nehmen wir mal an, das ist irgendwas Sinnvolles und nehmen wir
mal an, das ist tatsächlich wieder ein Wort, was hier festgelegt wird.
Wenn das stimmt, dann sieht man, die Länge dieses Wortes W1, W2 ist
dann jedenfalls M plus N einfach per Definition von was ist die Länge
eines Wortes.
Das ist die Größe dieses Definitionsbereiches und das heißt also die
Länge von W1, W2 ist M plus N ist Länge von W1 plus Länge von W2.
Das klingt plausibel und wenn das eine vernünftige Definition ist,
gilt das jedenfalls.
Aber das, was da hingeschrieben ist, ist das vernünftig.
Also nochmal, Behauptung, wenn W1 und W2 zwei Wörter sind, dann ist
das hier eine vernünftige Definition eines Wortes.
Behauptung, ja.
Und wenn Sie sowas mal sehen und in den kommenden Semestern Sie werden
auch noch Definitionen vorgesetzt kriegen oder mal irgendwann im Pro
-Seminar in irgendwelchen Aufsätzen lesen, die sind noch länger als so
Zwei -Zeilen-Fall-Unterscheidungen.
Lassen Sie sich von sowas nicht abschrecken, auch wenn die Definition
eine halbe Seite lang ist.
Meistens ist die Struktur, also in ganz, ganz, ganz vielen Fällen, die
Struktur völlig harmlos.
Man muss nur den richtigen Abstand finden, nicht zu nah, dass man nur
noch drei Symbole sieht und nicht zu weit weg, dass man überhaupt
nichts mehr erkennen kann.
Aus der richtigen Entfernung sehen Sie dann so grob die Struktur und
kriegen einen Plan, was soll da sein.
Aber da muss man halt so ein bisschen gucken, wie sehe ich es am
besten.
Ist halt so.
Wenn Sie ins Museum gehen, Sie ärgern sich ja auch nicht, dass da
vorne das Bild, das können Sie ganz schlecht sehen.
Was ist denn das für ein blödes Museum?
Machen Sie es ja auch nicht.
Gehen Sie einfach näher hin.
Machen Sie es bei Definitionen genauso.
Wenn das eine Definition sein soll, eine Abbildung, dann sollte man
erstens mal gucken, ist das wirklich eine Definition, eine Abbildung?
Und wenn dann auch noch behauptet wird, das ist nicht irgendeine
Abbildung, das ist ein Wort, also eine subjektive Abbildung oder
irgendwas, dann muss man halt noch gucken, stimmt das auch, was der
Autor da behauptet.
Und das geht auch einfach.
Also bei so einer Fallunterscheidung, wenn man möchte, dass es eine
Abbildung ist, dann muss hier bitte für jedes I aus dem
Definitionsbereich was festgelegt werden.
Sonst fehlt was.
Wenn ich nicht weiß, was W von 3 ist, ist das keine ordentliche
Abbildung.
Also man muss gucken, für alle I aus Z M plus N wird hier etwas
festgelegt.
Naja, in Z M plus N sind alle Zahlen von 0 bis M plus N minus 1.
Für welche I wird was festgelegt?
Erstmal die von 0 bis M minus 1.
Und dann ab M wird hier in der zweiten Zeile was festgelegt.
Also es wird für jedes I was festgelegt.
Das ist schon mal gut.
Dann, wann immer Sie eine Fallunterscheidung haben, in diesem Fall
etwas, in jenem Fall etwas anderes, gucken Sie, ob diese
Beschreibungen der Fälle irgendwie vielleicht sich überlappen und es
Argumente gibt, wo mehrere Fälle zuschlagen.
Das ist jetzt hier zum Glück nicht der Fall.
Also entweder ist I echt kleiner M oder größer gleich M.
Also die Fälle schließen sich aus.
Da kann nichts schief gehen.
Aber wenn es sich überlappt, passen Sie auf, ob dann immer das Gleiche
festgelegt wird, egal, welche Zeile der Definition man nimmt von der
Fallunterscheidung.
Aha.
Warum jetzt konkret genau das dasteht, das sehen wir gleich noch.
Also hier passieren auch keine Widersprüche.
Es gibt kein I, für das beide Fälle überhaupt infrage kommen,
geschweige denn, dass wir drüber nachdenken müssen, ob dann hier das
Gleiche steht oder nicht für diese konkreten I.
Jetzt wird gesagt, hier im Fall von 0 kleiner gleich I kleiner M, der
Funktionswert an der Stelle I ist W1 von I.
Da muss man natürlich gucken, ob das überhaupt existiert, W1 von I.
Für 0 bis M, also der erste Teil, das ist das Wort Apfel.
Das Wort Apfel, da sind die Buchstaben durchnummeriert von 0 bis 4 und
hinterher in Apfelmus steht Apfel vorne, sind die Buchstaben auch
wieder durchnummeriert von 0 bis 4.
Deswegen hinterher an Stelle I will man das Gleiche stehen haben wie
vorher und tatsächlich, also wenn I zwischen größer gleich 0 und
kleiner M ist, das sind genau die I, für die das Wort W1 definiert ist
und W1 von I existiert dann.
Gut.
Und dann ist die Frage, was ist für die größeren I und jetzt gehe ich
nochmal zwei Folien, nein, mehrere Folien zurück.
Also die Frage ist jetzt hier hinten, wenn I größer gleich 5 ist in
dem langen Wort, wo alles konkateniert ist, was steht da an Stelle 5,
6, 7?
Also ab 5, ab Länge des ersten Wortes.
Und da sehen Sie, die Buchstaben, die da stehen, sind die gleichen wie
in dem Wort, das der zweite Faktor von der Konkatenation ist, nur die
Nummern haben sich geändert.
Und das, was jetzt hinterher 5, 6, 7 ist, das war vorher 0, 1, 2.
Und das heißt also, an Stelle 5 steht jetzt das, was vorher an Stelle
0 war, an Stelle 6 das, was vorher an Stelle 1 war und bei 7 das, was
vorher 2 war.
Jetzt gehe ich wieder nach vorne.
Also hinterher steht an Stelle I, 5, 6, 7, das, was vorher beim
zweiten Wort an Stelle 0, 1, 2 stand.
Und da müssen Sie also von dem I M abziehen und wenn I in diesem
Bereich liegt, von M bis M plus N, wenn Sie M abziehen, dann steht da
0, kleiner gleich I minus M, kleiner N.
Und dann I minus M, das sind genau die Indizes, wo Sie im zweiten Wort
nachgucken können, was steht da.
Hier vorne das I ist 5, 6, 7, das I minus 5 ist 0, 1, 2.
Das sind die Buchstaben M, U, S.
Also das ist auch in Ordnung.
Dann, wenn das eine Abbildung ist, das A1 vereinigt A2, alle
Funktionswerte müssen da drin sein.
Es kommt ja nur W1 von I vor, die sind alle in A1 und die W2 von
irgendwas sind alle in A2.
Ist auch in Ordnung.
Und wenn es ein Wort sein soll, die Abbildung soll subjektiv sein, das
heißt jedes Zeichen hier hinten in A1 vereinigt A2 soll auch mal
irgendwo stehen, irgendwo vorkommen.
Das ist so, denn wir nehmen ja nur die aus A1 und A2 hier rein und die
aus A1 kommen garantiert im ersten Faktor vor und die stehen dann auch
in der langen Konkordination.
Und die aus A2 kommen garantiert auch vor, denn die stehen ja im
zweiten Faktor.
Also das ist auch subjektiv, also das ist wirklich eine Abbildung.
Gut.
Ja und jetzt nochmal zum leeren Wort.
Bei den Zahlen stellt man fest, oh die 0 ist ja ein neutrales Element
bezüglich Addition, also jede Zahl x plus 0 ist wieder x und 0 plus x
ist auch wieder x.
Sowas nennt man ein neutrales Element bezüglich der Addition.
Und bei Wörtern über Alphabet bezüglich Konkordination zeigt sich, das
leere Wort ist das neutrale Element.
Das ist wieder anschaulich ganz einfach.
Wenn Sie ein Wort haben, W, und Sie kleben jetzt hintendran noch alle
Symbole aus dem leeren Wort, gibt es gar keine, was rauskommt, ist das
Wort W.
Anschaulich irgendwie offensichtlich und genauso, wenn Sie ein Wort
nehmen und die nicht vorhandenen Symbole davor schreiben, es bleibt
das Wort W.
So, da ist eine Frage.
Also die Frage ist die folgende, angenommen hier bei der
Konkordination, jetzt nochmal eine Folie zurück hier, angenommen es
gibt ein Symbol, das ist sowohl in A1 als auch in A2.
Also zum Beispiel Schlüssel und Schrank, in beiden Wörtern kommt ein S
vor.
So, wenn Sie jetzt die hier vereinigen, da ist das S immer noch drin,
immer noch nur einmal sozusagen, aber das S ist drin, denn es ist ja
in A1, es ist in A2, das S ist auch in der Vereinigung.
Und weil es in der Vereinigung ist, ist es auch kein Problem zu sagen,
an irgendeiner Stelle es steht ein S, egal ob die Stelle weiter vorne
ist und das S steht da, weil es im ersten Faktor drin vorkommt, oder
ob das I weiter hinten ist und das S kommt im zweiten Faktor vor.
Egal ob hier oben im ersten oder im zweiten Fall hier mal S rauskommt,
das S ist in der Vereinigung drin.
Es ist vorhanden.
Gut.
Also jetzt, wir üben mal wieder Beweisen, ein kleines bisschen
schwieriger als A ist Teilmenge von A vereinigt A.
Nochmal die Folie davor.
Ich nehme mal Ihre Frage zum Anlass, ein bisschen was Allgemeineres zu
sagen.
Also die Frage war die folgende, muss ich dann das größer gleich null
hier überhaupt noch hinschreiben, ist doch sowieso klar, dass keine
kleineren Werte infrage kommen, weil wir das ja alles so definiert
haben.
Also erstens, ich bin ja manchmal ein bisschen faul und will nicht
unnötig lange argumentieren müssen.
Zweitens, ich finde immer im Zweifelsfall etwas explizit zu machen ist
besser als irgendwas implizit, so ist ja klar.
Deswegen, also das hier hinzuschreiben ist sicherlich nicht schädlich.
Punkt 1.
Punkt 2.
Ich weiß nicht genau, was Sie weglassen wollen.
Also wenn ich hier das Gleichheitszeichen weglasse, wenn ich behaupte,
i muss echt größer null sein, ist verkehrt.
Die Null ist mit dabei.
Achso, und Sie wollen das ganz weglassen hier, beim ersten Fall.
Ja.
Also Sie sagen, das ist überflüssig, denn i kleiner m steht hier und
dass i größer gleich null ist, kommt daher, dass es ja aus Zm plus N
stammt.
Ja, das ist so.
Aber also auch um die beiden Fälle so syntaktisch ähnlich zu
gestalten, habe ich es halt mit hingeschrieben.
Ja.
Gut.
Also, dritter Anlauf.
Das leere Wort ist neutrales Element bezüglich Konkatenation.
Wir üben, beweisen und jetzt sind wir so ein kleines bisschen
komplizierter als bisher.
Also, wir wollen beweisen, für jedes Alphabet A gilt, für jedes Wort W
aus A-Stern gilt, W konkateniert mit dem leeren Wort ist W und das
leere Wort konkateniert mit W ist W.
Das ist so eine kleine Aussage, die nicht so besonders bedeutend ist.
Die ist wirklich nicht besonders bedeutend.
Das ist elementar, ja.
Sowas nennt man manchmal ein Lämmer.
Gucken Sie mal nach, wo das herkommt.
Wer hatte Griechisch in der Schule?
Boah, nicht so viele.
Einer?
Wer hatte Lateinisch?
Ah, mehr.
Ich auch, aber ich könnte mich jetzt auch nicht auf Lateinisch mit
Ihnen unterhalten.
Als ich studiert habe, hat mal ein Dozent einen Vortrag einfach so mal
Freitagabend angekündigt und jedenfalls der Titel des Vortrags war
Lateinisch.
Ich bin nicht hingegangen, aber vielleicht wäre es interessant
gewesen.
Also anschaulich klar, aber jetzt, wir können es beweisen, wir haben
präzise Definitionen von Konkordination, von leeres Wort.
Tun wir es und üben ein bisschen Beweisen.
Wir müssen etwas beweisen, für jedes Alphabet gilt das.
Nun gibt es viele Alphabete, ja.
Also mindestens zwei Hochanzahlelemente im Unicode-Alphabet, also
mindestens zwei Hochhunderttausende Alphabete, die wollen Sie nicht
alle einzeln betrachten.
Wie beweist man das für jedes denkbare Alphabet?
Naja, man legt sich gar nicht genau fest, man sagt, A ist ein
Alphabet, mehr nehme ich nicht an, mehr wissen wir erstmal nicht, aber
alles was ich jetzt sage, soll bitte so sein, dass es einfach für
jedes Alphabet funktioniert und wenn es für jedes Alphabet
funktioniert, ist ja alles gut.
Zweitens, wir sollen etwas beweisen, für jedes Wort W aus A-Stern und
auch wieder, also die einfachste Variante, es gibt kompliziertere, da
kommen wir dann nächste Woche drauf.
Wie beweise ich, dass etwas für jedes Wort W aus A-Stern geht?
Naja, wieder, nehmen wir halt irgendeins, wir wissen nichts, das
Einzige, was wir annehmen ist, es ist halt ein Wort aus A-Stern.
So, und dann haben wir also ein beliebiges Wort über einen beliebigen
Alphabet und für das sollen wir jetzt beweisen, meinetwegen W,
konkateniert mit dem leeren Wort, ist wieder W.
Also, wir haben ein beliebiges Wort, also jetzt formal eine
surreaktive Abbildung von irgendeinem ZM auf B und B ist Teilmenge von
A und wir haben das leere Wort, das war also die surreaktive Abbildung
von Z0 auf die leere Menge.
Leeres Wort.
So, und jetzt wollen wir, was wir einfach tun werden, ist W
konkateniert mit Y ausrechnen, also nennen wir das mal W- und das
rechnen wir jetzt aus, also W- ist dann auch ein Wort, eine
surreaktive Abbildung, das rechnen wir jetzt einfach mal aus und
vergleichen es mit W und wenn raus kommt, W- ist gleich W, sind wir
fertig.
Also, W- ist W konkateniert mit dem leeren Wort.
Per Definition von Konkatenation ist eine Abbildung von Z-Index M plus
0, ja, Summe der Längen der beiden Einzelwörter auf die Menge
Vereinigung der beiden Zielmengen.
B vereinigt leere Menge.
Naja, ZM plus 0 ist ZM und B vereinigt leere Menge ist B.
Also W- ist wieder eine Abbildung von ZM auf B und jetzt müssen wir
uns davon überzeugen, dass W- gleich W ist.
Naja, gut.
Was macht man?
Was soll man groß machen?
Man nimmt jetzt halt die Definition von Konkatenation und schreibt es
sich mal hin.
Und da auch wieder ein Rat am Rande, ganz unbedeutend, aber manchmal
sehr nützlich.
Versuchen Sie nicht an so einer Stelle dann, ach, jetzt muss ich so
viel schreiben, das versuche ich mal zu optimieren und hier ein
bisschen abkürzen und da und so, dann geht es schneller.
Machen Sie sowas nicht zu früh.
Schreiben Sie lieber 10 Sekunden länger und die komplette
Fallunterscheidung erstmal hin, richtig und fangen Sie dann an, drüber
nachzudenken, was da steht.
Genau wie beim Programmieren.
Versuchen Sie nicht von Anfang an ein möglichst schnelles Programm zu
konstruieren, das irgendetwas tut.
Schreiben Sie lieber erstmal eins, das überhaupt funktioniert.
Ja, jetzt habe ich noch 5 Minuten, also beweisen wir jetzt mal noch,
ja, es klappt, dass dieses W' gleich W ist.
Also was ist die Definition von dem konkatenierten Wort?
Das ist hier einfach diese Fallunterscheidung 1 zu 1 abgeschrieben.
Also W' von I ist W von I für I zwischen 0, also größer gleich 0 und
kleiner m und es ist leeres Wort an der Stelle I minus m, falls m
kleiner gleich I, kleiner m plus 0.
Das habe ich einfach 1 zu 1 aus der Definition abgepinselt und da wo N
stand, die Länge des zweiten Faktors, leeres Wort, habe ich heute hier
die 0 eingesetzt.
So, scharfes Hinsehen ergibt dieser zweite Fall, da muss also I größer
gleich m sein und echt kleiner m.
Gibt's nicht.
Passiert nie, dieser Fall.
Kommt einfach nicht vor.
Das heißt, die zweite Zeile können Sie komplett streichen.
Das ist auch gut so, denn beim leeren Wort, da können Sie keine
Indizes reinstecken und es kommt was raus.
Aber dieser zweite Fall kommt nie vor, das fällt weg und was übrig
bleibt ist W' von I ist gleich W von I für I größer gleich 0 und
kleiner m.
Also auf gut Deutsch für alle I aus Zm und das ist der
Definitionsbereich von W' und auch von W.
Und also W' und W haben den gleichen Definitionsbereich Zm, haben auch
den gleichen Zielbereich B und an allen Stellen I ist der
Funktionswert der gleiche.
Also ist W' gleich W.
Fertig.
Und was haben wir gemacht?
Die Definition für Konkatenation mal eingesetzt und dann geguckt, was
passiert in diesem Fall.
So.
Okay.
Jetzt habe ich noch 4 Minuten, ja, oder viereinhalb.
Was kommt denn hier jetzt noch?
Ach, das sind ja nur zwei Folien.
Ja, die mache ich noch.
So.
Also das eine haben wir vorhin schon gesehen, bei Konkatenation
Reihenfolge ist wichtig.
A konkateniert mit B ist was anderes als B konkateniert mit A.
Aufpassen ist immer so.
Also nein, Sie müssen darauf aufpassen.
Sie dürfen nicht willkürlich Faktoren vertauschen im Allgemeinen.
Zweitens, bei Zahlen sind Sie sowas gewöhnt, wenn Sie x mal y mal z
haben, wie man das klammert ist egal, ob Sie erst x mit y
multiplizieren und das dann mit z oder x multiplizieren mit dem
Ergebnis von y mit z multipliziert, da kommt das gleiche raus.
Sowas nennt man dann Assoziativität und die Behauptung ist, oder die
Mitteilung ist, diese Assoziativität, das gilt auch bei Konkatenation.
Also wenn Sie 3 für jedes Alphabet A, für jedes Wort W1, für jedes
Wort W2, für jedes Wort W3, W1 konkateniert mit W2, in Klammern
konkateniert mit W3, ist das gleiche wie das andere.
Wie beweist man das?
Auf beiden Seiten einfach zweimal die Definition von Konkatenation
einsetzen und ein bisschen umformen und dann stellen Sie fest, auf
beiden Seiten steht ein Wort und was Sie kriegen ist zweimal das
gleiche Wort, gleicher Definitionsbereich, gleicher Zielbereich, an
allen Stellen der gleiche Funktionswert.
Das sind die gleichen Wörter.
Das ist dann länglicher als gerade eben, aber man lernt auch überhaupt
nichts dazu.
Das ist so wie man es erwartet, auch anschaulich.
Wenn Sie drei Wörter hintereinander schreiben, am Ende stehen halt
einfach die drei Wörter hintereinander.
Punkt.
Wo soll da eine Mehrdeutigkeit herkommen?
Also alles ist gut.
Klammern darf man hin und herschieben und deswegen muss man auch gar
keine hinschreiben.
Es ist ja eh egal.
Und dann spart man sich das halt auch gerne.
Aber bitte als Warnung, ich glaube, ich habe das das letzte Mal auch
schon gesagt, hier bei Zahlen, so Multiplikation, alles ist egal.
Es kommt immer das gleiche raus.
In der schönen Mathematik.
Im hässlichen Rechner, wenn Sie da mit Repräsentationen von Zahlen rum
hantieren, da kommen vielleicht unterschiedliche Dinge raus, je
nachdem, was Sie zuerst miteinander multiplizieren.
Da gibt es ganz hässliche Effekte.
Also seien Sie vorsichtig, wenn Sie mit Zahlen im Rechner hantieren.
Oder mit Darstellungen von Zahlen im Rechner hantieren.
Gut.
Und dann sind wir soweit gekommen heute mit der Vorlesung.
Prima.
Das war es für meinen Teil.
Und dann kommt jetzt die große Übung und Herr Modanese wird jetzt noch
mal so ein paar Dinge von letzter Woche und auch von heute so ein
bisschen wiederholen.
Das ist jetzt noch nicht so ganz eingeschwungen, weil eben noch nicht
alle Tutorien hatten.
Dankeschön.
Ja, dann einen schönen guten Morgen meinerseits.
Herzlich willkommen zur Übung.
Mein Name ist Augusto Modanese.
Ich bin ja der Übungsleiter.
Was kommt dann als inhaltliches hier?
Was setzen wir als Ziel an?
Das ist eher so, dass wir die Vorlesung hier ein bisschen vertiefen
wollen.
Sie haben ja Tutorien.
Die Tutorien sind eher für die Wiederholung da, damit sie sich
einüben, die Konzepte der Vorlesungen und so.
Und hier können wir draufbauen und ein bisschen dieses Wissen
konsolidieren.
Ich werde nebenbei auch was vielleicht von eher unmittelbaren Nutzen
für Sie auch geben, nämlich Tipps für das Übungsblatt.
Also manche Themen aus der Übung werden sich ganz nah an den
Übungsblättern halten.
Und da werde ich an manchen Stellen ja direkt explizit sagen, ja das
können Sie zum Beispiel bei einer Aufgabe so und so verwenden.
An anderen Stellen ist es eher so, dass Sie, wenn Sie in der Übung
waren und die Sachen da verstanden haben, dann kann das hilfreich
sein, vielleicht Ideen bei den Lösungen, bei den Lösungsvorgehen in
den Aufgaben zu haben.
Und nebenbei möchte ich auch Bezüge zu anderen Gebieten der Informatik
hier vorstellen.
Höchstwahrscheinlich werde ich hier Sachen aus der theoretischen
Informatik erzählen.
Das ist ja, wo ich unterwegs bin.
Ich versuche auch ein Big Picture zu geben.
An manchen Stellen werde ich auch erwähnen, hier werden Sie das und
das auch in weiteren Vorlesungen sehen.
Ich fange aber leider nicht von Informatik zu reden, sondern von
Mathematik.
Ich muss zweimal blättern, weil ich meine Notizen hier auf dem Laptop
habe.
Und wir wollen jetzt die Mathematik nicht für sich selber anschauen,
natürlich.
Wir möchten aber sie als Werkzeug sehen.
Mathematik arbeitet mit mathematischen Objekten, sozusagen.
Zum Beispiel haben Sie ja kennengelernt, Mengenzahlen, das kennen Sie
ja aus der Grundschule sowieso.
Und ich glaube, wir haben auch letzte Woche in der Vorlesung gesehen,
dass es Abbildungen, Relationen und so weiter gibt.
Und diese Objekte setzen wir fest durch Definitionen.
Und die Definitionen sind präzise
Beschreibungen von was diese Objekte sind und was eben als eine Art
Objekt zählt oder nicht.
Und eine Seite von der Mathematik ist eben diese Objekte zu
identifizieren, die präzise zu definieren, aber auch die anschließend
zu analysieren und dann Aussagen darüber treffen und diese Aussagen
beweisen.
Das letzte Ziel ist eigentlich Wissen herzustellen, indem man Aussagen
beweist.
Und diese Beweise sind so nützlich, also warum die mathematische
Sichtweise hier?
Man kann diese Beweise, die sind für ewig wahr.
Also egal, wer durch die Tür reinkommt, ich kann ihn überzeugen, dass
so und so gilt und deswegen ist die Aussage wahr.
Und wir wollen diese Wahrheiten ableiten.
Warum jetzt für die Informatik ist das überhaupt nützlich?
Wir können zum Beispiel Objekte in der Informatik erkennen und dann
diese mathematisch modellieren und dann mathematisch analysieren und
Wahrheiten davon ableiten.
Wir können Wissen für die Informatik herstellen, indem wir die
mathematische Sichtweise darauf anwerfen.
Zum Beispiel, wir können einen Rechner als ein mathematisches Modell
darstellen und dann sagen, was kann dieser Rechner überhaupt tun?
Welche Probleme kann er denn lösen?
Dieses Gebiet der Informatik nennt sich dann Berechenbarkeitstheorie.
Das kommt in weiterführenden Vorlesungen vor und wir können auch
sagen, vielleicht dieser Rechner ist eingeschränkt, der darf nur so
und so viel Zeit verbringen, der darf nur so und so viele Sprecher
verbringen, was können wir noch dann immer noch lösen?
Dann sind wir im Gebiet der Komplexitätstheorie.
So, das ist ein bisschen eine konzeptionelle Sicht darauf zu geben,
warum ich jetzt die weiteren Themen behandle.
Weil wir nämlich mit den Grundlagen der Mathematik ganz anfangen.
Früher war es nicht so, aber heutzutage ist es so, dass praktisch alle
Objekte in der Mathematik sind eigentlich Mengen.
Sie können Zahlen auch als Mengen darstellen.
Deshalb ist der Begriff der Menge so wichtig, auch wenn wir jetzt was
mathematisch machen wollen.
Sie kennen vermutlich die Mengen von Zahlen, das ist ganz grundlegend.
Es gibt bestimmte besondere Mengen, wie die leere Mengen, die keine
Elemente enthält.
Es gibt Mengen von Zahlen und hier zum Beispiel bei den rationalen
Zahlen, ich kann die nicht so leicht aufzählen wie bei den natürlichen
Zahlen, dass ich einfach mit eins anfange und dann weiterzähle.
Sondern ich muss jetzt dieses Set Comparison verwenden.
Also mir zumindest ist nicht bekannt, wie man jetzt die rationalen
Zahlen so leicht in einer Liste aufzählen kann.
Deshalb haben wir diesen sechgerechten Strich.
Auf der linken Seite steht, wie die Elemente in dieser Menge aussehen,
zum Beispiel Brüche A über B.
Und auf der rechten Seite steht da so eine Bedingung, die sagt, wann
diese Elemente dann der Menge sind oder nicht.
Und natürlich haben wir auch nicht nur Mengen von Zahlen, wir haben
auch Mengen von Mengen und wir haben auch Mengen von Zeichen, das
haben Sie auch in der Vorlesung kennengelernt, wenn Sie mit Mengen von
Zahlen gelangweilt sind.
Auch eine Bemerkung an der Stelle, wenn Sie
jetzt wörtlich ausdrücken, dass ein Element in einer Menge ist, dann
sagen Sie ja, dieses Element ist in einer Menge enthalten und es ist
gar nicht so eindeutig, was das eigentlich bedeutet.
Sie können dieses Enthalten auch für Teilmengen, die
Teilmengenrelation verwenden und dann geraten Sie in Schwierigkeiten,
wenn Sie sagen, die 1 ist in der Menge mit der 1 enthalten, aber die
Menge mit der 1 ist nicht in der Menge mit der Menge mit der 1
enthalten.
Deswegen passen Sie darauf auf, dass Sie klar unterscheiden zwischen
ist Element von Zeichen und ist Teilmenge von Zeichen.
Außerdem es gibt was für jede Menge A gilt, nämlich dass A Teilmenge
von sich selber ist und wiederum haben wir auch, dass die leere Menge
immer in jeder Menge enthalten ist.
Sie hat keine Elemente, aber sie passt überall an.
Deswegen ist das auch so wichtig.
Weil sie keine Elemente enthält, ist es egal, welche Elemente ich
darüber rede.
Sie wird in jeder Menge, egal wie die Elemente aussehen, drin sein.
Was haben wir dann auch als Operationen mit Mengen kennengelernt?
Wir haben ja Vereinigung und Durchschnitt.
Und in der Vereinigung von A und B zum Beispiel, egal was B ist, ist A
wieder enthalten.
In dem Durchschnitt von A und B ist egal was B ist, ist das wieder in
A enthalten.
Auch was wir mit Mengen machen können, ist die Anzahl Elemente drin
zählen, wenn wir ähnlich viele Elemente haben.
Zum Beispiel, wie schon gesagt, die Lehrermenge hat keine Elemente,
deswegen hat sie die Anzahl null Elemente.
Und egal wie viele Mal ich jetzt ein Element in der Menge schreibe,
dann wird das nur einmal gezählt.
Ich kann tausend Mal die drei schreiben, ich werde die drei nur einmal
sehen, wenn ich die Kardinalität dieser Menge betrachte.
Jetzt mit dem Zusammenhang Vereinigung und Durchschnitt haben sie zum
Beispiel diese Formel da, die sie zum Beispiel bei Aufgabe 1.2
einsetzen können.
Nämlich, weil wenn sie jetzt zwei Mengen vereinigen, es kann ja
durchaus sein, es Elemente gibt, die in beiden Mengen enthalten sind.
Es sind Elemente von den beiden Mengen, dann werden sie doppelt
gezählt.
Wenn sie nur die Kardinalität der zwei Mengen addieren.
Deswegen muss ich noch diesen Durchschnitt davon abziehen.
Deswegen kommt diese Rechenregel zustande.
Eine andere Mengenoperation, die sie kennengelernt haben, ist das
Produkt.
Was daraus entsteht, ist dann wieder eine Menge, natürlich.
Die enthält aber nicht einfache Elemente, sondern die enthält Paare.
Diese Paare sind dann so, dass die linke Komponente von dem Paar
dieser Mengen auf der linken Seite des Produkts entspricht.
Und wiederum für die rechte Komponente die Menge auf der rechten
Seite.
Damit man sich schon Gedanken macht über die pathologische Fälle hier.
Was passiert zum Beispiel, wenn eine der zwei Mengen dann leer ist?
Dann habe ich ein Paar.
Sollte ich Paare bekommen, wobei die zweite Komponente ein Element aus
der leeren Menge ist.
Ich habe ja keine Elemente, deswegen kann ich ja auch keine Paare
bilden und deswegen kommt wieder die leere Menge raus.
Und das ist jetzt egal, auf welcher Seite des Produkts diese leere
Menge steht.
Auch hilfreiche Rechenregeln hier ist, dass die Kardinalität von dem
Produkt wieder das Produkt der Kardinalitäten ist.
So kann man das schön formulieren.
Und das gilt insbesondere auch, wenn sie wenn die leere Menge da ist,
dann ist eins der Faktoren gleich null.
Wie kann man sich davon aber überzeugen, dass das gilt?
Sie können die Paare in so einer Tabelle aufschreiben, dann haben sie
Kardinalität von A viele Spalten und Kardinalität von B viele Zeilen.
Dann multiplizieren sie einfach Anzahl Zeilen mal Anzahl Spalten und
dann haben sie ganz genau wie viele Elemente sie in dem Produkt haben.
Eine andere besondere Menge oder Operation, die auf eine Menge
loslassen kann, ist die Potenzmenge.
Dann nehme ich eine Menge A und erhalte ich Mengen, eine Menge von
Mengen und diese Mengen sind Teilmengen von diesem A.
Und das schreiben wir gerne als 2 hoch A.
Es ist jetzt nicht so intuitiv auf der ersten Sicht.
Zwei ist eine Zahl, warum soll das eine Menge bedeuten?
Warum soll das für eine Menge stehen?
Nun ja, wenn Sie das schon mehrmals gesehen haben, dann haben Sie auch
die Kardinalität da vorne im Kopf.
Nämlich die Kardinalität von dieser Potenzmenge ist einfach 2 hoch die
Kardinalität von A.
Wenn das A ähnlich ist, natürlich.
Und zum Beispiel haben sie die Potenzmenge über die leere Menge, dann
kommt wieder eine Menge raus und da sollen dann alle Mengen drin sein,
die Teilmengen von der leeren Menge sind.
Und jede Menge ist Teilmenge von sich selber, deswegen bekomme ich
genau eine Menge wieder und dann bekomme ich eine Menge mit der leeren
Menge.
Das ist nicht die leere Menge, weil diese Menge genau ein Element
enthält, nämlich die leere Menge.
Das ist auch wichtig.
Wiederum, wenn ich weiter mit kleinen Mengen mache, dann bekomme ich
wieder Menge von Mengen, da sehen Sie auch Beispiele.
Und Sie sehen auch, dass ich immer zwei Mengen garantiert wieder in
dieser Potenzmenge wiederfinde.
Das ist einmal die leere Menge, die ist Teilmenge von jeder Menge.
Und zweitens die Menge selber.
Die Menge selber ist Teilmenge von sich selber.
Und in dem Fall der leeren Menge passiert es einfach, dass die beiden
die gleiche Menge sind.
Heute noch in der Vorlesung haben sie diese Schreibweise mit der
großen Vereinigung kennengelernt.
Zum Beispiel habe ich Mengen von A1 bis A5.
So kann ich ein großes U schreiben und dann sagen, welche Indizes da
drin in der Vereinigung über welchen Indizes diese Vereinigung läuft.
Und dann einfach AI schreiben, anstatt alle Mengen aufzulisten.
Das ist besonders praktisch, wenn ich zum Beispiel tausend Mengen habe
oder gar unendlich viele Mengen, wie auf der unteren Seite der Folie.
Und dann nehmen wir an, ich habe zum Beispiel ein BI definiert, das
ist einfach ganze Zahlen, die zwischen Minus I und I liegen.
Zum Beispiel B0 ist die 0 und B1 ist Minus 1, 0 und 1 und so weiter
und so fort.
Und dann kann ich alle diese Mengen unendlich viele Mengen habe ich,
die sind aber auch alle ähnlich und wenn ich die alle vereinige, dann
bekomme ich die ganzen Zahlen, was eigentlich eine unendliche Menge
ist.
Also ich kann die ganzen Zahlen als eine Vereinigung von ähnlichen
Mengen darstellen.
Es ist nicht klar, dass das auch gehen würde, deswegen wenn ich das
schreibe, möchte ich das auch beweisen.
Nicht nur behaupten, sondern beweisen.
Und für die Gleichheit von Mengen gibt es ein ganz einfaches Schema,
wie man das vorgeht.
Zum Beispiel ich habe Mengen A und B, ich will zeigen A ist gleich B.
Ich zeige das einfach, indem ich die zwei Inklusionen zeige.
Dann nehme ich ein beliebiges Element aus der einen Menge und zeige
ich, dass dieses Element auch in der anderen Menge liegt.
Und dann das für beide Richtungen.
Und warum reicht das aus?
Warum ist es so, dass ich dann bekomme, dass die Mengen gleich sein
müssen?
Warum kann es...
Das ist einfach dadurch gegeben, dass die Menge nur damit
gekennzeichnet, also die Identität von dieser Menge nur dadurch
beschrieben wird, welche Elemente sie enthält oder nicht.
Es ist nicht so, dass ich eine Menge hier A haben kann, die zum
Beispiel 1, 2 und 3 enthält und wenn ich eine andere Menge habe,
unterschiede ich davon, die 1, 2, 3 enthält.
Die gleichen Elemente.
Es ist komplett irrelevant, was drumherum um diese Elemente liegt.
Es ist egal, es ist nur der Inhalt der Menge, der eben wichtig ist.
Das ist vielleicht ein bisschen philosophisch hier, aber an manchen
Stellen der Mathematik stößt man an diesen philosophischen Grenzen.
Das ist auch...
Das kommt einfach durchaus vor.
Und dann kann ich diese Aussage von vorher beweisen, wenn ich wieder
diese zwei Inklusionen zeige.
Und zuerst fange ich mit der Inklusion von ganzen Zahlen in dieser
großen Menge.
Dann nehme ich ein beliebiges x, wenn es eine ganze Zahl ist und wenn
das größer gleich 0 ist, dann kann ich einfach das bx nehmen.
Das x ist auf jeden Fall in dem bx enthalten, weil es zwischen minus x
und x liegt.
Wenn das x kleiner gleich 0 ist, dann kann ich auch b minus x nehmen
und dann ist das wieder zwischen diesen zwei Zahlen, minus x und minus
minus x.
Und dann habe ich gezeigt, für jedes x gibt es ein i in 0, sodass x in
diesem b enthalten ist.
Und dann ist das in der großen Vereinigung auch enthalten.
Wiederum, wenn ich zeigen will, die andere Richtung ist ganz
einfacher, weil wenn ein x in dieser Vereinigung liegt, dann muss es
in einem b liegen.
Und wenn es in einem b liegt, ist das einfach die Definition.
Ich habe geschrieben, b enthält ganze Zahlen, sodass die Bedingungen
so und so erfüllen.
Und dann habe ich diese andere Inklusion.
Dann sind wir zum Ende der Übung.
Ich bedanke mich für die Aufmerksamkeit und wünsche euch noch eine
schöne Woche.