Fangen wir an.
Schönen guten Tag.
Grundbegriffe der Informatik.
Zweite Vorlesung.
Wir haben am Ende gerade noch angefangen, am Mittwoch, mit dem dritten
Kapitel.
Im zweiten ging es ja erst nochmal so, habe ich erstmal so ein paar
grundlegende Dinge erzählt.
Das Wesentliche, was Sie davon bitte nie vergessen, unterscheiden Sie
immer deutlich, sauber, zwischen dem, was irgendwo steht, als
Nachricht, als Text, eine Folge von Zeichen, Sie erinnern sich an 1 0
0 0 0 0 1, und der Interpretation davon, die offensichtlich
unterschiedlich sein kann.
Sie haben das gesehen, verschiedene Personen hier im Hörsaal haben
diese Zeichenfolge ganz unterschiedlich interpretiert.
Also so ein Wort, das man irgendwo hinschreibt, das kann verschiedene
Dinge bedeuten.
Und man muss sich halt dann irgendwie einig sein, worum es gerade
geht.
Wichtig, nie vergessen, unterscheiden Sie das sauber.
Und diese saubere Trennung, die werden Sie in diversen Kapiteln immer
wieder sehen.
Da werde ich Sie auch nicht in Ruhe lassen damit.
Man muss das einfach unterscheiden.
Gut.
Und was ich Ihnen auch schon mal gesagt habe, also in einem präzisen
Sinne, es gibt Probleme, die kann man nicht mit dem Rechner lösen.
Sie sind zu schwierig für eine präzise Definition von Problem und eine
präzise Definition von Rechner.
Und darauf werden wir aber dann in einem späteren Kapitel sowieso noch
mal genauer eingehen.
Und also wenn Sie aus diesem Dilemma raus wollten, dann müssen Sie
entweder an der Definition von Problem was ändern oder an der
Definition von Rechner.
Sie müssen sich einschränken oder was verallgemeinern, was auch immer.
Aber so wie die Dinge definiert sind, üblicherweise Standard.
Es gibt Probleme, die können Sie einfach nicht mit dem Rechner lösen.
Gut.
Bevor wir soweit sind, brauchen wir aber noch so ein paar Grundlagen,
damit wir präzise reden können, präzise Aufgaben stellen können, Sie
präzise Lösungen für die Aufgaben hinschreiben können und irgendwie,
dass man sich vernünftig unterhalten kann.
Und das ist ein bisschen wie eine andere natürliche Sprache lernen.
Ja, man braucht halt ein paar Vokabeln.
Es gibt ein paar Regeln, wie man die Vokabeln so benutzt.
Und darum geht es halt jetzt hier erst mal in diesem Kapitel 3.
Und im nächsten Kapitel fangen wir dann an, diese Begriffe zu
benutzen.
Tendenziell neige ich dazu, jedenfalls in dieser Vorlesung, in diesem
Vorlesungsskript, Ihnen immer erst mal ein, zwei Beispiele von
irgendetwas vorzusetzen und danach zu sagen Okay, und jetzt definieren
wir das in Anführungszeichen allgemein oder etwas abstrakter.
Ja, das ist wie bei kleinen Kindern.
Ich meine, die überfällt man auch nicht mit 1, 2, 3, sondern man zählt
erst mal Äpfel oder Autos oder Krokodile.
Und dann irgendwann sind es nur noch die Zahlen, ohne was anderes
dabei.
Und das scheint ja ganz gut zu funktionieren.
So, also wir fangen jetzt an, mit so ein bisschen allgemeinen
Bemerkungen noch zu mengen, damit Sie bitte auch irgendwie vernünftig
die Sachen hinschreiben können.
Und dann fangen wir schon mal an, so ein bisschen konkreter.
In dem zweiten Abschnitt Alphabete kommt dann Unicode vor.
Wer hat das Wort Unicode schon mal gehört?
Okay, gut, ja.
Und dann ist man aber auch sozusagen schon ganz natürlich dabei, über
Relationen und Abbildungen zu reden und da sich so ein paar Begriffe
anzugucken, Eigenschaften, die Abbildungen haben können oder nicht.
Und dann im letzten Teil noch so drei, vier, fünf Folien, so ein paar
zusätzliche Dinge, die immer nützlich sind.
Also erst mal Mengen.
Das machen wir im Grunde ganz naiv.
Und das ist gefährlich.
Ich weise gleich nochmal darauf hin.
Aber wir machen halt hier nicht axiomatische Mengenlehre in der
Mathematik.
Und die Beobachtung ist, also für die harmlosen Dinge, die wir hier so
tun, ist alles in Ordnung.
Gut.
Es gibt zwei Dinge, zwei Arten irgendwie so Namen zu benutzen für
irgendetwas.
Und das taucht jetzt auch immer wieder in allen möglichen
Formulierungen ständig überall, die ganze Vorlesung auch in allen
Vorlesungen auf.
Halten Sie das auseinander?
Das eine ist, dass man sich manchmal einfach nicht den Mund fußlich
reden will und dann sagt, also ich führe jetzt einfach eine Abkürzung
ein.
Ich sage jetzt nur noch Groß A.
Und ich meine zum Beispiel immer die Menge, die enthält die Zahlen 1,
2 und 3 und sonst nichts.
Das ist natürlich eine Vereinbarung, die gilt dann vielleicht für die
Dauer dieser Vorlesung, vielleicht auch nur für eine halbe Folie.
Da muss man dann halt immer ein bisschen aufpassen.
Aber das ist natürlich nichts, wenn Sie übermorgen in irgendeiner...
Übermorgen vielleicht nicht.
Nächste Woche in irgendeine andere Vorlesung gehen oder in irgendeinen
Laden und sagen Groß A.
Der, dem Sie das sagen, der wird nicht wissen, was das soll.
Natürlich nicht.
Also es gibt immer so einen begrenzten Bereich, in dem dann diese
Abkürzung irgendwie gültig ist.
Und da muss man sich halt einig sein.
Das ist übrigens beim Programmieren auch so.
Führen Sie variablen Namen ein, aber die sind halt nur gültig in einem
gewissen Bereich.
Also wer schon ein bisschen programmiert hat, nichts Neues.
Und das andere ist, dass man manchmal so sagt, also angenommen A ist
jetzt eine Abkürzung für irgendeine ganz konkrete Menge.
Und dann sagen Sie vielleicht sowas, es sei jetzt x ein Objekt, das in
der Menge A drin ist.
Und dann reden Sie und benutzen klein x.
Und was Sie aber meinen, ist nicht ein ganz bestimmtes Element aus der
ganz konkreten Menge A, sondern Sie wollen jetzt etwas sagen,
vielleicht etwas beweisen.
Und das soll halt funktionieren, egal welches Element, das Sie jetzt
gerade betrachten.
Und dann sagen Sie halt, ja, so allgemein irgendein x.
Und egal, was Sie sagen, ja, das, was Sie sagen, egal, ob Sie sich
jetzt vorstellen, dass x ist die 1 oder die 2 oder die 3 oder noch ein
anderes Element in der Menge, in dem Beweis, es soll halt immer wahr
sein.
So.
Also das ist wie so ein Platzhalter und Sie können da irgendwas
einsetzen und immer ist alles in Ordnung.
Gut.
Und für uns einfach eine, also nicht nur für uns, also das ist immer
so, ja, eine Menge ist einfach festgelegt dadurch, welche Elemente
sind drin, welche Objekte sind drin.
Nichts anderes.
Also wenn Sie zweimal eine Beschreibung einer Menge hinschreiben und
aus beiden Beschreibungen geht hervor, es ist genau die 1 drin, die 2
und die 3 und sonst nichts, dann es wird die gleiche Menge
beschrieben.
Und wenn ein Element drin ist, dann schreiben wir x Element A, wie Sie
das wahrscheinlich in der Mathematik auch schon gesehen haben.
Und wenn ein Element nicht drin ist, dann streicht man dieses
Elementzeichen halt durch.
Und man fängt dann an, so Abkürzungen zu machen, kürzer zu reden,
kürzer zu schreiben, so es sei x Element A.
Und das ist nur noch, hat nur ein Drittel der Länge des ausführlichen
Satzes oben drüber, ist einfacher zu erfassen, kann man leichter
damit, kann man leichter verstehen, wenn man was liest.
Und wenn man es redet, geht es schneller, auch gut.
So, und wenn wir jetzt sagen, eine Menge ist dadurch und nur dadurch
festgelegt, welche Elemente sind drin und welche nicht, dann heißt das
also, zwei Mengen sind genau, also jetzt wieder, wenn wir ein A haben
und ein B, und das sind jetzt aber, jetzt benutzen wir A und B als
solche Variablen, egal welche Menge A Sie nehmen und egal welche Menge
B Sie nehmen, zwei Mengen sind gleich, wenn für jedes Objekt gilt,
also wenn es in der einen Menge drin ist, wenn es in A drin ist, ist
es auch in B drin, und wenn es in B drin ist, ist es auch in A drin.
Die gleichen Objekte sind in A und in B.
Das ist die Definition von Mengengleichheit, nichts anderes.
Gut.
Also, es kommt nur drauf an, welche Elemente sind drin und welche
nicht.
Punkt.
Ganz einfach.
Jetzt, wenn Sie zwei Mengen haben, manchmal sind nicht genau die
gleichen Elemente drin, da können unterschiedliche Dinge passieren.
Und ein Fall, den man oft hat, um den man sich oft kümmern will, sagen
wir mal so, ist, dass jedenfalls jedes Element einer Menge A auch in
einer anderen Menge B drin ist, und dann sagt man auch, A ist
Teilmenge von B und schreibt dann A und dann diesen Bogen und
vielleicht noch einen kleinen Strich dafür, es kann auch gleich sein,
B und sagt dann, A ist eine Teilmenge von B oder was das Gleiche
bedeutet, B ist eine Obermenge von A und wenn Sie das andersrum
hinschreiben wollen, dann können Sie das auch spiegeln.
Links das B, rechts das A und das Inklusionszeichen, wie dieser Bogen
heißt, auch gespiegelt.
So, also A ist Teilmenge von B, wenn jedes Element von A auch Element
von B ist.
Und wenn Sie nochmal zu Hause eine Folie zurückblechtern und gucken,
was ist die Definition von Gleichheit zweier Mengen, dann sehen Sie
ja, Gleichheit zweier Mengen ist äquivalent zu, also A ist gleich B,
wenn A Teilmenge von B ist und B Teilmenge von A.
Und das ist dann auch ein Rezept direkt, um zu beweisen, dass zwei
Mengen gleich sind.
Sie haben zwei Mengen, die kommen irgendwo hier, irgendwelche
Beschreibungen, irgendwelche Definitionen, wenn Sie beweisen sollen,
das ist beides die gleiche Menge, die enthalten die gleichen Elemente,
man zeigt halt die beiden Inklusionen.
Also man zeigt dann für jedes Element, das in A drin ist, ist es in B
und umgekehrt jedes Element, das in B drin ist, ist es auch in A.
Machen wir auch gleich an dem Beispiel.
So, na prima, aber jetzt, wie schreibt man denn Mengen konkret hin?
Also wenn die Menge klein ist, wenig Elemente enthält, ist das ganz
einfach, man zählt sie halt alle auf und man macht dann geschweifte
Klammern außenrum.
Geschweifte Klammern, keine runden, keine eckigen, keine spitzen,
geschweifte Klammern.
Sie sehen so aus, wie hier auf der Folie.
Und meinetwegen, hier diese Menge enthält dann halt 1, 2, 3, 4, 5 und
die 42 und das Zeichen A und das Zeichen B.
Das geht, wenn die Menge klein ist, wenn die Menge 10 hoch 21 Elemente
enthält, wird es schwierig.
Die will man nicht alle hinschreiben.
Aber bleiben wir erstmal bei kleinen Mengen.
Da können Sie vielleicht noch ein paar Elemente dazu machen, können
auch ein paar weglassen.
Und Extremfall, Sie schreiben die Menge hin und da sind gar keine
Elemente drin.
Das gibt es auch.
Also Sie schreiben die geschweiften Klammern hin und dazwischen steht
aber nichts.
Keine Elemente.
Das ist die leere Menge.
Die gibt es auch, so wie es die Zahl 0 gibt.
0 Krokodile stehen gerade vor Ihnen auf dem Tisch.
Nichts Besonderes.
Manchmal statt der geschweiften Klammern und nichts dazwischen,
schreibt man auch so einen Kringel, mehr oder weniger rund, der
irgendwie noch so einen Schrägstrich durchgeht.
Also die leere Menge gibt es auch.
Und Sie erinnern sich, zwei Mengen sind gleich, wenn Sie die gleichen
Elemente enthalten.
Ob Sie jetzt geschweifte Klammern hinschreiben und dann 1,2,3 oder 3,2
,1, da sind die gleichen Elemente drin.
Das ist die gleiche Menge.
Und auch wenn Sie sich Mühe geben und irgendwie dreimal die 1
hinschreiben und fünfmal die 3 hinschreiben, um zu betreuern, ja
wirklich, die 3 ist da ganz bestimmt drin.
Trotzdem, sie ist nur einmal drin.
Das ist die gleiche Menge.
Dinge mehrfach hinschreiben führt nicht dazu, dass die Menge größer
wird.
Die Menge hier rechts, 1,1,2,3,3,2,1,3,3,3, enthält auch nur die 1,
die 2 und die 3.
Enthält nur drei Elemente.
Auch wenn Sie es umständlich hingeschrieben haben.
Gut.
Wichtig, nicht vergessen.
Ich weiß, das ist nicht ganz leicht, aber trotzdem.
So, ja, also bei kleinen Mengen kann man sich so behelfen, aber
irgendwann werden die Mengen halt größer und man will über sowas
reden, wie die natürlichen Zahlen.
Ohne Null oder mit Null.
Und erstens, also Achtung, auf der Welt gefühlt die eine Hälfte, wenn
sie natürliche Zahlen sagt, meint die Zahlen ab 0, die nicht negativen
ganzen Zahlen 0,1,2,3,4,5 und die andere Hälfte, wenn sie natürliche
Zahlen meint, meint die Zahlen ab 1, 1,2,3,4,5.
Deswegen, da ist nichts besser und nichts schlechter.
Und damit da keine Missverständnisse entstehen, also erstens die
Zahlen ab 1, die nenne ich die positiven ganzen Zahlen und die Zahlen
ab 0 nenne ich die nicht negativen ganzen Zahlen und unterstelle, dass
wir uns einig sind, was sind die ganzen Zahlen.
Und dann benutze ich eben, weil diese Mengen halt ganz oft vorkommen,
so Abkürzungen, so ein N, wo einer dieser Striche irgendwie doppelt
ist, ein senkrechter oder der schräge Strich.
Und wenn ich die positiven ganzen Zahlen meine ab 1, dann schreibe ich
unten noch so ein kleines Pluszeichen dran.
Und wenn ich die nicht negativen Zahlen einschließlich 0 meine,
schreibe ich an das N unten eine kleine 0 dran.
Es gibt auch haufenweise Leute, die benutzen dieses N mit dem
Doppelstrich ohne irgendwas unten dran geschrieben, aber auch wieder
gefühlt die eine Hälfte der Welt meint, die 0 ist da dabei und die
andere Hälfte meint, nein, wir meinen nur die Zahlen ab 1.
Und da finde ich es albern, jetzt für eine Vorlesung zu definieren.
Wir meinen jetzt aber das und in der anderen Vorlesung ist aber genau
das andere.
Das hilft keinem.
Also benutze ich das N mit dem Doppelstrich ohne was unten dran
einfach gar nicht.
Aber ich habe hier Pünktchen hingeschrieben, weil ich halt auch nicht
diese ganz diesen positiven ganzen Zahlen alle hinschreiben kann.
Das sind unendlich viele.
Aber bitte übrigens Achtung.
Ja, jede natürliche Zahl ist endlich groß.
1 ist eine endliche Zahl.
2, 3, 47 ist eine endliche Zahl.
3 Milliarden ist eine endliche Zahl.
Jede einzelne Zahl ist endlich groß.
Aber es sind unendlich viele.
So und bei den natürlichen Zahlen, also bei den bei den positiven
ganzen Zahlen oder bei den nicht negativen.
Ich unterstelle einfach, dass wir uns hoffentlich so ungefähr das
gleiche vorstellen.
Bei unendlich vielen Zahlen.
Toi, toi, toi.
Aber wann immer man eine konkrete Frage stellen würde, irgendjemand
von Ihnen ist die Zahl dabei oder nicht, sie wären sich alle einig.
Das ist keine Frage.
Aber es ist schon so ein bisschen riskant.
Irgendwie.
Und Sie können sich ja mal fragen, woher das eigentlich kommt, dass
Sie wahrscheinlich alle die gleiche Vorstellung haben.
Keiner von Ihnen hat schon jemals alle nicht negativen ganzen Zahlen
gesehen.
Nur manche.
Nur endlich viele.
Man kann jede sehen, wenn man will, sich hinschreiben, aber nicht
alle.
Was macht man denn dann bei anderen unendlich großen Mengen?
Also erstens, wir schreiben keine Pünktchen mehr.
Das darf ich mal ausnahmsweise auf Folien.
Sie dürfen es nie, wie gesagt.
Niemals Pünktchen schreiben und dann denken, ist ja klar, was ich
meine.
Nein.
Nichts ist klar.
So, wenn man andere große Mengen oder vielleicht auch kleine
Teilmengen von so einer unendlichen Menge festlegen will, eine
Möglichkeit ist so eine Notation, die heißt im Englischen Set
Comprehension.
Und ich weiß kein vernünftiges deutsches Wort.
Also ich habe schon einen Begriff gefunden, aber den finde ich doch
etwas sperrig, um es mal vorsichtig zu sagen.
Was man da macht ist, man notiert eine Menge, deswegen außenrum stehen
geschweifte Klammern.
Und um dann zu sagen, welche Elemente sind in der Menge drin, also
stellen Sie sich vor, es gibt schon eine große Menge M irgendwoher,
von der man weiß, jawohl, die haben wir einfach, wir wissen, was
gemeint ist, nehmen wir die mal groß M, dann erlauben wir so etwas
hinzuschreiben, die Menge aller, und das jetzt lese ich halt, wie ich
das so normalerweise lese, die Menge aller X aus der Menge groß M und
dann kommt so ein senkrechter Strich, das lese ich als mit der
Eigenschaft und dann dahinter zwischen dem senkrechten Strich und der
geschweiften Klammer zu, steht so eine Aussage, irgendwas, was immer
wahr oder falsch ist und was irgendwie von dem X abhängt.
Also zum Beispiel hier unten, die Menge aller X aus den positiven
ganzen Zahlen mit der Eigenschaft X ist ohne Rest durch zwei teilbar.
Das sind dann also auf gut Deutsch die geraden Zahlen.
Und wenn wir davon ausgehen, N plus, das haben wir einfach, da müssen
wir uns nicht mehr groß drüber unterhalten.
Es ist uns klar, hoffentlich, was das ist.
Dann ist das hier halt eine Teilmenge davon.
Man nimmt halt manche her, nur noch die, die eine Eigenschaft haben.
Eine gewisse.
Und manchmal lassen wir auch noch dieses Element von M weg und man
schreibt nur noch hin die Menge aller X mit der Eigenschaft P von X.
Und hofft, dass dann immer noch klar ist, welche X gemeint sind.
Und manchmal ist es halt einfach klar.
Wir reden hier über die Menge M und dann ist es klar.
Manchmal sind wir vielleicht auch etwas salopper.
Aber so wie wir das hier verwenden, ist alles gut.
Gott sei Dank.
Aber hier lauert eine Gefahr.
Darauf will ich Sie nur hinweisen.
Wir werden nur harmlose Dinge tun, es passiert kein Unglück.
Aber wenn man es genau anguckt, muss man aufpassen.
Das hier ist Bertrand Russell.
Gucken Sie mal nach, wer das war.
Bemerkenswerter Herr.
Philosoph, Mathematiker, Politiker.
Hat mit Herrn Whitehead ein dreibändiges Werk geschrieben.
Über die Grundlagen der Mathematik so richtig nicht, wir nehmen an,
wir wissen schon, was natürliche Zahlen sind und dann machen wir
etwas, sondern wirklich so weit unten wie nur irgend möglich.
Und dann gibt es, das fängt sehr langsam an und dann kommt im ersten
Band auf Seite, das wollte ich Ihnen eigentlich zeigen.
Er kommt zum Beispiel irgendwo auf Seite 379 im ersten Band, kommt ein
kleiner Beweis von etwas und dann steht drunter, also wenn wir dann
später mal Addition eingeführt haben, dann wird uns das helfen, um zu
beweisen, dass 1 plus 1 gleich 2 ist.
Also lesen Sie mal ein bisschen nach und das Paradoxon von Herrn
Russell ist also sozusagen sowas, was aussieht wie eine Set
Comprehension.
Aber wenn man drüber nachdenkt, stellt man sehr schnell fest, man darf
hier offensichtlich nicht beliebige Dinge sagen, also dieses P von X,
das darf nicht beliebig sein und es ist erst mal gar nicht klar,
worauf man sich einschränken muss.
Also das, was man da hinschreibt, was Herr Russell in seinem Paradoxon
hier hinschreibt, ist zwar ein bisschen ungewöhnlich, aber sieht im
Prinzip völlig harmlos aus, aber es führt dazu, dass alles explodiert.
Und offensichtlich nicht alles eine Menge ist, was man so hinschreiben
kann.
Also vielleicht wollen Sie mal drüber nachlesen.
So, wenn man erst mal zwei Mengen hat, dann definiert man Vereinigung
und Durchschnitt von zwei Mengen.
Für die Vereinigung schreibt man A vereinigt B, also mit so einer
Badewanne zwischen A und B und per Definitionen, da sind alle Objekte
drin, die in A drin sind oder in B.
Also X ist in A vereinigt B.
Genau dann, wenn X in A ist oder X in B oder beides.
Dieses Oder ist kein ausschließendes Oder in genau einem, sondern in
einem oder im anderen oder in beiden.
Also 1, 2, 3 vereinigt mit 3, 4, 5 ist 1, 2, 3, 4, 5.
So, und Durchschnitt, da nimmt man nur die Elemente in den
Durchschnitt, die sowohl in A als auch in B sind.
Also der Durchschnitt von 1, 2, 3 und 3, 4, 5 ist halt nur 3.
Und es kann natürlich passieren, dass hier als Durchschnitt die leere
Menge rauskommt.
Ja, wenn die eine Menge nur die geraden Zahlen enthält und die andere
Menge nur die ungeraden, der Durchschnitt ist halt leer.
Keine Zahl ist beides.
Und Sie können sich ja auch mal überlegen bei Vereinigung und
Durchschnitt, was passiert, wenn eine der beteiligten Mengen leer ist.
Und dann gibt es so allerlei Rechenregeln, die alle mehr oder weniger
einleuchtend sind.
Also zum Beispiel, wenn Sie eine Menge mit sich selbst vereinigen,
dann kommt die Menge selber wieder raus und genauso A geschnitten, A
ist wieder A.
Und das gilt, also alles, was hier steht, gilt für jede Menge A, jede
Menge B, jede Menge C.
Also hier A, B, C, das sind jetzt nicht irgendwie konkrete Mengen 1,
2, 3 und 3, 4, 5 und noch was, sondern egal, welche Mengen Sie nehmen.
Ja, das gilt immer.
Wenn Sie zwei Mengen vereinigen, die Reihenfolge ist egal.
Ja, A vereinigt B, ist das gleiche wie B vereinigt A und für den
Durchschnitt auch.
Wenn Sie mehr als zwei Mengen vereinigen wollen, dann, also erstmal
ist ja nur definiert, zwei Mengen zu vereinigen, dann müssen Sie halt
in irgendeiner Reihenfolge vereinigen.
Also erst A und B und dann noch C dazu oder umgekehrt erst B und C zum
Beispiel und dann A dazu.
Beobachtung, die Mengen, die rauskommen, sind gleich.
Kann man alles beweisen.
Genauso für den Durchschnitt.
Und das ist aber alles ähnlich langweilig.
Ja, und man lernt gar nichts dabei und das ist einem irgendwie klar.
Und zum Beispiel, weil A vereinigt B vereinigt C, weil da immer das
gleiche rauskommt, egal wo die Klammern sind, lässt man sie dann halt
auch gerne mal ganz weg.
Es ist ja egal.
Und dann gibt es hier die Distributivgesetze.
Das kennen Sie auch so ein bisschen.
Das hat alles irgendwie analoger, zum Beispiel bei natürlichen Zahlen
mehr oder weniger.
A plus B ist B plus A.
A mal B ist B mal A.
A plus B plus C ist A plus B plus C, egal wie Sie es klammern.
Jedenfalls wenn Sie die echten Zahlen, die abstrakten Gebilde aus der
Mathematik haben, seien Sie vorsichtig, wenn Sie im Rechner mit
irgendwelchen Nährungsdarstellungen von irgendwelchen komischen Zahlen
rechnen.
Wenn Sie da drei Zahlen addieren, da kann es schon mal passieren, dass
unterschiedliche Ergebnisse rauskommen, je nachdem, wie Sie klammern.
Vorsicht.
So, Distributivgesetze A plus B in Klammern mal C kennen Sie.
Das ist A mal C plus B mal C.
Also hier A vereinigt B.
Das Ganze geschnitten mit C ist A geschnitten C vereinigt mit B
geschnitten C.
Und hier bei der Menge, wenn Sie Vereinigung und Durchschnitt
austauschen, es gilt immer noch.
Das ist in der Arithmetik falsch.
X mal Y plus Z ist nicht X mal Z.
Nee, Quatsch, ist nicht X plus Z mal Y plus Z.
Das gilt einfach nicht.
Und jede Menge A ist Teilmenge von A vereinigt B und A geschnitten B
ist immer Teilmenge von A.
Kann man alles beweisen.
In einem Fall tun wir es jetzt mal.
Und jetzt nicht, weil der Beweis besonders aufregend ist oder das
Ergebnis besonders bemerkenswert.
Nein, sondern um jetzt mal so ein bisschen Beweisen zu üben, so ganz
allgemein und jetzt so ein bisschen im Zusammenhang mit Mengen.
Denn immer wieder kommt die Frage dann irgendwann von irgendwem an der
oder jenen Stelle.
Ja, jetzt soll ich hier was beweisen, wie mache ich das denn?
Oder wenn da ein Beweis steht, ja, wie soll ich denn da drauf kommen?
Tja, das erfordert einfach Übung.
Dinge beweisen ist übrigens auch etwas, was Sie nicht komplett dem
Rechner übertragen können.
Es ist kein Wunder, dass man sich da manchmal schwer tut.
Also für eine präzise Definition von in welchem Bereich wollen wir
etwas beweisen und für eine präzise Definition von was heißt etwas
beweisen.
Also, wie beweist man etwas?
Also nehmen wir an, wir wollen hier beweisen diese eine Aussage für
jede Menge A.
A ist das gleiche wie A vereinigt A.
Das soll man beweisen.
Für jede Menge A.
Dann erstens, das steht hier gar nicht explizit, jetzt sollen wir das
für jede Menge beweisen.
Mengen gibt es wahrscheinlich ziemlich viele, um es mal vorsichtig zu
sagen.
Wie sollen wir das beweisen, wenn wir gar nicht wissen, um welche
Menge es geht?
Naja,
führen wir halt so eine Variable groß A ein und sagen ja, das ist eine
Menge.
Was wissen wir?
Nichts, außer es ist halt eine Menge.
Und alles was wir jetzt sagen, um etwas zu beweisen, das muss halt
richtig sein, egal welche Menge A das wirklich konkret dann wäre.
Gut.
Also sei A irgendeine Menge.
Wir wissen nichts, außer es ist eine Menge.
Und wir sollen das zeigen.
Eine Menge gleich einer anderen Menge.
Wie beweist man Gleichheit von zwei Mengen?
Habe ich gerade schon mal gesagt.
Naja, zwei Mengen sind genau dann gleich, wenn erstens die linke Seite
Teilmenge von der rechten Seite ist.
A Teilmenge von A vereinigt A.
Und zweitens die rechte Seite Teilmenge der linken Seite ist.
A vereinigt A Teilmenge A.
Und die Definition von Teilmenge ist, jedes Element der Teilmenge ist
auch Element der Obermenge.
Also wir müssen dann beweisen, jedes Element, das aus A ist, ist auch
Element von A vereinigt A.
Und umgekehrt, jedes Element von A vereinigt A ist auch Element von A.
Bis hierhin habe ich noch gar nichts getan.
Außer, naja, also ein bisschen schon, ja, sonst wären wir schon
weiter.
Also erstens dieses Beweisprinzip, was bedeutet, wie kann ich manchmal
zeigen, zwei Mengen sind gleich, hier einfach mal hingeschrieben.
Und dann diese beiden Inklusionen einfach hingeschrieben.
Was ist die Definition dieser Inklusion?
Also was bedeutet, was sagt die Definition der Inklusion in diesen
konkreten Fällen?
Konkret in Anführungszeichen.
Eine beliebige Menge A.
So.
Und jetzt muss man halt beides beweisen.
Und was heißt das?
Also, naja, da steht ja, wenn X, ich formuliere jetzt ein bisschen um,
bei erstens, wenn X Element von A ist, dann ist X auch Element von A
vereinigt A.
Also, womit geht es los?
Was weiß ich?
Naja,
jetzt muss ich für jedes Element der Menge A etwas beweisen.
Und ich weiß noch nicht mal, welche Menge das groß A ist.
Also, ich benutze einfach kleinen x für jedes x-beliebige Element, das
in der Menge A drin ist.
Das ist offensichtlich die Voraussetzung.
Und was muss ich beweisen?
Das ist auch immer ganz nützlich, wenn Sie irgendwas beweisen müssen.
Also, erstens, schreiben Sie sich halt mal hin, was Sie an
Voraussetzungen haben.
Und zweitens, schreiben Sie sich halt mal hin, was das Ziel ist, wo
Sie hinwollen.
Wenn Sie eine Reise machen, ist es ja manchmal auch ganz nützlich, zu
wissen, wo fahre ich los und wo will ich eigentlich hin.
Das ist nicht immer so.
Sie können sich auch einfach aufs Fahrrad setzen und in den Wald
losradeln, weil Sie die Nase voll haben von Informatik am
Sonntagnachmittag oder so.
Und dann fährt man einfach irgendwo hin, Ziel egal.
Aber hier gibt es ja ein Ziel.
Und das Ziel ist, wir wollen beweisen, dieses gleiche x ist Element
von A vereinigt A.
Also, Voraussetzung, das wissen wir, x ist in A und wir wollen
einsehen, x ist in A vereinigt A.
Immer noch inhaltlich nicht groß, was passiert.
Da ist der Start, da ist das Ziel und jetzt muss man das halt
irgendwie füllen.
Was kann man tun?
Also, bei x ist Element von A, was soll man noch groß tun?
Da ist nichts mehr zu tun.
Also, muss man sich vielleicht mal das Ziel angucken.
Da steht die Vereinigung von zwei Mengen, da kann man sich ja
vielleicht mal hinschreiben, was das bedeutet.
Und dann guckt man halt nach, was ist die Definition von Vereinigung
und die Definition von Vereinigung ist, naja, also x ist in A
vereinigt A, wenn genau dann, wenn x Element von A ist oder x ist
Element von A.
Also, jetzt einfach ignorieren Sie mal die rechte Hälfte einfach so
auf der linken Seite.
Das eigentliche Ziel umformuliert in etwas Äquivalentes per Definition
von Vereinigung.
Ja, und jetzt in diesem schönen, einfachen Fall ist man schon fertig,
wenn scharfes Hinsehen ergibt.
Also, wenn x aus A ist oder x aus A, dann natürlich ist x in A
vereinigt A, das ist ja genau die Definition.
Und von der Voraussetzung x ist Element von A folgt daraus, dass x
Element von A ist oder x ist Element von A.
Ja, also da müssen Sie jetzt nicht mehr argumentieren, das ist in
Anführungszeichen einfach logisch.
Und im übernächsten Kapitel machen wir Aussagenlogik und da werden Sie
sehen, ja, das ist auch im Sinne der Aussagenlogik völlig logisch
sozusagen.
Ja, und dann ist man fertig.
Wenn x Element von A ist, dann ist x Element von A oder x ist Element
von A.
Und das ist die Definition von x ist Element von A vereinigt A.
Und damit sind wir am Ziel angekommen.
Und das war Teil 1.
Und Teil 2 geht genauso.
Also, da ist die Voraussetzung, ist es Element von A vereinigt A.
Das Ziel ist, wir wollen einsehen, x ist Element von A.
Was kann man tun?
Naja, man schreibt sich einmal hin, was die Definition von Vereinigung
ist.
Also, aus der Voraussetzung folgt sofort x ist Element von A oder x
ist Element von A.
Ja, und wieder.
Es ist völlig logisch, dass dann x von A ist.
Fertig.
So.
Und auf diese Art und Weise nur viel länglicher diese ganzen anderen
Gleichheiten, Gesetze, die da gerade standen, Distributivgesetze und
was weiß ich alles, kann man alle so runterprügeln auf irgendwelche
logischen Zusammenhänge, wo man sagt, ja, ist doch klar.
Noch ein bisschen mehr zu Mengen.
Manchmal will man auch reden über die Elemente in einer Menge A, die
nicht in einer anderen Menge B sind.
Und dafür schreibt man dann hier sowas mit so einem Backslash zwischen
A und B.
Und also, wenn wir das sozusagen als Set Comprehension hinschreiben,
also das lesen wir als A ohne B und das ist also sozusagen per
Definition die Menge aller x aus A mit der Eigenschaft x ist nicht
Element von B.
Also die Menge 1, 2, 3 ohne die Elemente in der Menge 3, 4, 5.
Da müssen wir halt nur die 3 weglassen, die 4 und 5 sind eh nicht
dabei, bleibt halt noch 1, 2.
Und wenn Sie sich das als Bildchen hinmalen, also einen Kringel für
eine Menge A und drunter einen Kringel für eine Menge B und die
überlappen sich so ein bisschen,
dann eben A ohne B, das ist eben der Teil des oberen Kringels, der für
A steht, der sich nicht mit dem unteren Kringel für B überlappt.
Und umgekehrt für B ohne A unten.
Und der Überlappungsbereich, das sind sozusagen in dem Bild gerade die
Elemente aus dem Durchschnitt A geschnitten B.
Manchmal ist es nützlich, über die Größe einer Menge zu reden.
Also entweder man sagt einfach Größe oder manchmal etwas genauer
Kardinalität.
Das machen wir hier nur für endliche Mengen.
Also wir werden sowas wie A in senkrechten Strichen oder so eine
Abkürzung Card A für die Kardinalität einer Menge nur wirklich
benutzen für endliche Mengen und das bedeutet einfach die Anzahl der
Elemente, die da drin sind.
Und
also wenn Sie zum Beispiel die Mengen 1,2 und die Menge 2,3 angucken,
jede von den beiden enthält zwei Elemente.
Das sind also zusammen, also wenn Sie beiden Kardinalitäten addieren,
2 plus 2 ist 4, aber wenn Sie die Mengen vereinigen, kriegen Sie halt
nur 1,2,3 und die Kardinalität der Vereinigung ist 3.
Also Vorsicht, wenn Sie zwei Mengen vereinigen, die Kardinalität des
Ergebnisses kann also zumindest offensichtlich in diesem Beispiel
kleiner sein als die Summe der Größen der beteiligten Mengen.
So.
Und die Anzahl der Elemente, das in einer Menge ist also immer eine
nicht negative ganze Zahl.
1,2,3,4,5 oder auch mal 0.
Die leere Menge enthält 0 Elemente.
So.
Wir werden es uns verkneifen, für Mengen, die mehr als nur endlich
viele Elemente enthalten, von ihrer Kardinalität zu reden.
Also wir sagen dann halt, die Menge ist unendlich groß.
Kardinalität von Mengen kann man auch für unendliche Mengen betreiben.
Und da passieren viel kompliziertere Dinge, als Sie sich jetzt gerade
vorstellen wollen oder können.
Oder ich auch.
Das tun wir hier nicht.
Man kann das ordentlich machen.
Aber das ist Mathematik.
Und nicht erstes Semester Mathematik.
Also es gibt, so wie es unterschiedlich große endliche Mengen gibt,
gibt es auch unterschiedlich große unendliche Mengen.
Nicht einfach unendlich ist gleich unendlich.
Unendliche Mengen können deutlich unterschiedlich groß sein.
Gut.
Okay.
So viel kurz zu Mengen.
Wer hat dieses Bild oder so ein Bild von diesem Stein schon mal
gesehen?
So ein paar.
Also dieses Ding heißt im Englischen Rosetta Stone.
Viele Grüße vom Display.
Also das ist ein Stein.
Da stehen Zeichen drauf.
In der oberen Hälfte das sind Hieroglyphen.
Also da steht was auf Ägyptisch sozusagen.
Habe ich Hälfte gesagt?
Sagen wir mal Drittel.
Im unteren Drittel steht was in einer Schrift.
Das erinnert doch sehr an das, was auch heute in Griechenland noch
geschrieben wird.
Also das ist Griechisch.
Und in der Mitte steht was in einer anderen Schrift, die heißt
Demotisch.
Und das, was da steht, ist aber auch auf Griechisch sozusagen.
Und der Punkt ist, man wollte gerne wissen, was bedeuten diese
Hieroglyphen.
Und dann hat man diesen Stein gefunden.
Und dann hat Herr Champillon gesagt,
Champillon...
Mein Französisch ist nicht existent.
Da steht ja bestimmt in all drei Texten das Gleiche.
Und altes Griechisch und altes Demotisch, das können wir ja schon
lesen.
Hypothese in Hieroglyphen steht da genau das Gleiche.
Und das hat dann wesentlich dazu beigetragen, tatsächlich zu
entziffern, wenn man einen Hieroglyphentext hat, was steht denn da.
Konkret auf diesem Stein, worum geht es?
Da loben Priester, König sowieso, ich weiß nicht mehr welcher Name,
der fünfte von Ägypten, zum Beispiel für seine Steuersenkungen.
Das gab es schon damals.
Also jedenfalls Steuern.
So.
Also jetzt habe ich schon die ganze Zeit gesagt, da stehen Zeichen.
Was ist ein Zeichen?
Wie bei den natürlichen Zahlen, da fragen wir nicht weiter nach.
Wir unterstellen einfach, dass wir das gleiche Verständnis davon
haben, was ein Zeichen ist.
Also sowas wie die Buchstaben, die in einer deutschen Tageszeitung zum
Beispiel vorkommen.
Oder vielleicht nur zwei Zeichen, so eine 0 und eine 1.
Oder vielleicht nur ein Zeichen, ein senkrechter Strich.
Oder vielleicht die Zeichen 0 bis 9 und Groß A bis Groß F.
Oder vielleicht so eine 1 und eine 0 und eine 1, die auf dem Kopf
steht.
Und jetzt tun wir dann mal so, als wäre eine auf dem Kopf stehende 1
ein anderes Symbol.
Und
also das Problem ist, auf dieser ganzen Folie, auf allen Folien, auch
im Vorlesungsskript, überall stehen Zeichen.
Zeichen, wohin man guckt.
Jetzt hier habe ich also die Zeichen, die jetzt so hier explizit in
einer Menge aufgeführt sind, als die interessieren uns.
Die habe ich hier blau gemacht, um das deutlich zu unterscheiden vom
Rest.
Alles, was schwarz ist, das sollen Sie interpretieren als deutschen
Text.
Und das, was blau ist, also hier, das sollen Sie bitte nicht
interpretieren.
Hier steht nicht die Zahl 0, da steht ein blauer Kringel.
Und daneben steht nicht die Zahl 1, sondern da ist ein blauer
senkrechter Strich und oben an dem Strich ist noch so ein kleiner
Haken und unten ist noch so ein kleiner Strich.
Das ist ein Symbol, der bedeutet nichts.
Erstmal.
So.
Und eine Menge von Zeichen, mit der Unterstellung, wir wissen, was
Zeichen sind, eine endliche Menge von Zeichen wollen wir einfach ein
Alphabet nennen.
Das darf groß sein, das darf klein sein, aber bitte nicht leer.
Also mindestens ein Zeichen wollen wir schon haben, sonst ist
irgendwie alles doof.
Punkt.
Also für uns in den Mickey-Maus-Beispielen immer das Alphabet ist 0, 1
oder klein a, klein b, klein c oder irgendwie sowas.
Wenn Sie irgendwie mir das mal glauben wollen, wenn Sie später mal
eine Vorlesung über Compilerbau hören oder so, dann werden Sie sehen,
aus Ihrem Eingabetext wird dann vom Programm irgendetwas gemacht und
das interpretiert dann so kompliziertere Dinge als jeweils ein
Zeichen.
Also hier so ein Semikolon ist einfach für sich vielleicht ein
Zeichen, aber so eine Zeichenfolge i, kleines i, kleines n, kleines t,
da müssen Sie dann so ein bisschen abstrahieren sozusagen, das ist
dann für den Compiler nur noch ein Zeichen, obwohl Sie da auf drei
Tasten gedrückt haben, als Sie das Programm geschrieben haben.
Also das sind dann irgendwie so kleine Lego-Blauklötzchen, die
zersägen Sie nicht in noch kleinere Teile, so wie Sie ein kleines a
auch nicht in irgendwelche blauen Atome zerhacken oder irgendwie und
sagen, ach da ist ja noch was kleineres.
So, also manchmal vielleicht auch später mal ein bisschen abstrakter.
So, also das ist schon alles.
Jetzt wissen Sie, was ein Alphabet ist, eine endliche Menge von
Zeichen.
Zwei Alphabete spielen oder haben gespielt eine große Rolle in der
Informatik.
Das eine ist der American Standard Code for Information Interchange,
ASCII.
Der enthält irgendwie 94 sogenannte druckbare Zeichen, die die
Amerikaner halt brauchen konnten.
Also zum Beispiel Buchstaben von A bis Z, Ziffern, runde Klammern,
solche Sachen.
Und einige sogenannte unsichtbare Zeichen.
Und das war es dann.
Und da fehlt also jede Menge von Zeichen, wo Sie sagen würden, na, das
hätte ich aber auch gerne, wenn ich einen Text schreibe.
Also alles Mögliche aus allen möglichen europäischen Schriften, so AES
oder hier so ein N mit einer Schlange oben drüber aus dem Spanischen
oder so ein C mit einer CD unten dran.
Das kam gerade im Namen von dem Herrn vor, der Hieroglyphe
entschlüsselt hat.
U mit einem Kringel oben drüber.
Es gibt da alles Mögliche.
Ganz zu schweigen, also das ist alles nicht in ASCII drin, ganz zu
schweigen von total anderen Schriften, ja, Kirillisch, Chinesisch,
irgendwas, alles nicht drin.
Das wurde dann im Laufe der Zeit, und wir sind alle vernetzt und eine
Welt und global und tralala, wurde das dann doch etwas sehr restriktiv
und irgendwann hat man gesagt, okay, also jetzt sollten wir das
vielleicht doch nochmal so ein bisschen allgemeiner angehen und hat
man also angefangen, das zu definieren, also Unicode und das
beinhaltet insbesondere ein großes Alphabet von Zeichen.
Das Alphabet ist inzwischen ziemlich groß, so jenseits von 100.000
Zeichen und da wird nicht nur gesagt, hier ist die Liste von allen 100
.000 Zeichen, sondern zu dem ganzen Unicode-Standard gehört noch mehr,
also jedes Zeichen kriegt einen Namen, es wird für verschiedene
Sprachen definiert, was ist denn die Sortierreihenfolge von den
Buchstaben jeweils und nur damit Sie sich da nicht vertun, also selbst
in Europa, ja, in Schweden Wörter werden in einer anderen Reihenfolge
sortiert als in Deutschland zum Beispiel.
Hierzulande hat man sowas wie Groß- und Kleinbuchstaben und zu welchem
Großbuchstaben wo ist die Entsprechung, welcher Große gehört zu
welchem Kleinen, sowas steht auch in Unicode drin.
Mittlerweile steht da übrigens auch für das Deutsche ein großes,
scharfes S drin.
Ich weiß nicht, ob Sie das schon mal gesehen haben, das ist etwas
gewöhnungsbedürftig, aber gut.
Da steht sowas über Schreibrichtung für verschiedene Sprachen und,
und, und, und, und, und.
Also Unicode umfasst ziemlich viel, aber insbesondere eine endliche,
nicht leere Menge von Zeichen und es sind irgendwie hundert und ein
paar tausend.
Für ASCII habe ich hier Ihnen so einen Auszug aus der ganzen Tabelle
mal hingeschrieben und bei ASCII ist es so, jedes Zeichen hat eine
Nummer und zum Beispiel Groß-A hat die Nummer 65 und ich vermute mal,
also bei 1, 0, 0, 0, 0, 0, 1 aus der letzten Vorlesung vielleicht
erinnern Sie sich, manche haben schon gesagt 65 und andere haben
gesagt Großes A und dass das eine der anderen das andere gesagt hat,
das liegt wahrscheinlich daran, dass eben im ASCII-Zeichensatz das
Große A die Nummer 65 hat.
Und bei Unicode haben Zeichen auch Nummern und bei Unicode das Große A
hat auch Nummer 65.
Ja, und was übrigens hier insbesondere beim ASCII und beim Unicode
-Zeichensatz dabei ist, ist so ein Zeichen, das man normalerweise,
also jetzt hier in europäischen Schriften heutzutage benutzt, um
irgendwie so ein bisschen Abstand zu machen zwischen zwei Dingen, die
man als Wörter bezeichnet, so ein Leerzeichen und damit man es aber
doch hier auf den Folien, wenn ich denn mal sagen will, hier ist das
Leerzeichen, dann male ich nicht das Leerzeichen hin, weil man das so
schlecht sieht, sondern so ein kleines blaues, eckiges Ding.
Dass Sie aber interpretieren sollten als das Leerzeichen, dass man
nichts sieht, aber in Wirklichkeit auch blau ist.
Und naja, als es irgendwann mal losging mit E-Mails, wurde zum
Beispiel gesagt, was in E-Mails vorkommen kann, das sind die Zeichen
aus dem ASCII-Zeichensatz und nichts anderes.
Und so eine E-Mail hat ja immer eine gewisse Struktur.
Da gibt es eine Zeile, da weiß ich nicht, ob Sie das jemals schon mal
so roh gesehen haben.
Mittlerweile kriegt man da ja immer vor allen möglichen bunten
Schnickschnack außen rum gezeichnet.
Also so eine E-Mail hat immer eine Zeile, die fängt an mit From,
Doppelpunkt und dann steht da die E-Mail-Adresse vom Absender und es
gibt eine Zeile To, Doppelpunkt, E-Mail-Adresse von Empfänger und dann
irgendwo ist der eigentliche Text und wenn ich das richtig gemacht
habe, steht da mit dem richtigen Datum, wann die nächste Klausur ist.
Also 18.
März, 14 Uhr und es gibt einen Standard, das Ding heißt RFC 5.322, das
ist jetzt nicht mehr der aktuelle, ich weiß, aber da stand zum
Beispiel wirklich drin, in E-Mails sind nur ASCII-Zeichen erlaubt.
Jetzt vermute ich mal ganz stark, dass viele von Ihnen schon mal eine
E -Mail auf Deutsch verschickt haben.
Wer hat das getan und vermutet, dass da ein Umlaut oder ein scharfes S
drin war?
Zu wenig?
Na, also heutzutage irgendwie, es geht doch.
Und naja, da gibt es zwei Möglichkeiten, wie man die Umlaute in die E
-Mails reinkriegt und eine Möglichkeit, das sehen wir dann im späteren
Kapitel über Codierungen und andere Möglichkeiten sind, dass halt
irgendwann ein aktualisierter Standard gesagt hat, okay, jetzt wir
erlauben nicht nur ASCII, wir erlauben mehr.
Was auch immer.
So, bei Unicode, also wir haben dieses große Alphabet mit 100.000
Zeichen, das nenne ich jetzt mal immer A Index U, damit wir da
irgendwie, damit ich nicht immer sagen muss, das große Unicode
Alphabet.
Eine Abkürzung für ein ganz konkretes Alphabet.
Und was Unicode insbesondere festlegt, ist zu jedem Zeichen eine Zahl.
Die heißt dann typischerweise der Code Point dieses Zeichens.
Und da werden aber nicht die Zahlen von 1 bis 100.000 benutzt, sondern
am Anfang so ein paar Zahlen und dann gibt es ja hier und da Lücken
von Zahlen, die nicht benutzt werden.
Also das ist nicht fortlaufend nummeriert.
Und dann gibt es also offensichtlich eben irgendwie eine Beziehung
zwischen den Unicode Zeichen, also den Elementen klein a aus groß a u
und den nicht negativen ganzen Zahlen n aus n null.
Und wenn man so eine Beziehung hat, dann ist das ein Beispiel für eine
sogenannte Relation.
Und das ist das, was wir jetzt als nächstes uns angucken wollen.
Was ist eine Relation?
Was ist eine Abbildung?
Eine Relation ist auch eine Menge und die enthält sogenannte Paare.
Also stellen Sie sich vor, wir haben zwei Mengen, groß a und groß b
und ein Element klein a aus groß a und ein Element klein b aus groß b.
Und dann schreiben wir sowas hin, runde Klammer und jetzt bitte immer
runde Klammern, keine geschweiften, kein irgendwas, runde Klammer,
klein a, klein b, runde Klammer zu.
Das nennen wir ein Paar und das klein a nennt man die erste
Komponente, das klein b die zweite Komponente und die beiden sind
immer da bei jedem Paar.
Und es ist auch nicht verboten, da als erste und zweite Komponente das
gleiche zu nehmen, kann ja groß a gleich groß b sein oder so.
Also 1,1 in runden Klammern ist auch ein Paar.
Und da stehen diese zwei Einser und das sind verschiedene Dinge, das
eine ist erste Komponente, das eine ist zweite Komponente.
Das ist nicht wie eine Menge, wo dann halt jetzt die Eins drin ist
oder so.
Das ist was anderes.
Und zwei Paare, also das erste, wenn man irgendetwas einführt, man
sagt, wann sind zwei so Dinger gleich.
Und zwei Paare a, b und x, y sind genau dann gleich, wenn die ersten
Komponenten übereinstimmen, a gleich x und die zweiten Komponenten
auch übereinstimmen, b gleich y.
Also das Paar 1,2 ist nicht gleich dem Paar 2,1.
Die ersten Komponenten sind verschieden.
Die zweiten auch.
Gut.
Und die Menge aller Paare, wo die erste Komponente aus Groß A und die
zweite aus Groß B ist, nennt man das kathesische Produkt A Kreuz B,
lese ich das immer.
Also A Kreuz B ist die Menge aller Paare und das schreibe ich jetzt
hier auch einfach mal so hin mit der Eigenschaft klein a aus Groß A
und klein b aus Groß B.
Manchmal will man nicht, also bei einem Paar, sie haben eine feste
Reihenfolge, erste Komponente, zweite Komponente.
Manchmal will man nicht zwei Dinge in einer festen Reihenfolge haben,
sondern vielleicht drei oder vier.
Und das kathesisches Produkt von zwei Mengen ist wieder eine Menge.
Wenn Sie M1 Kreuz M2 schon haben, dann können Sie natürlich das nehmen
und kathesisches Produkt mit der dritten Menge M3 machen.
Und was ist dann da drin?
In dieser Menge sind Paare drin.
Die zweite Komponente ist aus M3, nennen wir es mal X3 und die erste
Komponente von so einem Paar stammt aus M1 Kreuz M2.
Das heißt, die erste Komponente von diesem großen Ding ist selber
wieder ein Paar X1, X2.
Und dann sagt man, ach ja, diese vielen Klammern, das ist aber
irgendwie doof.
Die möchten wir bitte auch weglassen können.
Und dann schreibt man einfach nur eine Runde Klammer auf, X1, X2, X3
Runde Klammer zu.
Und man schreibt auch einfach M1 Kreuz M2 Kreuz M3 und macht da auch
keine Klammern mehr.
Und dann hat man das, was man Triple nennt.
Und dann das gleiche oder das analoge jetzt Hände wedeln für vier
Mengen, fünf Mengen, sechs Mengen, Pünktchen, Pünktchen, Pünktchen.
Sowas will man auch manchmal haben.
Preisfrage, wie definiert man das ohne diese Pünktchen?
Hier ist jetzt ein erstes schönes Beispiel, wo Sie sehen, dass das mit
den Pünktchen manchmal tatsächlich gefährlich ist.
Ich habe da jetzt hingeschrieben N1 Kreuz M2 Kreuz Pünktchen,
Pünktchen, Pünktchen, Kreuz MN.
Ja, was ist denn jetzt?
Also wenn N gleich 5 ist, also wenn ich Sie bitten würde, das jetzt
explizit auszuschreiben, ich wette, Sie würden alle das gleiche
hinschreiben ohne die Pünktchen.
Aber ist das noch sinnvoll, wenn ich für N 2 hinschreibe?
Da steht da M1 Kreuz M2 Kreuz Pünktchen, Pünktchen, Kreuz M2.
Meinen wir da noch alle das gleiche?
Was ist denn, wenn N gleich 1 ist?
Gefährlich.
Da wird es wirklich gefährlich.
Deswegen machen wir das ordentlich.
Also großes kathesisches Produkt machen wir da ein großes Kreuz
von Mengen MI.
Und jetzt gehen wir mal davon aus, dass wir Mengen MI haben für alle
positiven ganzen Zahlen von 1 bis N.
Und die Menge jetzt auf dieser und den nächsten zweieinhalb Folien
oder so.
Die Menge aller positiven ganzen Zahlen von 1 bis N, also die Menge
aller I aus N plus mit der Eigenschaft I ist kleiner gleich N.
Das nenne ich jetzt mal einfach PN.
Also das enthält die Zahlen, die natürlichen Zahlen von 1 bis N.
Das ist nichts Geheimnisvolles.
Und für jedes N aus M plus ist das eine vernünftige Menge.
Wenn N gleich 1 ist, enthält die Menge nur die 1.
Wenn N gleich 2 ist, enthält die Menge 1 und 2 und so weiter.
Wir haben uns geeinigt auf eine gewisse Anzahl N.
Und dann nehmen wir mal an, für jedes I von 1 bis N, also für jedes I
aus PN haben wir eine Menge MI.
Und dann definieren wir das große kathesische Produkt aller MI, wo I
aus dieser Menge PN ist.
Wie definieren wir das jetzt?
Erstmal für den Fall N gleich 1.
Also großes kathesisches Produkt für alle I aus der Menge P1.
Das heißt, I kann überhaupt nur den Wert 1 annehmen.
Von MI, also das ist einfach M1.
Das ist eine Definition.
Hier links ist ja irgendeine Schreibweise.
Jetzt wird definiert, was das bedeutet.
Und man sagt, ja, das ist M1.
Jetzt hat man also für N gleich 1 hier definiert, was das sein soll.
Bleiben noch die Fälle 2, 3, 4, 5, 6, 7, 8 und so weiter.
Und das macht man jetzt so, dass man sich weiterhangelt und jetzt
nicht für jeden Fall 1 in irgendwas hinschreibt, sondern sagt, für 1
haben wir es jetzt explizit.
Was die Bedeutung für 2 ist, da benutzen wir schon mal die Bedeutung
für 1.
Und was es dann für 3 ist, da benutzen wir schon mal die Bedeutung für
2.
Und wenn wir wissen, was es für 3 ist, dann auch für 4.
Und wenn wir es für 4 haben, dann auch für 5.
Wenn wir es für 5 haben, für 6 und so weiter.
Also für jedes N aus M+.
Und wenn Sie jetzt ein großes kathesisches Produkt von N plus 1 Mengen
MI haben, also I läuft jetzt von 1 bis N plus 1, was soll das sein?
Das soll das große kathesische Produkt der Mengen MI für I von 1 bis N
sein.
Und dann kleines kathesisches Produkt, so wie wir das kennen.
Zwei Mengen.
Links eine, rechts eine.
Und was dann rechts noch dazukommt, ist MN plus 1.
Und manchmal
statt I aus PN schreibt man auch so großes kathesisches Produkt von I
gleich 1 bis N.
So, jetzt habe ich hier oben einfach nochmal die Definition
hingeschrieben.
Hier steht nichts Neues in den ersten beiden Zeilen.
Und jetzt können Sie einfach mal anfangen und rechnen und zum Beispiel
gucken, was ist ein großes kathesisches Produkt für die I aus P2, also
für die I von 1 bis 2 der Mengen MI.
Also die erste Zeile sagt einem da nichts, das ist ja nur der Fall P1.
Das heißt, wenn man wissen will, was das ist, muss man die zweite
Zeile benutzen von der Definition.
Und wenn wir wissen wollen, wie ist das für P2, dann muss man hier in
der Definition für das kleine N bei PN plus 1 für N1 einsetzen.
Dann ist N plus 1 gerade 2.
Und dann auf der rechten Seite steht dann, also man macht etwas für
die I aus PN, also I aus P1 der MI kathesisches Produkt mit MN plus 1
und N plus 1 ist 2.
Und dann haben wir hier ein großes kathesisches Produkt stehen und da
steht aber in der ersten Zeile, was das sein soll, nämlich einfach M1.
Also großes kathesisches Produkt der MI für I von 1 bis 2 ist M1 kreuz
M2.
Ah, schön.
So wollte man das natürlich haben.
Dann haben wir das also für 2 und wenn Sie dann für 3 machen, die
Definition der kathesisches Produkt der MI für I von 1 bis 3 ist laut
zweiter Zeile der Definition großes kathesisches Produkt der I von 1
bis 2.
Und dann noch hinten dran kathesisches Produkt mit dem letzten, mit M3
und bis 2 haben wir gerade gesehen, das ist M1 kreuz M2 und dann noch
kreuz M3 dran.
Und dann für 4, 5, 6 können Sie sich so weiter hangeln und man sieht,
das was rauskommt ist irgendwie das Plausible.
Und deswegen hat man die Definition auch so gewählt.
Man ist ja frei, das so zu machen, dass es einem in den Kram passt.
Und das ist eine ganz wichtige Sache.
Manchmal kriegt man irgendwelche Definitionen vorgesetzt und die sehen
kompliziert aus und man denkt sich, oh, was ist das denn
Kompliziertes, wo soll das hinführen?
Solche Definitionen fallen nicht vom Himmel.
Da hat nicht jemand eine große Tüte mit Symbolen, schüttelt die, kippt
die aus und schaut, was steht denn jetzt für eine schöne Definition
da, sondern man macht etwas, was einem sinnvoll erscheint, was einem
weiterhilft.
Also man definiert das so, weil es einem in den Kram passt.
Und man nimmt hier so ein großes Kreuz in Anlehnung an das kleine
Kreuz für kathesisches Produkt von zwei Mengen.
So eine ähnliche Notation haben Sie vielleicht schon in der Schule
gesehen, haben Sie jetzt vielleicht schon in Mathematikvorlesungen
gesehen.
Wenn Sie Zahlen addieren wollen, viele Zahlen, dann benutzt man,
schreibt man manchmal auch nicht hin x1 plus x2 plus x3 pünktchen,
pünktchen, pünktchen plus xn, sondern man schreibt da so ein großes
Sigma, so ein großes griechisches Sigma, Summenzeichen.
Ist das in der Mathematik jetzt schon vorgekommen?
Ja, gut.
Aber das bedeutet eben Summe, Addition von Zahlen.
Das hier ist kathesisches Produkt von Mengen.
Das ist jetzt zumindest, wenn man jetzt naiv von außen drauf schaut,
sind das verschiedene Dinge.
Und wenn man genauer hinguckt, sind es immer noch verschiedene Dinge.
Deswegen nimmt man ein anderes Zeichen.
Gut.
Ja, und was haben wir hier gemacht hier oben bei der Definition?
Also wir haben erstmal für den Fall n gleich 1 explizit
hingeschrieben.
Was soll das sein?
Und dann haben wir hier sowas hingeschrieben.
Ja, angenommen, wir wissen schon, was es für den Fall n bedeutet, dann
können wir jetzt auch hinschreiben, was bedeutet es für den Fall n
plus 1.
Also man fängt erstmal an mit 1 oder 0 oder was auch immer.
Und dann man schreibt hin, wie komme ich von dem einen Fall zum
nächsten komplizierteren für ein größeres n.
Sowas nennt man eine induktive Definition.
Und sowas werden wir ganz oft sehen, weil das eine prima Möglichkeit
ist, um Pünktchen, Pünktchen, Pünktchen zu vermeiden.
Und das ist auch immer sehr schön, also wenn man etwas so definiert
hat, dann ist auch immer relativ naheliegend, auf welche Art und Weise
man dann irgendwelche Aussagen beweist, nämlich mit vollständiger
Induktion.
Da fängt man auch am Anfang an explizit und dann, warum geht es immer
weiter von einem zum nächsten.
Man muss sich natürlich fragen, warum ist es denn legal, sowas
überhaupt hinzuschreiben.
Man definiert den Fall n plus 1 und nimmt Bezug auf den Fall n.
Warum ist das legal?
Na ja, so wie ich das immer beschrieben habe, klingt es halt
plausibel.
Man weiß es für 1 und wenn man es erstmal für 1 weiß, dann weiß man es
eben auch für 2.
Und wenn man es erstmal für 2 weiß, dann weiß man es auch für 3.
Aber wenn man sich genauer hinschaut, wenn man sich das erstmal so ein
bisschen genauer anguckt, dann, also was diese Definition
sicherstellt, ist also erstens, wenn wir uns jetzt mal fragen,
für welche Indizes ist denn hier vernünftig was definiert, dann
stellen wir fest, also erstens für den Index 1 ist etwas vernünftig
definiert, also nehmen wir an, die Menge M, das ist die Menge der
Indizes, für die diese Definition von großes kathetisches Produkt
vernünftig definiert ist.
Dann stellen wir fest, für 1 ist das vernünftig definiert, da haben
wir es explizit hingeschrieben.
Und zweitens wissen wir, wenn es für irgendein n vernünftig definiert
ist, dann für n plus 1 auch.
Das hat ja diese zweite Zeile hier sichergestellt.
Wenn es für n vernünftig definiert ist, dann für n plus 1 auch.
Also die Menge der kleinen n, für die das alles eine vernünftige
Definition ist, enthält die 1 und wenn erstmal ein n drin ist, dann n
plus 1 ist auch drin.
Und wir haben natürliche Zahlen einfach so hingenommen, man kann die
auch ordentlich definieren und dann ist Bestandteil der Definition
natürlicher Zahlen das folgende und das ist also im Grunde wirklich
Teil der Definition von natürlichen Zahlen.
Wenn Sie eine Menge haben, da ist 1 drin und Sie wissen, wenn eine
Zahl drin ist, die 1 größere ist auch drin, dann Mathematik sagt
einem, die Menge ist... und wenn Sie wissen, in der Menge sind sowieso
nur positive ganze Zahlen und nicht auch noch Pi oder sonst irgendwas,
dann die Menge enthält schon alle positiven ganzen Zahlen.
Darauf fußt auch vollständige Induktion.
Also die Mathematik stellt einem hier sicher, ja, das darf man
hinschreiben und es ist eine vernünftige Definition für alle n.
Es kommt durchaus vor, dass man mehrfach die gleiche Menge hat, also
kathesisches Produkt, eine Menge mit sich selber, 2 mal, 3 mal, 4 mal,
5 mal und dann schreiben wir einfach für diese Menge nfaches
kathesisches Produkt schreiben wir einfach m hoch n.
Also wenn m eine Menge ist, m hoch n, das sind alle n-Tupel, sagt man
auch, von n Elementen und jedes Standteil aus m.
Das darf mehrfach das gleiche sein, das dürfen verschiedene Elemente
sein, die in so einem n-Tupel drinstehen.
Ganz egal.
So, ja.
So viel zu kathesischem Produkt.
Und bevor wir jetzt damit weitermachen, also wir werden gleich
weitermachen mit kathesischem Produkt.
Und da werden ganz viele Formulierungen sein, wo sowas steht, für
jedes a es gibt ein b oder für kein a es gibt nicht das, also ständig
für jedes a, für jedes b, es gibt ein c, für kein d, bla bla bla.
Und das führt sehr schnell zu sehr langen Formulierungen, die man sich
ersparen möchte.
Da möchte man eine Abkürzung haben.
Mindestens das.
Und das geht so, statt für jedes Element klein x aus groß a gilt
irgendetwas, also statt für jedes Element x aus a gilt, schreiben wir
einfach so ein auf der Spitze stehendes, stilisiertes a, also so um
180 Grad gedreht, rotiert und das lesen wir als für jedes x aus a.
Oder manchmal auch für alle x aus a.
Und als Abkürzung für es gibt ein Element x aus a in der Bedeutung es
gibt mindestens ein, also wenn man da so schreibt es gibt ein, dann
immer erstmal ist gemeint mindestens eins, vielleicht auch viele,
schreiben wir so ein gespiegeltes, stilisiertes e.
Und lesen es als es gibt ein x in a.
Und dieses auf dem Kopf stehende a heißt Alquantor und dieses
gespiegelte e heißt Existenzquantor.
Und so ein bisschen ordentlicher, genauer, allgemeiner gucken wir uns
das in einem Kapitel über sogenannte Prädikatenlogik erster Stufe an.
Vorläufig benutzen wir das einfach so ein bisschen informell als
Abkürzung für diese Formulierungen und wir machen das alles so
harmlos, dass auch kein Unglück passiert.
So, also das umgedrehte a für jedes Element oder für alle Elemente
gilt und das gespiegelte e für es gibt ein.
Und wenn die Menge a sowieso klar ist, dann lassen wir das auch noch
weg und schreiben nur noch hin für jedes x, für jedes y.
Ach so, erst mal, wenn man zweimal für jedes x aus a, für jedes y aus
a, schreibt man manchmal nur noch für jedes x und y an a und wenn das
a klar ist, lässt man das auch noch weg, dann steht da nur noch für
jedes x und y oder vielleicht für jedes x für jedes y.
So, und jetzt noch mal zurück zu Unicode.
Diese Beziehung zwischen Zeichen und Codepoints, eine Relation, das
war ja das Beispiel.
kommen wir also zu sogenannten Relationen.
Also bei Unicode ist es so, dass festgelegt dem großen a ist die Zahl
65 als Codepoint zugeordnet, dem scharfen s die 223, dem griechischen
kleinen alpha 945, diesem n mit Doppelstrich Codepoint 8469, dem
Alquandor, dieses Zeichen ist auch in Unicode, Nummer 8704, dem
kleinen Kreuz für katholisches Produkt Nummer 10799 und, und, und,
und, also Integralzeichen und ich weiß nicht, was Sie sich alles
ausdenken, alles ist in Unicode drin.
Auch Unmengen von Emojis und ich weiß nicht, was nur der Antrag
dengonisch aufzunehmen wurde abgelehnt.
So und also insbesondere zu Unicode gehört also die Spezifikation,
welche Paare hat man da Zeichen und zugehöriger Codepoint.
Das ist also eine Menge von Paaren, so eine Menge groß U von solchen
Paaren, erste Komponente aus dem Unicode Alphabet, katholisches
Produkt mit zweiter Komponente aus nicht negative ganze Zahlen.
Also eine Teilmenge vom katholischen Produkt aller dieser Paare, das
ist so ein Teil der Spezifikation von Unicode und jetzt allgemein,
wenn Sie zwei Mengen A und B haben und eine Teilmenge vom katholischen
Produkt, dann nennt man das eine Relation oder etwas genauer eine
binäre Relation, wenn man deutlich machen will.
Zwei Komponenten, zwei Dinge stehen da in Beziehung.
Also zum Beispiel Groß A, das Paar mit Groß A und 65 ist im Unicode
Alphabet, aber das Paar Groß B und 4711 ist nicht im Unicode Alphabet.
Zu B gehört 66.
So und wenn so ein Paar A, B in der Relation drin ist, also wenn R
Groß R in der Relation ist, so eine Teilmenge von A Kreuz B, dann
lesen wir auch, dass manchmal so als A steht in Relation zu B und man
schreibt dann vielleicht manchmal auch nicht AB aus R, sondern klein A
Groß R klein B.
Wenn Sie zum Beispiel Zahlen haben, Sie schreiben x3 kleiner gleich 5.
Sie schreiben nicht, dass Paar 3, 5 ist in der Relation kleiner
gleich.
So was macht man manchmal auch.
Und so Relationen können gewisse Eigenschaften haben oder halt auch
nicht.
Auf dieser Folie ist jetzt viel Text, aber es wird gleich weniger.
Und erst mal als Beispiel, wie ist das bei der Unicode Relation?
Also zum Beispiel bei Unicode ist halt wirklich für jedes Symbol, das
in dem Unicode Alphabet drin ist, ist ein Code Point festgelegt,
jedenfalls mindestens einer.
Also für jedes A aus dem Alphabet, es gibt ein N aus N0, sodass A den
Code Point N hat.
Allgemein der Relation heißt links total, wenn genau das der Fall ist,
für jedes A aus der ersten Menge Groß A gibt es ein B aus der zweiten
Menge mit der Eigenschaft A, B ist in R.
Und wenn wir jetzt mal die Quantoren anwenden, geht der Text mal weg.
Für jedes A es gibt ein B, A, B ist in R.
Und das ist bei Unicode so.
Für jedes A es gibt ein N, A, N ist in der Relation.
Also was nicht passiert ist, dass Sie in der Menge A ein Element
haben, das zu keinem Element in B in der Relation steht.
Und Relationen kann man halt so darstellen, dass Sie für die Mengen A
und B zwei so kringel hinmalen und dann ein Pfeil von einem Element in
A zu einem Element in B, wenn dieses Paar in der Relation drin ist.
Und wenn es zu jedem A ein B gibt, dann gibt es kein Element in A, von
dem kein Pfeil weggeht.
Das ist das eine.
Links total.
Also von jedem Element geht mindestens ein Pfeil weg sozusagen.
Bei Unicode ist es auch so, es gibt kein Element, das zwei Code Points
hat.
Also für kein A gibt es mehrere verschiedene N mit A, N ist in der
Relation.
Und allgemein, das heißt es gibt nicht ein Element in A, von dem im
Bild mehrere Pfeile weggehen zu verschiedenen Elementen in B.
Und allgemein nennt man eine Relation rechts eindeutig, wenn das
sichergestellt ist.
Für kein A, es gibt B1 und ein B2, die verschieden sind.
Und sowohl A, B1 ist in der Relation als auch A, B2.
Wenn wir da Quantoren benutzen, steht erstmal sowas da.
Es ist nicht so, dass es ein A gibt und ein B1 gibt und ein B2 gibt,
die verschieden sind.
Und A, B1 und A, B2 auch.
Jetzt mit dem nicht davor und so, das ist alles noch ein bisschen
unschön.
Das kann man jetzt auch noch versuchen umzuformulieren.
Also wenn es das nicht gibt, dann ist es offensichtlich für alle genau
anders.
Das heißt für alle A und für alle B1 und für alle B2.
Also wenn A, B1 in Relation steht und A, B2, wenn das nicht der Fall
ist, dann muss B1 gleich B2 sein.
Das ist so eine Möglichkeit, Rechtseindeutigkeit auszudrücken.
So und Relationen, die sowohl linkstotal als auch rechtseindeutig
sind, das heißt von jedem Element in A sozusagen es geht mindestens
ein Pfeil weg und rechtseindeutig von jedem Element geht höchstens ein
Pfeil weg.
Das heißt von jedem Element geht genau ein Pfeil weg.
Solche Dinger nennt man dann Abbildungen oder Funktionen und schreibt
dann halt üblicherweise R-Doppelpunkt groß A Pfeil groß B.
Das haben Sie bestimmt schon mal gesehen.
Und dann, wenn das eine Abbildung ist, das A nennt man den
Definitionsbereich und B den Zielbereich und statt A, B aus R schreibt
man typischerweise R von A gleich B.
Und B heißt Funktionswert von A.
An einer Stelle in der Vorlesung, in einem der letzten Kapitel
brauchen wir ein bisschen was anderes.
Das nennt man üblicherweise partielle Funktionen.
Außer man beschäftigt sich in irgendeinem Gebiet sowieso die ganze
Zeit nur mit partiellen Funktionen und dann ist das Pfeil weg.
Aber wir sagen immer partielle Funktionen.
Da wird nicht verlangt, dass das linkstotal ist, nur rechtseindeutig.
Das heißt, da kann es Elemente in A geben, für die kein Funktionswert
festgelegt ist.
Das ist manchmal auch nützlich.
Und alle diese Begriffe, also man führt sie halt ein, weil sie
nützlich sind, nicht weil man besonders viele Vokabeln lernen will.
So.
Bei Unicode
sinnigerweise verschiedene Zeichen haben auch verschiedene Code
Points.
Allgemein, man nennt eine Relation linkseindeutig.
Gerade hatten wir rechtseindeutig, jetzt sind wir bei linkseindeutig.
Wenn gilt, wenn Sie zwei Paare in der Relation haben, A1, B1 und A2,
B2, wenn A1 und A2 verschieden sind, dann B1 und B2 sind auch
verschieden.
Also nicht zwei Dingen in A wird das gleiche Ding in B.
Die stehen nicht in Relation zu dem gleichen Element in B.
Also es ist verboten, dass Sie im Bildchen zwei Pfeile haben, die an
verschiedenen Stellen starten in A, bei verschiedenen Elementen, aber
beim gleichen landen.
Und eine Abbildung, die linkseindeutig ist, heißt auch Injektiv.
Unicode ist so, ja.
Und eine Abbildung heißt rechtstotal oder eine Relation heißt
rechtstotal, wenn es für jedes B in B ein A in A gibt, sodass A, B in
Relation steht.
Also es passiert Ihnen nicht, dass Sie in B hier so ein Element haben
und da geht kein Pfeil von irgendwo in A hin.
Und eine Abbildung, die rechtstotal ist, heißt auch Surreaktiv.
Und eine Abbildung, die sowohl Injektiv als auch Surreaktiv ist, heißt
B -jektiv.
Das heißt, von jedem Element in A es geht genau ein Pfeil weg, weil es
eine Abbildung ist.
Und weil es B-jektiv ist, in jedem Element in B kommt auch genau ein
Pfeil an.
Salopp gesagt, Sie haben genauso Sie haben genauso Sie haben genauso
viele Funktionswerte jetzt, wenn es endliche Mengen sind.
Sie haben genauso viele Funktionswerte wie Argumente.
Und verschiedene Argumente haben verschiedene Funktionswerte.
Und in der Zielmenge, Sie haben auch nur die Funktionswerte, nicht
noch was anderes.
Und weil das bei endlichen Mengen und das heißt mit anderen Worten,
bei endlichen Mengen, wenn Sie eine Bijektion haben von A in B, wenn
das eine B-jektive Abbildung ist, wenn es endliche Mengen sind, die
sind gleich groß.
Wenn sie endlich sind.
Und weil das so ist, kommt man dann auf die Idee, auch für unendliche
Mengen, nur so am Rande erwähnen, das so zu definieren, wann sind zwei
unendliche Mengen gleich groß?
Ja, wenn es eine B-jektive Abbildung gibt von der einen auf die
andere.
Und dann stellt man fest, manche unendlichen Mengen sind gleich groß
und andere halt nicht.
Also zum Beispiel, die nicht negativen ganzen Zahlen und die Menge
aller ganzen Zahlen, also mit den negativen, die sind gleich groß, da
gibt es eine B-jektive Abbildung.
Aber die Menge der ganzen Zahlen und die Menge der rationalen Zahlen
sind auch noch gleich groß, da gibt es auch eine B-jektive Abbildung.
Aber die Menge der rationalen Zahlen und die Menge der reellen Zahlen,
die sind richtig unterschiedlich groß.
Da gibt es keine B-jektive Abbildung.
Und dass es da keine B-jektive Abbildung gibt, das ist genau diese
Kernidee von Kantor, die wir dann auch benutzen werden, die gleiche
Idee, um zu beweisen, es gibt Probleme, die man nicht mit dem Rechner
lösen kann.
Es gibt nämlich viel mehr Probleme als Programme.
Es gibt keine B-jektive Abbildung.
Zu viele Probleme, zu wenig Programme.
Das ist einfach die Argumentation.
Manchmal muss man Abbildungen definieren und bitte, wenn Sie
Abbildungen definieren, sagen Sie immer, was ist der
Definitionsbereich, was ist der Zielbereich, das ist wichtig.
Das dürfen Sie nicht weglassen und Sie müssen dann eben sagen, für
jedes Element aus dem Definitionsbereich, was ist der Funktionswert?
Wie sagt man das für jedes Element aus dem Definitionsbereich?
Das sind ja vielleicht unendlich viele.
Sie schreiben halt eine unbekannte, eine variable X hin und egal,
welchen konkreten Wert man nimmt, Sie sagen, also jetzt hier auf der
rechten Seite, wenn Sie da das X einsetzen, das ist der Funktionswert.
Und dann schreiben wir also so ein X und dann so ein Pfeil, der am
linken Ende noch so einen kleinen senkrechten Strich hat und rechts
irgendetwas, in dem X vorkommen darf, nicht muss.
Also wenn Sie alle Elemente, jedes X einfach auf 1 abbilden wollen,
dann können Sie rechts einfach hinschreiben, Funktionswert ist 1.
Dann müssen Sie nicht hinschreiben, noch irgendwas mit X.
Und wenn Sie für jedes Paar was festlegen wollen, dann schreiben Sie
eben da das Paar hin, sozusagen mit den beiden Komponenten X und Y und
auf der rechten Seite als Funktionswert irgendwas, wo X und Y drin
vorkommen darf.
Also zum Beispiel sowas hier, Abbildung F von N0 nach N0 und N wird
abgebildet auf und es steht hier etwas, wo N drin vorkommt und wenn es
komplizierter wird, macht man halt eine Fallunterscheidung zum
Beispiel, das ist durchaus legal.
Wenn N gerade ist, wird N abgebildet auf N halbe und wenn N ungerade
ist, wird N abgebildet auf 3N plus 1.
Sie können mal diese Abbildung nehmen und mal ausversuchen, achso,
nehmen Sie 7 oder 21 oder was auch immer, wenden Sie F an, kommt was
raus.
Auf diese Zahl wenden Sie wieder F an, kommt was raus.
Machen Sie das mal eine Zeit lang.
So, und wichtig bei einer Abbildung sind nicht irgendwelche Namen,
also ob die Abbildung F oder G heißt und ob die Variable N oder X
heißt, ist egal, solange der Definitionsbereich gleich ist, solange
der Zielbereich gleich ist und die Abbildungsvorschrift, solange für
jedes Element aus dem Definitionsbereich der gleiche Funktionswert
rauskommt, ist das die gleiche Abbildung.
Und es ist wichtig, Definitions- und Zielbereich zu haben, sonst
können Sie nicht entscheiden, ob eine Abbildung injektiv ist oder
nicht, ob sie surjektiv ist oder nicht.
Nehmen wir mal die reellen Zahlen, also ich schreibe hier jetzt R0
oben plus für die reellen Zahlen, größer gleich null.
Wenn Sie Abbildung nehmen, die X auf X² abbildet und nehmen wir mal
an, Zielbereich sind die nicht negativen reellen Zahlen.
Die Abbildung ist injektiv, wenn Sie sagen, mein Definitionsbereich,
das sind nur die nicht negativen reellen Zahlen.
2 und 7 werden auf unterschiedliche Funktionswerte abgebildet.
Und Sie finden nicht zwei Zahlen größer gleich null verschiedene, die
quadriert das gleiche ergeben.
Aber wenn Sie sagen, mein Definitionsbereich ist ganz R, die negativen
Zahlen sind auch dabei, dann ist es nicht mehr injektiv.
Minus 2 und 2 werden beide auf 4 abgebildet.
Und genauso für die Surjektivität ist wichtig, wie groß ist der
Zielbereich?
Wenn Sie sagen, der ist R0 plus, dann beim Quadrieren jedes Element
kann rauskommen für jede nicht negative reelle Zahl.
Gibt es ein Urbild, nehmen Sie halt die Wurzel.
Aber wenn Sie sagen, der Zielbereich ist ganz R, ist die Abbildung
nicht mehr surjektiv, weil keine Quadratzahl negativ ist.
Also wichtig, immer Definitionsbereich, Zielbereich,
Abbildungsvorschrift.
Und nur wenn alles 3 gleich ist, handelt es sich um die gleiche
Abbildung.
So, und noch so ein kleines bisschen Notation.
Wenn wir eine Abbildung haben von A nach B und wir haben eine
Teilmenge des Definitionsbereiches, dann schreiben wir manchmal
einfach f von dieser Teilmenge.
Also eigentlich kann ich ja kleinen f nur auf Funktionswerte anwenden
erstmal.
Und jetzt definiere ich noch, was f von einer Teilmenge von
Funktionswerten sein soll.
Nämlich die Menge aller b aus b, die als Funktionswert für ein a aus
der Teilmenge auftreten.
Oder etwas salopper gesagt, das ist die Menge aller f von a äh mit der
Eigenschaft, a ist in der Teilmenge.
Ja.
Das ist einfach manchmal nützlich.
Ja.
Und dann machen wir an dieser Stelle für heute Schluss.
Sie sehen, es bleiben noch 5 Folien übrig.
So ein kleines bisschen was.
Und dann in der Hauptsache, das nächste Mal kümmern wir uns um Wörter.
Dankeschön.