Präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, dann möchte ich Sie alle herzlich zur heutigen Vorlesung begrüßen. Schönen guten Morgen wünschen.

Wir stehen am Ende von Kapitel 4 und steigen Kapitel 5 ein.

Also, und beim Kapitel 5 dreht es sich um Beweisprinzipien.

Also es geht jetzt ein Kapitel lang nicht darum, neue Mathematik einzuführen, sondern Ihnen einfach so ein bisschen zu zeigen, was es für Möglichkeiten gibt, Sätze zu beweisen. Ich werde Ihnen so 3, 4 Standardbeweisverfahren zeigen, jeweils mit einem Beispiel.

Sie haben sicher schon gesehen und wir haben auch schon einiges gemacht, in der Mathematik wird viel bewiesen. Im Prinzip geht es nur darum. Und was ist ein Beweis? Mit einem Beweis versucht man irgendwie den Wahrheitsgehalt einer Aussage zu zeigen.

Und da man nie irgendwas aus dem luftleeren Raum schöpfen kann, haben Sie immer irgendwelche Voraussetzungen. Also die Aussagen, die Sie zeigen in einem Beweis sind immer von der Form, wenn irgendwas gilt, dann gilt was anderes. Sie haben immer, wenn die Voraussetzungen erfüllt sind, dann gilt die Aussage des Satzes.

Weil ganz ohne Voraussetzung gilt auch nichts. Es kann sein, dass in dem Satz keine Voraussetzung drin steht, weil die irgendwie implizit woanders versteckt ist. Aber zumindest die Voraussetzungen, es gibt Zahlen, mit denen kann man rechnen oder sowas steckt hinter allem.

Jetzt können Sie sagen, jetzt argumentiere ich es sozusagen, jeder Beweis, den man führt, ist der Nachweis, dass eine Implikation wahr ist. Also dass irgendwas aus der Voraussetzung A folgt, die Behauptung B stimmt. Jetzt können Sie sagen, das stimmt nicht ganz, weil es gibt ja auch Äquivalenzen. Es gibt ja auch den Fall, dass man zeigen will, zwei Aussagen sind äquivalent.

Dann sage ich klar, das gibt es auch, nur eine Äquivalenz ist auch nichts anderes als zwei Implikationen. Also wenn Sie zeigen wollen, sollen zwei Aussagen, sind äquivalent, A genau, dann wäre B. Dann können Sie das auseinanderpflücken, das macht man meistens auch in 90% der Fälle, indem

man sagt, wir zeigen zuerst aus A folgt B und wir zeigen aus B folgt A. Und dann hat man A äquivalent B. Insofern können wir uns darum drücken und die Aufgabe, um die es beim Beweisen geht, wirklich auf die Implikation reduzieren. Die Aufgabe ist immer folgere, aus einer Aussage A, das ist das, was man üblicherweise die Voraussetzung nennt.

Und das kann sehr viel sein oder auch sehr wenig. Eine Aussage B, die Aussage B und diese Aussage B ist das, was normalerweise Behauptung heißt.

So, das ist die Aufgabe beim Beweisen. Sie haben irgendwelche Voraussetzungen und Sie sollen irgendwas daraus folgern. Und im Wesentlichen gibt es jetzt zwei, drei, vier Herangehensweisen, die man immer nimmt.

Wir fangen mit der naheliegendsten an, das ist der sogenannte direkte Beweis. Und da macht man genau das, was man soll. Das sieht also folgendermaßen aus.

Man hat die Voraussetzung, die Aussage A. Und was ich Ihnen jetzt hier hinschreibe, ist sozusagen eine Blaupause, wie so ein Beweis aussieht. Also auch wenn Sie einen Beweis aufschreiben wollen, tut es der Nachvollziehbarkeit des Geschriebenen und auch Ihrer eigenen Strukturierung des Denkens gut,

wenn Sie sich erst noch mal genau hinschreiben, was sind eigentlich meine Voraussetzungen? Was habe ich gegeben, was weiß ich, wovon soll ich starten? Erst wenn man das richtig klar gemacht hat, sollte man loslegen, weil man sonst loslegt und gar nicht so richtig weiß, wo man eigentlich steht. Also würde ich Ihnen raten, zumindest für die ersten 15 Beweise, die Sie aufschreiben, halten Sie so ein bisschen da dran,

erst mal die Voraussetzung hinzuschreiben, also so wie es hier steht, Voraussetzung, und dann dahinter alles sammeln, was man hat. Dann schreiben Sie drunter das Wort Behauptung und machen sich noch mal genau klar, was soll ich eigentlich, wo will ich hin? Loslaufen ist immer einfacher, wenn man weiß, wo man hin will.

Dahinter steht jetzt eben die Behauptung, das ist jetzt im abstrakten Fall die Aussage B, das ist je nach Aufgabenstellung halt irgendwas, was Sie zeigen sollen. Tut, und dann kommt der Beweis, bitte den Beginn des Beweises kenntlich machen, üblicherweise mit dem Wort Beweis oder Sie dürfen auch schreiben, hier beginnt der Beweis oder irgendwas,

aber für jemanden, der das dann hinterher nachvollziehen oder lesen will oder korrigieren will, ist das sehr gut zu wissen, bis wohin ist die Voraussetzung und bis wohin ist die Behauptung und wo fängt der Beweis an. Und das gilt nicht nur für den Korrektor, sondern denken Sie auch daran, dass es Ihnen passieren kann, dass Sie irgendwelche Aufgaben bearbeiten, in einen Ordner heften und dann ein Jahr später für irgendeine Klausurverbereitung oder was, die wieder rausziehen,

und dann müssen Sie das auch selber noch verstehen. Auch das ist, wenn man es nicht gut strukturiert, manchmal schwierig. So, was macht man jetzt im Beweis? Na ja, man weiß, dass A gilt und will B. Also der Beweis könnte anfangen mit sei A erfüllt, dann gilt irgendwas und dann gilt noch was anderes und deswegen gilt und so weiter.

Und am Schluss muss dann stehen, also gilt B. So einen Beweis haben Sie sicher schon ein paar Mal geführt, das ist der sogenannte direkte Beweis. Ich hatte hier in der Vorlesung auch schon welche von der Sorte.

Also wenn Sie nochmal zurückblättern, der Beweis von Satz 312 A Teil und C Teil waren solche direkten Beweise. Der Beweis von Satz 2.5 waren direkter.

Also wir hatten schon einige. Ich mache Ihnen trotzdem noch ein Beispiel. Ich habe nochmal hier auf Folie das Beweisprinzip nochmal aufgeschrieben.

Auch der untere Hörsaal kann jetzt mal den Overhead anschmeißen, da liegt die Folie schon drauf. Also das ist der Kasten, den ich hier gerade hingeschrieben habe. So ein, noch ein einfaches Beispiel für einen direkten Beweis. Beispiel 5.1.

Also was ich Ihnen zeigen will ist, wenn Sie zwei gerade Zahlen haben, zwei gerade natürliche Zahlen, dann ist auch deren Summe gerade.

Wenn Sie mir sofort glauben, es geht jetzt auch nicht darum irgendwas total Überraschendes Ihnen hier vorzuführen, sondern eben wenn man das Prinzip sehen will, lohnt es sich irgendwas Banales zu nehmen, dass man sich auf das Beweisprinzip konzentrieren kann.

Also wie würde man das beweisen? Und häufig sind es gerade diese Banalitäten, die einem viel zu klar sind, und man sich schwer tut, die zu beweisen, weil man irgendwie nicht weiß, wie soll man das hinschreiben, ist doch offensichtlich. Also was wissen wir? Wir gehen von dem aus, was wir wissen. Wir müssen von der Voraussetzung zur Behauptung.

Also Sie wissen, N und M ist gerade. Was bedeutet denn, dass das eine Zahl gerade ist? Das bedeutet, Sie können ganzzeitig durch zwei teilen, also es gibt natürliche Zahlen L und K, so dass Sie das N schreiben können als zwei mal L und das M schreiben können als zwei mal K.

Und L und K sind immer noch natürliche Zahlen. So, wenn Sie das haben, dann können Sie jetzt N plus M anschauen. Das ist das, was uns interessiert. Man muss gucken, wo kommt man her, wo will man hin?

Jetzt haben wir das, wo wir herkommen, ausgeschlachtet. Jetzt müssen wir langsam mal den Kopf heben und zum Horizont gucken, wo wollen wir eigentlich hinlaufen? Wir wollen dahin laufen, wir wollen zeigen, dass N plus M gerade ist. Also lohnt es sich mal anzuschauen, was ist denn jetzt N plus M?

Also was ist N plus M? Wir wissen, unser M, N ist zwei mal L und unser M ist zwei mal K. Also haben wir, dass N plus M zwei L plus zwei K ist. Das ist dasselbe wie zwei mal L plus K. So, jetzt ist diese Zahl L plus K, die nenne ich mal P.

Das ist immer noch eine natürliche Zahl, weil L und K natürliche Zahlen waren. Und wenn man natürliche Zahlen addiert, kommen natürliche Zahlen raus. Also haben wir, dass N plus M zwei mal P ist.

Und das bedeutet gerade, dass N plus M gerade ist. Das ist jetzt ein kurzer, banaler Beweis, der nicht dazu dient, dass wir was Tolles gezeigt haben, sondern dass Sie das Prinzip sehen. Und das Vorgehen beim direkten Beweis ist immer das.

Sie schreiben Sie mir hin, was Sie haben. Sie formulieren das mal. Meistens gibt es dann so eine Phase, wo man das, was man hat, naheliegend umformt. Und dann guckt man, wo man hin will und schaut, wie man dahin kommt. Und da fängt die Kreativität an und das Irrgartenlaufen.

Also die Frage ist, ob man immer wie hier versucht, L und K zu einer Variante P zusammenzufassen. Die Antwort ist nicht unbedingt. Die Antwort ist, Sie müssen es so machen, dass es, oder das Ziel ist es so zu machen, dass es am leichtesten nachvollziehbar ist.

Und das ist keine objektives Kriterium, sondern ein subjektives. Ich habe es jetzt hier versucht, möglichst sehr ausführlich zu machen. Sowas würde ich natürlich in drei Wochen in eine Zeile schreiben. Natürlich könnte man auch von oben sagen, jetzt sieht man N plus M ist zweimal eine natürliche Zahl und damit ist das gerade.

Die Frage, wie genau man es macht, ist keine objektive. So genau, dass es für jeden mit gleichem Wissensstand absolut nachvollziehbar und nicht mehr hinterfragt weiß. Es kommt eben darauf an, für wen man es, wer die Zielgruppe des Beweises ist.

Und hier ist jetzt relativ offensichtlich, was passiert, ein Beweis kann länger sein.

Und frusten Sie sich nicht, wenn Sie in diesem Irrgarten, wie komme ich zu meinem Ziel, fünfmal falsch abbiegen. Das ist normal. Also man ist in den ersten Semestern immer frustriert, weil um zwei Seiten Übungsblatt abzugeben, schmiert man zehn Zettel Schmierpapier voll. Oder manchmal ist das Verhältnis noch krasser. Wenn Sie es schon erlebt haben bei Ihrem ersten Übungsblatt und dann denkt man, das ist

nervig und das wird aber hoffentlich besser und ich kann Ihnen sagen, es wird nicht besser. Also auch ich, wenn ich jetzt forsche, arbeite 90 Prozent für die Mülltonne. Das ist so. Dafür sind die Beweiswege, die Irrgarten, in denen man irrt, um den Beweis zu finden, zu groß und zu undurchsichtig, man muss einfach mal loslaufen.

Trauen Sie sich loszulaufen und wenn Sie in einen Irrgang kommen und in der Stadtgasse stecken, laufen Sie wieder zurück. Und probieren einen anderen Weg. Das geht gar nicht anders. Und glauben Sie mir, von diesen ganzen Irrläufen lernt man unglaublich viel. Weil man nämlich das nächste Mal, zumindest das übernächste Mal, nicht mehr in die Falle tappt.

Also wenn Sie in einem Beweis feststecken, was oft vorkommt, was auch mir immer noch ständig passiert, machen Sie mal was, was geht und gucken, ob es für was führt. Und wenn es zunächst führt, müssen Sie was Neues ausdenken. Aber das ist der Teil, weshalb Mathematiker ob ihre Frusttoleranz geschätzt werden.

Und bei Ihnen wird das nicht anders sein. Gut, ich will Ihnen dann nur, das soll nicht dazu dienen, Ihnen Angst einzujagen, sondern um Ihnen klar zu machen, wenn Sie jetzt lang hängen und viel Schmierpapier für die Mülltonne produzieren, ist das normal. Vollkommen normal. Gut, das war der direkte Beweis, werden Sie auch schon ein paar Mal gemacht haben.

Ich hatte in den ersten Vorlesungen, ich habe es auch schon ein, zwei Mal verwendet, auch schon mal den Begriff Beweis durch Kontraposition erwähnt. Das hatten wir am Anfang beim Thema Aussagen gesehen. Die Aussage A impliziert B, ist äquivalent zur Aussage nicht B impliziert nicht A.

Und das kann man sich eben zum Nutzen machen, wie wir es auch schon gemacht haben, für den Beweis durch Kontraposition. Das Setting ist das gleiche, Sie haben irgendeine Voraussetzung. Aussage A, also im Beispiel oben, N und M sind natürliche Zahlen.

Sie haben eine Behauptung. Aussage B. Und Sie wollen wieder zeigen, aus A folgt B. Und das machen Sie jetzt eben nicht, indem Sie mit A anfangen und zeigen, daraus folgt B. Sondern indem Sie mit nicht B anfangen und zeigen, daraus folgt nicht A.

Also der Beweis geht los, es gelte nicht B. Also die Aussage B ist falsch. Dann muss man erst mal sich überlegen, was das Negative von B ist. Aber wenn man das hat, dann kann man von da loslaufen und sagen, dann gilt irgendwas und dann gilt noch was. Und dann kommt wieder der kreative Prozess.

Und am Ende steht dann, also gilt irgendwas, und also ist dann am Ende A falsch. Wenn Sie das haben, haben Sie den direkten Beweis, aus nicht B folgt nicht A. Und ein Beweis, aus nicht B folgt nicht A, liefert automatisch ein, aus A folgt B.

Das hatte ich damals, die abstrakte Bemerkung dazu, dass die beiden Aussagen, A folgt B und nicht B folgt nicht A, äquivalent sind, war die Bemerkung 1.6. Und ein Beispiel für so einen Beweis durch Kontraposition hatten wir in der letzten Vorlesung, Satz 3.12b.

Den hatte ich Ihnen per Kontraposition gezeigt. Ich mache jetzt noch ein zweites Beispiel. Das ist Beispiel 5.2. Geht wieder um gerade und ungerade.

Das ist jetzt schon ein bisschen weniger banal als das oben. Wir nehmen uns eine natürliche Zahl her, von der wir wissen, ihr Quadrat ist gerade. Und dann ist meine Behauptung, wenn Sie eine Zahl haben, deren Quadrat gerade ist, dann war schon die Zahl selbst gerade.

So, wie zeigen wir das? Wie gesagt, Kontraposition. Wir zeigen nicht, aus A folgt B, also wir zeigen nicht, wenn n Quadrat gerade ist, ist n gerade, sondern wir zeigen, aus nicht B folgt nicht A.

Also wir zeigen, wenn n ungerade ist, dann ist auch n Quadrat ungerade. Das ist die Kontraposition hier. Also man fängt an mit sei nicht B, also sei n ungerade.

Was heißt das? Das heißt, es gibt eine natürliche Zahl k, so dass Sie das n schreiben können als 2 mal k plus 1. Eine ungerade Zahl ist immer 1 mehr als eine gerade. So, was heißt das? Das heißt, es gibt ein k aus n, sodass n 2k plus 1 ist.

Was uns interessiert ist, nicht n, sondern was uns interessiert ist, wie sieht das mit n Quadrat aus? Also was ist mit n Quadrat? Wenn n 2k plus 1 ist länger, dann ist n Quadrat 2k plus 1 Quadrat. Jetzt kommt binomische Formel.

Erinnern Sie sich hoffentlich alle dran, 4k Quadrat plus 4k plus 1. Jetzt kommt ein verdammt bekloppter Seitenumbruch. Also ich schreibe gerade nochmal hin, wir haben also n Quadrat, also die Zeile von gerade eben, es gibt ein k aus n, so das n Quadrat ist 4k Quadrat plus 4k plus 1.

So, es geht uns darum zu zeigen, das Ding ist ungerade. Also versuchen wir es in die Form zu bringen, 2 mal irgendwas plus 1. Klammern wir mal eine 2 aus, bleiben 2k Quadrat plus 2k übrig plus 1.

So, wenn Sie das jetzt hier l nennen, dann ist das eine natürliche Zahl. Dann ist das hier 2l plus 1 und damit ist n Quadrat auch ungerade. Also ist n Quadrat ungerade und was haben wir gezeigt?

Wir haben gezeigt, wenn n Quadrat gerade ist, ist n Quadrat ungerade. Kontraposition, wenn n Quadrat gerade ist, ist n Gerade. Das ist ein Beispiel für einen Beweis durch Kontraposition. Und jetzt kommt natürlich die Frage, wenn ich jetzt irgendeine Aussage habe,

was ist das Richtige, der Direkte oder der Kontrapositionsbeweis? Jeder Beweis, der funktioniert, ist der Richtige. Es ist halt mal der eine einfacher und mal der andere einfacher. Und welcher der Einfachere ist, weiß man halt leider nicht vorher. Man kann natürlich Erfahrungswerte sammeln.

Also wenn Sie einfach 30 Beweise gemacht haben, dann kommt so der Moment, wo Sie sagen, das probiere ich erst gar nicht direkt, das probiere ich mal über Kontraposition. Das sieht leicht aus. Aber das ist Erfahrungswissen. So, das ist Kontraposition. Ach so, die stand hier auch auf der Folie, aber gut.

Jetzt kommt ein drittes Verfahren und da ist jetzt die Frage, man könnte das Verfahren 2b nennen, weil es ist eine Variante der Kontraposition. Aber eine, die oft, die sich lohnt, sich nochmal extra herzunehmen,

weil sie in häufigen Fällen leichter ist als die Kontraposition und Beweise ermöglicht, die direkt manchmal sehr, sehr schwer werden. Und das ist der sogenannte Beweis durch Widerspruch.

Und der sieht folgendermaßen aus. Ich schreibe Ihnen wieder sozusagen so ein Gerüst hin, das dann zu füllen ist. Also Sie haben wie bei jedem Beweis, ich meine bei jedem Satz, das ist immer das Gleiche. Sie haben eine Voraussetzung, das ist die Aussage A.

Sie haben eine Behauptung, das ist die Aussage B. So, und jetzt geht der Beweis los. Wie gesagt, das, was ich hier unterstreiche, sollte irgendwie auch so als Keyword, als Landmarke in jedem ihrer Beweise auftauchen.

Gut, der Beweis durch Widerspruch fängt eigentlich so an wie ein direkter Beweis. Also wir setzen voraus, dass A gilt. Und jetzt kommt der Clou, weshalb das Beweis durch Widerspruch heißt.

Jetzt nehmen wir mal an, dieses Wort ist so ein Keyword, das darauf hinweist, Beweis durch Widerspruch. Annahme, die Aussage B ist falsch. Also Sie setzen voraus, A gilt, und B ist falsch. Das darf jetzt natürlich nicht gehen, weil wir ja zeigen wollen, wenn A gilt, gilt auch B.

Also wenn Sie jetzt voraussetzen, A gilt, und Sie setzen voraus, B ist falsch, dann muss ungeheuerliche Dinge passieren, weil das ist ja genau das, was nicht sein darf. Und genau das muss auch rauskommen, es darf nicht sein. Also was man jetzt macht ist, man geht von diesen beiden Annahmen aus,

also das A gilt und das B falsch ist. Und dann fängt man wieder, jetzt kommt wieder der kreative Teil, also dann fängt man an zu argumentieren. Wenn A gilt und B falsch ist, dann gilt und dann gilt also. Und dann muss am Schluss ein Widerspruch rauskommen.

Und dann kommt, also damit ergibt sich ein Widerspruch. Was ist ein Widerspruch? Zum Beispiel sowas wie 0 gleich 1. Also meistens ist es dann im Zusammenhang, ich zeige Ihnen auch gleich ein Beispiel, wenn Sie sehen, wenn der Beweis sinnig sein soll und tatsächlich die Aussage gilt,

dann ist eben A folgt B. Und wenn Sie jetzt annehmen, A ist richtig und B ist falsch, dann müssen Sie irgendwie zu einer Situation kommen, in der die Kausalität des Universums aus den Fugen bricht und in dem Moment haben Sie Ihren Widerspruch. So, was heißt dieser Widerspruch also?

Dieser Widerspruch kam eben daher, dass anscheinend A richtig und B falsch nicht zusammenpasst. A richtig ist aber gegeben per Gesetz, weil das die Voraussetzung ist, also muss die Annahme falsch gewesen sein und damit ist B richtig.

Das ist die Idee vom Widerspruchsbeweis. Und er ist insofern ein Ticken schöner als die Kontraposition, weil Sie mehr in der Hand haben. Bei der Kontraposition argumentieren Sie von nicht B aus und wollen nach nicht A

und beim Beweis durch Widerspruch haben Sie nicht B und A. Also wissen Sie, dass A gilt oder Sie nehmen an, dass nicht B gilt. Damit haben Sie einfach mehr Material, mit dem Sie arbeiten können und müssen dann halt irgendwie zu einem Widerspruch kommen. Das Prinzip vom Beweis durch Widerspruch auch auf Folie. Der Saal unten kann zur nächsten Folie greifen.

Also das, was ich gerade hingeschrieben habe, das ist die Blaupause für den Beweis durch Widerspruch. So, und ich habe Ihnen auch wieder ein Beispiel dafür mitgebracht. Und das Beispiel ist sozusagen der Klassiker unter den Aussagen, die man durch Widerspruch beweist.

Und insofern auch typisch, als es einer ist, wenn Sie versuchen, den direkt zu beweisen, da beißen Sie wirklich auf Granit. Das geht, aber das ist äußerst mühsam.

Und indirekt und per Widerspruch ist es ein wirklich schöner, nicht allzu langer Beweis. Was ich Ihnen zeigen will, ist die Katastrophe der Pythagorea, nämlich Wurzel 2, ist nicht rational.

Die Pythagorea, ich weiß nicht, wen das was sagt, das Pythagoras sagt jedem was. Ich glaube, die Pythagorea, eine Gruppe, die sich eben um ihn schartet, würde sagen in der Geschichte,

die bisher einzige wirkliche Mathematiksekte, kann man nicht anders sagen, die haben die Mathematik zum Glauben erhoben und insbesondere war ihr Grundglaubenssatz, alles ist Zahl. Und Zahlen waren für die Griechen ganze Zahlen. Wenn man ganze Zahlen hat, hat man auch Brüche. Schon klar, es sind Zahlen und Brüche, aber für die Griechen war klar, es gibt nur rationale Zahlen.

Und Pythagoras war geradezu begeistert davon, dass das ganze Universum sich durch Zahlen erklären lässt, hat begeistert festgestellt, dass schön klingende und schlecht klingende Intervalle in der Musik daherkommen, dass das kleine oder große Zahlverhältnisse der Seitenlängen sind und war also ganz begeistert.

Und das Problem ist, dass sie so viel Mathematik betrieben haben, dass sie ihren eigenen Glauben zerstört haben. Das ist auch nicht so oft passiert, aber es ist die einzige Glaubensgemeinschaft, die einen Widerspruch zu sich selbst brachte, weil sie nämlich irgendwann beim Geometrie machen feststellten, es gibt Zahlen, die sind nicht durch Brüche darstellbar.

Das gab eine kleine Krise dann. Und das ist hier jetzt die Pythagorealische Krise. So, also die Behauptung ist, Wurzel 2 ist nicht rational. Wie beweisen wir das?

Bevor ich anfange einen Kommentar, Sie sehen, hier fehlt schon die Zeile Voraussetzung, die ich eigentlich angemahnt habe. Was ist denn jetzt hier die Voraussetzung? Die Voraussetzung ist überhaupt erst mal, was ist denn Wurzel 2? Haben wir noch nicht definiert. Ich vertraue an der Stelle auf Ihr Schulwissen, dass Sie wissen, was Wurzel 2 ist.

Das definieren wir irgendwann nach Weihnachten. Dann sind Voraussetzungen hier alle Rechenregeln und das Rechnen in rationalen Zahlen und so weiter. Also das sind alles Voraussetzungen, die man überhaupt nicht mehr hinschreibt, aber die klar sein müssen, dass die implizit da sind. So, also wir wollen Wurzel 2 ist nicht rational per Widerspruch beweisen.

Also ein Widerspruchsbeweis fängt üblicherweise an mit dem Wort Annahme. Und wir nehmen eben an, die Behauptung ist falsch, also wir nehmen an, Wurzel 2 ist rational. Und der Vorteil davon, und das ist der Grund, warum der Widerspruchsbeweis an der Stelle einfacher ist,

die Aussage irgendwas ist rational, die können Sie gut in was Brauchbares umsetzen, nämlich das Ding ist ein Bruch. Wohingegen die Aussage irgendwas ist irrational, irgendwas folgt da draus. Das Ding ist kein Bruch. Und wie machen Sie jetzt weiter? Aber das Ding ist ein Bruch, dann haben Sie was in der Hand. Weil was heißt das? Was heißt das, das Ding ist ein Bruch?

Das heißt, es gibt zwei natürliche Zahlen, n und m, sodass Sie Wurzel 2 schreiben können, als den Quotienten von n und m. Und dann will ich gleich jetzt hier voraussetzen, dass Sie das n und m nicht irgendwie wählen, sondern dass Sie es geschickt wählen, nämlich dass Sie es maximal kürzen. Sie wissen, dass man jeden Bruch kürzen kann

und irgendwann geht es nicht mehr. Und das sollen Sie bitte machen. Also wenn Wurzel 2 rational ist, dann suchen Sie sich die Bruchdarstellung und kürzen die so lang wie es geht. So, und diese zwei Zahlen n und m. So, und dann wollen wir mal sehen, dass das nicht geht.

Also, Wurzel 2 ist n durch m. Was ist dann 2? Naja, 2 ist, das ist genau die Definition der Wurzel, das Quadrat von Wurzel 2, also n² durch m². Und das stellen wir jetzt um. Dann ist n² gleich 2m². Man beachtet, das m ist natürlich nicht 0, sonst ist das kein vernünftiger Bruch.

Also kann ich mit m² multiplizieren, also m² ist dann auch nicht 0, dann kann ich mit m² multiplizieren. Und dann kriege ich n² ist 2m². Okay, diese Erkenntnis merken wir uns mal.

Gehen wir in die Sternen. Außerdem liefert die uns noch was, die liefert uns nämlich, dass n² gerade ist. Na warum? Naja, weil n² ist 2m², m² ist natürliche Zahl, 2fache von einer natürlichen Zahl ist gerade. So, jetzt haben wir vorhin geschickterweise vorgearbeitet. Im Beispiel 5.2 habe ich Ihnen gezeigt,

wenn n² gerade ist, dann ist auch n² gerade. Das war der Kontrapositionsbeweis. Also, wenn n² gerade ist, gibt es jetzt wiederum ein k aus n, sodass Sie das n schreiben können als 2 mal k.

Das heißt, genau gerade sein. So, jetzt kommt wieder unser Stern. Wenn das n² mal k ist, dann ist n², also 2m², gleich 2m². Das ist das Stern.

Also haben wir insbesondere, dass 4k² gleich 2m² ist. Und das bedeutet, 2k² ist m². Also, das Quadrat ausgeführt und noch eine 2 gekürzt aus der Gleichung.

Also, 2k² ist m². Was bedeutet das? Und jetzt schließt sich die Schlinge um Pythagoras Hals. Das bedeutet, m² ist gerade. Aber wenn wir eine Zahl haben, die ein Quadrat gerade ist, gerade schon mal verwendet, dann ist die Zahl selbst gerade. Also ist auch m² gerade. So, und jetzt haben wir ein Problem.

Vielleicht sehen Sie es noch nicht, aber wir haben ein Problem, weil wir haben gesagt, Wurzel 2 ist ein Bruch. Diesen Bruch kürzen wir maximal. Jetzt haben wir gesehen, wenn Sie Wurzel 2 durch einen maximal gekürzten Bruch darstellen, dann sind Zähler und Länder des Bruchs gerade. Das heißt, wir haben beim Kürzen nicht aufgepasst.

Na gut, kürzen wir die zwei noch raus. Dann können Sie das Argument gerade noch mal machen. Dann sind n und m wieder gerade, also die neuen n und m. Das können Sie jetzt so lange machen, wie Sie wollen. Das tut nicht. Das ist ein Widerspruch dazu, dass n und m, n durch m, maximal gekürzt ist.

Und damit war die Annahme falsch und die Aussage und die Behauptung ist richtig. Das heißt, Wurzel 2 ist nicht rational.

Also was Sie hier zeigen ist, wenn das Ding ein Bruch ist, dann ist jeder Bruch, der Wurzel 2 darstellt, noch durch zwei kürzbar. Und das ist Käse. Sie können nicht einen Bruch beliebig lange kürzen.

So, das ist so ein klassischer Widerspruchsbeweis und wie gesagt, der ist deswegen deutlich einfacher als der direkte, weil sie aus der Aussage Wurzel 2 ist irrational, aus der können Sie eigentlich nichts rausziehen.

Was bedeutet das? Es ist kein Bruch. Aber wenn Sie es umdrehen, wenn Sie die Annahme machen, es ist ein Bruch, dann haben Sie die n und die m, mit denen Sie rechnen können. Deswegen ist an der Stelle der indirekte Beweis, der Beweis durch Widerspruch deutlich einfacher. Das als Beispiel dazu. Und jetzt kommt noch ein viertes Beweisverfahren.

Warum? N² könnte ja 2 sein und M1.

Das geht natürlich nicht, da stecken Sie jetzt rein schon, dass die Wurzel 2 nicht rational ist.

Das N²2 und M²1 wäre eine Möglichkeit, aber es könnte ja die nicht gehen, weil Sie keine natürliche Zahl finden, die 2 ist. Aber es könnte ja eine mit ganz großen Ns und Ms geben.

Es ist übrigens interessant, sich den Beweis nochmal anzuschauen. Probieren Sie den Malstab mit 2 und mit 4. Mit 4 darf er nicht tun, weil die Wurzel von 4 ist rational. Also probieren Sie den mal mit 4 und schauen, an welcher Stelle es schief geht.

Oder probieren Sie ihn mal mit 5 und schauen, dass es auch geht. Und dann probieren Sie ihn mal mit 4 und schauen, warum es nicht geht. Gut. Jetzt kommt als nächstes das Beweisverfahren der vollständigen Induktion. Das ist ein bisschen anders, als was ich Ihnen bisher gezeigt habe.

Weil, was ich Ihnen bisher gezeigt habe, sind Beweisverfahren, die Sie im Prinzip auf jede Behauptung drauf werfen können. Und was jetzt kommt, die vollständige Induktion ist ein Beweisverfahren, das nur für ganz spezielle Behauptungen funktioniert, aber da ein absolut Schlagendes ist.

Und ich mache die vollständige Induktion nicht im allgemeinen Fall, sondern nur über natürliche Zahlen. In allgemeineren Konstrukten, vielleicht ganz am Ende der Matte 2 und allerspätestens in den formalen Grundlagen.

Wer hat denn die vollständige Induktion schon mal gesehen? Einfach so für das Stimmungsbild. Ich kann nicht drüber bügeln, ich werde es für alle anderen machen, aber die, die es kennen, haben jetzt mal kurz 10 Minuten.

Ein bisschen Ruhe. Also, wie bei jedem Satz, den wir zeigen wollen, haben wir eine Voraussetzung, das ist wieder irgendeine Aussage A, und wir haben eine Behauptung. Und die Behauptung muss, damit Sie das per vollständiger Induktion behandeln können,

eine Behauptung von der Sorte sein, für alle natürlichen Zahlen, gilt irgendwas. Also, die ist von der Form, für alle N aus N, gilt irgendeine Aussage Form E von N.

Also, E von N ist eine Aussageform, und wann immer Sie eine Aussage haben von der Form, irgendwas gilt für alle N aus N, dann sage ich jetzt Ihnen nicht, dass dann immer Induktion das richtige Mittel ist, aber es ist zumindest was, was Sie in die Erwägung einbeziehen sollen, weil es sollten, weil es dann häufig ein gutes Mittel ist.

Und wie sieht eine Induktion aus? Die Idee der Induktion ist die folgende, und die lässt sich am besten, bevor ich jetzt irgendwelchen Formelsalat hinschreibe, am besten an einer Domino-Schlange verdeutlichen. Die natürlichen Zahlen haben die schöne Eigenschaft, dass sie schön sortiert

hintereinander stehen, eine hinter der nächsten und schön diskret einzelne Werte sind. Und was man jetzt macht, ist folgendes, man zeigt bei der Induktion, die Aussage gilt für N gleich Null. Damit hat man Null Prozent des Problems gelöst, weil man muss jetzt für alle natürlichen Zahlen zeigen, jetzt hat man schon mal eine, fehlen nur noch unendlich viele.

Aber immerhin hat man die erste, und das ist ein ganz wichtiger Punkt. Und was man dann noch zeigt, ist jetzt nicht mehr, also jetzt könnte man natürlich für eins weitermachen und für zwei und für drei und für vier, und dann ist man ziemlich lang beschäftigt. Aber was man jetzt noch zeigt, ist nur noch eine einzige Sache, nämlich wenn es für irgendeine

Zahl N gilt, dann gilt es auch für die nächste, dann gilt es auch für N plus eins. Das ist das, was Sie zeigen müssen zeigen, es gilt für Null, und wenn es für N gilt, gilt es für N plus eins. Und damit sind Sie fertig, weil wenn es für Null gilt, gilt es nach dem zweiten, was Sie gezeigt haben, auch für eins.

Damit gilt es für eins, also gilt es für zwei. Damit gilt es für zwei, also gilt es für drei, also gilt es für vier, also gilt es für alle. Das ist die Idee der Induktion, und am besten stellt man sich das über die Dominoschlange vor. Was müssen Sie zeigen, damit die ganze Dominoschlange umkippt? Sie müssen erstens zeigen, der erste Stein fällt um, weil wenn niemand

die Dominoschlange ankippt und es keine Erdbeben gibt, dann fällt die nicht um. Das ist der Induktionsanfang, das heißt N gleich Null funktioniert, das heißt jemand stupst den ersten Stein an. Und dann müssen Sie zeigen, dass die Leute die Dominoschlange hingestellt haben, und das ist eine verdammt lange Dominoschlange, weil die hat unendlich viele Dominosteine, dass die nicht gepfuscht haben.

Soll heißen, jeder Dominostein steht schön hinter seinem Vorgänger und nicht irgendwo anders, also das Ding geht nicht so und dann irgendwo anders weiter. Und das ist der Induktionsschluss, das ist diese Aussage, wenn der Nte fällt, fällt auch der N plus Erste. Sie müssen für jeden Stein zeigen, wenn er fällt, schmeißt er den Nächsten um. Und wenn Sie das haben, der Erste fällt und jeder schmeißt seinen Nachfolger um, dann fällt die ganze Reihe.

So, jetzt war da eine Frage. Ja, das ist das, was ich vorhin meinte, also die Frage ist, ob die Induktion auch über andere Zahlmengen geht. Ja, wenn es kein kleines Element gibt, dann ist das mit der Induktion wieder schwierig.

Ja, also, aber da gibt es extrem viel Theorie drüber. Sie können sogar über die reellen Zahlen Induktion machen, wenn Sie es richtig machen, sogenannte transfinite Induktion. Machen wir jetzt aber nicht, wir machen jetzt einfach N, damit Sie mal sehen, was die Idee ist und dann können Sie die Idee später gerne auf ganz,

und in der Informatik ist das wichtig, Sie werden Induktionen auf andere Mengen als die natürlichen Zahlen haben. Und Sie werden sie auch haben auf Mengen, die noch nicht mal mehr total geordnet sind, sondern nur partiell geordnet. Ja, aber jetzt fangen wir mal da an.

Gut, also das, was ich gerade gesagt habe, packe ich jetzt in den Raster. Wie gesagt, das sind zwei Dinge zu tun. Der erste Feld und die stehen richtig hintereinander und man fängt normalerweise mit dem leichten an und das leichte ist meistens der erste Feld. Das ist der sogenannte Induktionsanfang und in dem muss man jetzt begründen, dass E von Null gilt.

Also, und das macht man normalerweise jetzt mit einem direkten Beweis oder was, also es gilt A, deswegen gilt irgendwas und so weiter, und sie argumentieren und am Schluss muss stehen, also gilt E von Null.

Muss man sich jetzt was einfallen lassen, Sie müssen zeigen, E von Null gilt. In den meisten, zumindest Aufgaben am Anfang, ist das ein Einzeiler. So, das ist der Induktionsanfang und jetzt lohnt es sich und sollte man bei einer Induktion immer machen,

für diesen zweiten Schritt, also wenn N, wenn E von N gilt, dann gilt auch E von N plus 1. Und den müssen Sie ja wirklich für allgemeines N machen, also es nutzt nichts zu zeigen, wenn E von 4 gilt, gilt auch E von 5. Dann haben Sie, dass der fünfte Stein hinter dem vierten steht, aber das sagt nichts über den 328. Stein. Also, das müssen Sie jetzt für jedes N machen und dann lohnt es sich nochmal ganz klar zu machen, wo stehen wir.

Also, wir setzen voraus, dass für irgendein N aus N die Aussage E von N stimmt. Und jetzt kommt der dritte Teil, das ist der Induktionsschluss und auch hier wieder, wenn Sie einen Induktionsbeweis machen,

diese drei Keywords, Induktionsanfang, Induktionsvoraussetzung, Induktionsschluss, die sollten in dem Beweis mal drin stehen. Also, alles was hier unterstrichen ist, sollte irgendwann mal in dem Beweis stehen. Und im Induktionsschluss gehen Sie davon aus, dass die Induktionsvoraussetzung gilt, also E von N.

Und natürlich haben Sie weiter Ihre Voraussetzungen, A sind wahr. Und Ihr Ziel ist jetzt, das wird wieder argumentiert und argumentiert und Sie laufen ein bisschen durch den Irrgarten. Und dann muss am Ende stehen, ja, nee, jetzt müssen wir noch, also Sie argumentieren.

Dann kommt irgendwann ein Moment und der muss in jedem Induktionsbeweis kommen. Wenn der nicht kommt, haben Sie irgendwas vermurkst, an der Sie sagen, wegen der Induktionsvoraussetzung, also wegen E von N, weil E von N wahr ist,

haben Sie irgendwas und dann geht es weiter und weiter und dann muss am Ende stehen, damit gilt E von N plus 1. Also Sie setzen für den Induktionsschluss voraus, E von N gilt und A haben Sie E immer und dann muss E von N plus 1 gelten.

Und ein absoluter, eben ein Plausibilitätscheck ist, schauen Sie sich am Schluss Ihren Beweis nochmal an und suchen Sie die Stelle, wo Sie die Induktionsvoraussetzung verwendet haben. Und wenn Sie die nicht verwendet haben, ist das ein absolutes Alarmzeichen dafür, dass dieser Beweis, wie er darf, den Humbug ist.

Es kann sein, dass Sie sie irgendwie verwendet haben und nur nicht markiert haben. Grundregeln markieren Sie immer, wo die Induktionsvoraussetzung eingeht. Erstens, um selber sicher zu sein, dass Sie es richtig gemacht haben und zweitens für entsprechende nachvollziehende Leser oder Korrekteure. Also das ist eine Grundregel. Die Induktion, wo die Induktionsvoraussetzung nicht eingeht, ist falsch.

100 Prozent. Gut. Also das ist die Induktion. Jetzt brauchen wir natürlich auch ein Beispiel. Ich lege Sie nochmal auf den Overhead und dann machen wir das Beispiel, aber das machen wir dann in Ruhe nach der Pause.

Jetzt gönne ich Ihnen erstmal 10 Minuten kurz Luft holen. So, ich würde gern in die zweite Hälfte einsteigen und Ihnen für das Beweisprinzip der Induktion sogar zwei Beispiele zeigen.

Erstens den absoluten schnellen Klassiker und zweitens ein etwas weiter ergeholtes Beispiel.

Bevor ich das mache, will ich noch eine Bemerkung loswerden. Das ist die Bemerkung 5-4. Ich habe Ihnen die Induktion hier formuliert für natürliche Zahlen, die bei Null losgehen und den Induktionsanfang, das eh von Null wahr ist. Das geht ein bisschen allgemeiner, weil wenn Sie sich wieder die Domino-Schlange vorstellen, dann funktioniert das natürlich auch.

Also wenn die Domino-Schlange richtig steht, das heißt der Induktionsschluss geht durch und Sie stoßen jetzt nicht den Nulltenstein an, sondern weil Sie dazu gerade Lust haben, den fünften, dann funktioniert das natürlich auch. Also Sie dürfen auch gern einen Induktionsanfang mit N gleich 5 machen, dann kriegen Sie

halt, dass für alle N größer gleich 5 die Aussage gilt, wenn der Induktionsschluss durchgeht. Das kommt manchmal vor, weil es eben einfach Aussagen gibt, wo die Null oder die Eins Spielverderber sind, wo es nicht klappt, aber ab zwei geht es gut. Also zum Beispiel können Sie eben auch solche Behauptungen von der Form, für alle N größer gleich irgendeiner Zahl N0 gilt eh von N.

Wenn N0 halt irgendein Startwert in N ist, die können Sie auch per Induktion machen. Induktionsschluss wie vorher und die Induktionsanfang halt mit N0 statt mit Null.

Ja und das was wir vorhin gesagt hatten, Sie können Induktionen auch auf allgemeineren Strukturen machen. Was man halt braucht um Induktionen zu machen, ist irgendwo wo man anfangen kann und ist so eine Struktur, dass eins mit dem nächsten zusammenhängt.

Sie müssen irgendwie sich durch die gesamte Struktur hoppeln können von einem Punkt zum nächsten. Das kann sich auch verzweigen oder so, aber das machen wir in dieser Folge so nicht. Das machen wir allerhöchstens ganz am Ende von Matte 2 und sonst kriegen Sie da in den formalen Grundlagen was zu sehen.

So jetzt aber Beispiele. Und das erste ist der absolute Klassiker von Induktionsbeweis. Die endliche Summenformel der ersten N natürlichen Zahlen. Also meine Behauptung ist, für alle N aus N Stern gilt 1 plus 2 plus 3 plus 4 plus 5 bis N, ist N mal N plus 1 halbe.

Das ist die Behauptung. Also wenn Sie die ersten 37 natürlichen Zahlen addieren, 1 plus 2 plus 3 bis 37, dann ist das 37 mal 38 halbe.

So das wollen wir beweisen und das machen wir per Induktion. Das ist jetzt ein Fall wo es auch ohne Induktion geht. Einen direkten Beweis kann man hier auch relativ leicht finden, wenn man sich an die...

Da weiß man wie üblich nicht ob die stimmen, aber eine Anekdote von ihm, dass er in der Schule war und der Lehrer hatte keine Lust sich um die Klasse zu kümmern und hatte ihm die Aufgabe gegeben, sollen alle Zahlen von 1 bis 100 zusammen zählen und dann hat er mal eine halbe Stunde Ruhe.

Und Gauss kam eben nach drei Minuten zu ihm und hat ihm eben gesagt 5050 und da war er etwas genervt. Und Gaussens Idee war, er zählt nicht 1 plus 2 plus 3 plus 4, sondern er zählt 1 plus 99 und 2 plus 98 und 3 plus 97 und 4 plus 96 zusammen. Dann wird das übersichtlicher und dann kann man das sehr schnell sehen.

Und auf die Weise kann man das auch direkt beweisen, aber ich will Ihnen einen Induktionsbeweis davon zeigen. Hier sind beide ungefähr gleich lang insofern ist das wurscht. Also was brauchen wir für einen Induktionsbeweis? Wir brauchen einen Induktionsanfang.

Schauen Sie für die Orientierung auf die Folie. In dem Fall ist das jetzt schon so ein Fall. Wir haben eine Aussage für alle n aus n Stern. Also in dem Fall machen wir den Induktionsanfang für n gleich 1. Wenn Sie versuchen, das was da steht für n gleich 0 hinzuschreiben, summieren Sie von 1 bis 0. Weiß man nicht so recht, was das soll. Macht sinnigerweise 0, aber fangen wir bei 1 an.

Was ist für n gleich 1 auf der linken Seite der Gleichung? 1 plus und so weiter bis 1. Die linke Seite hat nur einen Summanden. Und das ist was, was Sie bei Induktionsbeweisen oft haben, dass in der Induktionsannahme die Aussage, die da steht, banal bis total einfach ist.

Was steht auf der rechten Seite? Da steht für n gleich 1, 1 mal 1 plus 1 halbe. Und wenn man da länger drauf guckt und richtig rechnet, kommt da auch 1 raus. Und Sie sehen, das ist dasselbe, also das klappt. Also für n gleich 1 stimmt das.

Was ist jetzt die Induktionsvoraussetzung? Die steht auch auf der Folie. Für ein n aus n gelte die Behauptung. Also wir wissen jetzt, dass für ein bestimmtes n aus n Stern gilt, dass wenn Sie 1 plus

2 plus und so weiter plus n ausrechnen, dann kommt da n mal m plus 1 halbe raus. So, das ist die Induktionsvoraussetzung und jetzt kommt der Induktionsschritt. Induktionsschritt, was war das nochmal? Das war diese Argumentation, wenn die Induktionsvoraussetzung gilt, also

wenn die Aussage für n gilt, dann gilt es ja auch für n plus 1. Also was müssen wir machen? Wir müssen die Aussage für n plus 1 nach xen. Also was schauen wir uns an? Wir schauen uns an, die 1 plus 2 plus und so weiter plus n plus n plus 1.

Das ist die Summe aller Zahlen bis n plus 1. So und jetzt kommt der Moment, wo man immer schauen muss, jetzt muss irgendwie wie gesagt die Induktionsvoraussetzung eingehen. Sie müssen jetzt irgendwie in dem, was Sie untersuchen, das finden, worüber Sie was wissen. Worüber wissen wir was? Wir wissen was über die Summe 1 plus 2 plus und so weiter bis n.

Und die finden wir geschickterweise genau hier. Also wissen wir nach Induktionsvoraussetzung, hier geht sie ein, wie gesagt markieren Sie immer, wo die Induktionsvoraussetzung eingeht, dass das dasselbe ist wie n mal n plus 1 halbe plus n plus 1.

So und jetzt ist es nur noch auf den Hauptländer bringen. Das ist n mal n plus 1 plus 2m plus 2 halbe. Das ist jetzt elementare Bruchrechnung. So und dann muss man das noch ein bisschen sortieren.

Wie machen wir das am geschicktesten? Jetzt habe ich es schon nicht schlau gemacht, ich schreibe das mal so. Also n mal n plus 1 plus 2 mal n plus 1. Und dann können Sie das auseinandernehmen als n plus 1 oder ausklammern als n plus 1 mal n plus 2 halbe.

Dann schreibe ich Sie noch deutlicher hin. Das ist n plus 1 mal n plus 1 plus 1 halbe. Nicht viel passiert, nur 2 geschrieben als 1 plus 1. Aber wenn Sie es so haben, dann sehen Sie, dass das genau das ist, wo wir hinwollen.

Wir müssen zeigen, die Summe über die Zahlen von 1 bis n plus 1 ist jetzt der Ausdruck, der steht noch in der Induktionsvoraussetzung. Haben Sie noch der Ausdruck, der da steht, aber mit n plus 1 statt n. N plus 1 mal n plus 1 plus 1 halbe. Damit sind wir schon fertig.

Das ist die Idee der Induktion. Wir haben gezeigt, für n gleich 1 stimmt es. Und dann rauscht die Dominoschlange durch und wir haben es für alle. So, das ist das erste Beispiel. Und das zweite dreht sich um die Mächtigkeit der Potenzmenge.

Also Sie haben eine endliche Menge. Und die Behauptung ist, jetzt bilden Sie von dieser Menge die Potenzmenge, die Menge aller Teilmengen. Wenn n endlich ist, dann hat die Menge auch nur endlich viele Teilmengen. Die Frage ist, sie hat wie viele?

Und das kann man zum Glück ganz genau ausrechnen. Nämlich die Anzahl der Elemente der Potenzmenge ist genau 2 hoch die Anzahl der Elemente von M. Eine Aussage, die übrigens sogar für die leere Menge gilt.

Die Potenzmenge der leeren Menge enthält das Element. Leere Menge ist 1 elementig. Leere Menge hat 0 Elemente. Und 1 ist 2 hoch 0. Passt. Das ist übrigens schon der Induktionsanfang. Aha. Und das beweisen wir jetzt per Induktion nach M.

Und was dann man an diesem Beispiel, nicht nach M, sondern nach der Anzahl der Elemente von M. Was man in dem Beispiel schon sieht, ist, dass manchmal Induktionen noch ein bisschen versteckt sind. Ich hatte vorhin gesagt, eine Induktion sollten Sie mal dann in Betracht ziehen, wenn die Aussage von der Form ist, für jede natürliche Zahl gilt irgendwas.

Das ist hier nur sehr versteckt der Fall. Hier steht im Prinzip, für jede natürliche Zahl, die der Mächtigkeit der Menge M entspricht, gilt das da. Und damit können wir das auch per Induktion angehen. So, also wir machen eine Induktion nach der Mächtigkeit der Menge M.

Das heißt, wir zeigen zunächst, dass die Aussage gilt für alle Mengen der Mächtigkeit 0. Das sind nicht so arg viele. Und dann zeigen wir, wenn die Aussage gilt für alle Mengen der Mächtigkeit N, dann gilt sie auch für alle Mengen der Mächtigkeit N plus 1. Und dann sind wir fertig.

Das ist der Induktionsbeweis, also Induktionsanfang. Induktionsanfang eben, die Aussage gilt für alle Mengen der Mächtigkeit 0. Also die Mächtigkeit von M sei jetzt 0. So, was ist dann, wenn die Mächtigkeit von M 0 ist, dann heißt das M hat kein Element.

Dann wissen wir, was M ist. Da gibt es nicht so viele Mengen, für die das gilt. Da gibt es nur eine, das ist die Leere. So, was ist die Potenzmenge der leeren Menge? Die Potenzmenge der leeren Menge hatten wir uns überlegt, ist eine Menge, die die leere Menge enthält, weil die leere Menge eine Teilmenge der leeren Menge ist.

Aber eben auch die einzige, das heißt, die Menge aller Teilmenge der leeren Menge ist die Menge, die die leere Menge enthält. So, was uns interessiert, ist die Mächtigkeit der Potenzmenge. Also die Mächtigkeit hiervon, das ist 1. 1 ist 2 hoch 0, und 2 hoch 0 ist 2 hoch Mächtigkeit M.

Also ist der Induktionsanfang okay. Jetzt kommt die Induktionsvoraussetzung. Das heißt, wieder unsere Aussage gilt für ein N aus N.

Also wir haben, dass die Mächtigkeit der Potenzmenge von M gleich 2 hoch die Mächtigkeit von M ist, für alle Mengen M mit N Elementen.

Wir gehen davon aus, wir haben die Aussage gezeigt für alle Mengen mit N Elementen. Wir haben sie ja tatsächlich schon gezeigt für alle Mengen mit N Elementen. Und so können wir uns nachher hoch hangeln. So, und was wir jetzt zeigen müssen im Induktionsschluss, Voraussetzung von oben, wir haben es gezeigt für alle Mengen mit N Elementen.

Jetzt muss es auch gelten für alle Mengen mit N plus 1 Elementen. Also sei M eine Menge mit N plus 1 Elementen, dann ist M auf jeden Fall nicht leer. Weil, selbst wenn N 0 war, ist N plus 1 mal mindestens 1.

Also M ist nicht leer. Und jetzt wählen wir uns, weil es nicht leer ist, können wir ein X aus M fest hernehmen. Es ist nicht leer, es gibt also ein X, das nehmen wir. Suchen Sie sich irgendeins aus und das halten wir fest. Und wenn Sie das haben, definieren wir uns eine neue Menge N. Das ist eben der ganze Rest.

Also M ohne das X. Jetzt können Sie wieder fragen, also Sie werden jetzt sehen, das führt zu einem Ziel. Wie kommt man jetzt da drauf, sich gerade zu dieser Menge zu definieren? Das ist das Grundproblem von jedem Beweis, wie kommt man drauf? In dem Fall ist die Begründung, wir wollen die Induktionsvoraussetzung anwenden.

Oder wollen Sie bei einem Induktionsbeweis immerhin, Sie müssen die Induktionsvoraussetzung anwenden. Die Induktionsvoraussetzung sagt Ihnen, was für Mengen der Mächtigkeit N. Sie haben eine Mengen mit Mächtigkeit N plus 1 und Sie brauchen eine der Mächtigkeit N. Also schmeißen Sie ein Element raus, weil dann hat es eine Mächtigkeit N.

Also diese Menge N, die hat jetzt Mächtigkeit N. Also die Anzahl der Elemente von N ist jetzt n, weil sie eins weniger hat als M. Also wissen wir schon, was die Mächtigkeit der Potenzmenge von N ist.

Die ist 2 hoch die Mächtigkeit von N, also 2 hoch N nach Induktionsvoraussetzung. Jetzt können wir sie anwenden, weil die Menge N hat die richtige Mächtigkeit. So und was ich Ihnen jetzt noch zeigen will, das schreibe ich mal als Zwischenbehauptung auf.

Und wenn wir das haben, dann haben wir es im Prinzip. Ich behaupte, die Potenzmenge von M, jetzt ist die Frage, wie hängt die Potenzmenge von M mit der Potenzmenge von N zusammen? Die Potenzmenge von N wissen wir was und die Frage ist, wie hängt die Potenzmenge von M mit der von N zusammen?

Und ich behaupte, da sind alle die drin, die zur Potenzmenge von N gehören. N ist eine Teilmenge von M, also es ist irgendwie sinnig, dass jede Teilmenge von N auch eine von M ist. Aber natürlich noch ein paar mehr, nämlich alle Mengen der Form A vereinigt mit X.

Teilmenge von N ist. Das ist jetzt viel Formelwurst für eine Banalität. Wenn Sie hier M haben, nehmen Sie da Ihr X raus. Was sind jetzt Teilmengen von M? Entweder Ihre Teilmenge enthält das X nicht, dann ist eine Teilmenge von N, oder sie enthält das X, dann ist

sie aber von der Form irgendeine Teilmenge von dem Rest plus das X. Und das ist das, was hier steht. So, und das müssen wir aber natürlich eigentlich beweisen. Das ist die Intuition, warum das gilt. Aber jetzt beweisen wir diese Mengengleichheit hier in der Zwischenbehauptung. Wie macht man Mengengleichheit durch zwei Inklusionen?

Also wir zeigen zunächst, P von M ist da drüben drin enthalten. Wenn B in der Potenzmenge von M ist, dann gibt es jetzt zwei Fälle. Entweder X gehört zu B, oder X gehört nicht zu B. Machen wir erst X gehört zu B. Dann schauen wir uns

die Menge B-Hut an. Das ist genau B ohne das X. B-Hut ist jetzt eine Teilmenge von M, die X nicht enthält. Also eine Teilmenge von M ohne X. Eine Teilmenge von N. Das heißt, das Ding ist aus der Potenzmenge von N. Also ist B aus dieser Menge aller

Teilmengen von N vereinigt mit X. Als A nehmen Sie das B-Hut. Und dann ist

in der Vereinigung rechts drin und wir sind fertig. Zweiter Fall, das X gehört nicht zu B. Naja, wenn das X nicht zu B gehört, ist die Sache einfach. Dann ist nämlich B eine Teilmenge von N. N war ja M ohne das X. Also ist dann B aus der

Potenzmenge von N. Und in jedem Fall ist das Ding entweder eine Potenzmenge von N oder in dieser Menge der A vereinigt X mit A aus der Potenzmenge von N. Haben wir die Inklusion, die eine Inklusion. Was uns noch fehlt, ist die andere Inklusion. Dazu müssen wir uns überlegen, dass die Potenzmenge von

N in der Potenzmenge von M enthalten ist und dass diese zweite Menge da in der Potenzmenge von M enthalten ist. Naja, das ist aber alles nicht schwer. Potenzmenge von N ist die Teilmenge von M. Also ist jede Teilmenge von N eine Teilmenge von M. Damit haben wir, dass die Potenzmenge von N in der Potenzmenge von M enthalten ist. Und auch in dem zweiten Ding stehen nur Teilmenge von M drin. Also das ist die einfache Richtung. So, und jetzt

muss man sich noch eins überlegen. Im Prinzip ist man jetzt versucht zu sagen, damit haben wir es doch im Sack. Was uns interessiert ist die Mächtigkeit der Potenzmenge von M. Sie haben da oben, die können Sie als

Vereinigung von den beiden Mengen schreiben. Die Potenzmenge von N, die wissen, sie hat 2 hoch N Elemente. In der Menge rechts sind auch 2 hoch N Elemente drin, nämlich immer jeweils alle Elemente von P von N und das X dabei. 2 mal 2 hoch N ist 2 hoch N plus 1. Das ist dann ok, wenn diese

beiden Mengen, die da stehen, keine gemeinsamen Elemente enthalten. Und das müssen wir uns noch überlegen, dass das nicht der Fall ist. Also außerdem gilt, dass wenn Sie sich alle Teilmengen von N nehmen und diese

anderen Mengen, die Sie kriegen, indem Sie jede Teilmenge von N noch mit X vereinigen, dass Sie dabei nicht 2 mal dasselbe erwischen, also dass der Schnitt leer ist. Und warum ist das so? Das liegt daran, dass X nicht in N

ist. Nicht in N. Und jede Menge, die in diesem rechten Teil drin liegt, also jede Menge, die von der Form A vereinigt X ist mit A Teilmenge N, enthält X. Und jede Menge, die in dem linken, in der Potenzmenge von N drin ist, die enthält X nicht. Also kann es keine geben, die in beiden drin liegt.

Damit ist dieses Schnitt leer. Und jetzt können Sie tatsächlich eine Übungsaufgabe ziehen. Im Skript war das die 2 8 und auf dem Übungsblatt war das auch irgendeine Nummer. Sie kriegen die Mächtigkeit der Potenzmenge von M als die Mächtigkeit dieser Vereinigung. Das haben wir

festgestellt. Das war die Zwischenbehauptung. Die Potenzmenge ist genau die Vereinigung dieser Potenzmenge von N und die Menge aller Mengen, die Sie kriegen, wenn Sie den Mengen aus der Potenzmenge von N jeweils das X dazu packen. So, davon die Mächtigkeit. Und jetzt war

diese Übungsaufgabe, dass Sie die Mächtigkeit der Vereinigung kriegen als die Summe der Mächtigkeiten minus die Mächtigkeit vom Schnitt, also die Mächtigkeit von P von N plus die Mächtigkeit von dieser Menge A vereinigt X, sodass A aus P von N und das Ganze minus den Schnitt, also

minus die Mächtigkeit der Menge P von N geschnitten mit A vereinigt X, sodass A aus P von N. Das Ding hier hatten wir gesehen ist 0, weil das die

leere Menge ist. Das ist 2 hoch N nach Induktionsvoraussetzung. Das zweite ist 2 hoch N, weil es genauso mächtig ist wie die Potenzmenge von N. Das ist 2 mal 2 hoch N. Das ist 2 hoch N plus 1 und das ist 2

hoch Mächtigkeit von N. Und Sie sind fertig. So, das war jetzt ein bisschen ein komplizierter Induktionsbeweis. Gleich zur Sicherheit. Induktionsbeweise von der Sorte vom ersten, den ich Ihnen vorgeführt habe, müssten Sie in

einer Woche selber führen können. Diesen zweiten, der es mir klar ist, außerhalb der momentanen Reichweite, also ich würde jetzt nächste Woche nicht erwarten, dass Sie mir einen entsprechenden runter bieten oder selber zusammenstückelen, der ist einfach dazu da, um zu sehen, dass dieses Verfahren an anderen Stellen verwendet werden kann und dass so ein

Induktionsbeweis durchaus auch was Längeres sein kann. Dafür kriegt man hier auch eine wirklich starke Aussage. Sie haben die Mächtigkeit der Potenzmenge exakt für jede endliche Menge. So, das war die Abteilung Beweisprinzipien. Das ist so ein Querschnittskapitel, auf das wir

eigentlich nie zurückkommen und trotzdem ständig, weil wir natürlich dauernd beweisen werden. Und dementsprechend lohnt es sich, darüber Gedanken zu machen. Auch an der Stelle nochmal die Werbung für den Treffpunkt Mathematik nächsten Montag, der sich auch nochmal dem

Thema widmen wird. Und die Werbung für die Übungsblätter und alle weiteren Übungsmethoden dazu. Für mich in der Vorlesung ist an wie gesagt, dieser Abschnitt eins steht so unter der Überschrift

mathematische Sprache, Grundkonzepte, mit denen wir arbeiten werden. Und wenn man so will, fangen wir jetzt mit dem Stoff an. Das ist natürlich Käse, weil das auch alles Stoff war, ist mir schon klar. Aber ich will Sie einfach dafür sensibilisieren, dass das, was wir bisher gemacht haben, der Teil ist, über den Sie in zwei Jahren nicht

mehr nachdenken werden, oder nicht mehr nachdenken sollten. Das sind die Grundlagen, das sind die Werkzeuge, mit denen man hinterher arbeitet, von denen man sich dann auch gar nicht mehr so genau überlegen will,

warum die jetzt funktionieren. Und was jetzt kommt ist sozusagen der Inhalt, das was man dann damit anstellen kann. So, und das nächste Kapitel, das Kapitel zwei, ist überschrieben mit algebraische

Strukturen. Und wir wollen im Wesentlichen drei davon behandeln. Das sind Gruppenringe Körper. Und das ist jetzt wahrscheinlich eine

Überschrift, die ich für die meisten von Ihnen genauso hätte auf Chinesisch oder Swahili hinschreiben können, wenn ich es denn könnte. Was ist damit gemeint? Damit ist gemeint, oder womit wir uns jetzt

beschäftigen werden in den nächsten Wochen, ist eigentlich die Frage nicht, wie rechnet man, sondern was ist Rechnen? Was ist eigentlich das, was wir tun, wenn wir rechnen? Was ist die Struktur dahinter? Und wie kann man das abstrakt beschreiben, was Rechnen ist? Und warum tut man

das? Weil wir feststellen werden, natürlich kann man mit Zahlen rechnen und wir wissen alle, wie das funktioniert. Aber man kann auch mit ganz anderen Dingen rechnen. Man kann mit Transformationen der Ebene und des Raums rechnen. Man kann mit Symmetrien rechnen. Man kann mit

Funktionen rechnen. Und wenn man dann genauer hinguckt, stellt man fest, dieses Rechnen mit den Dingern verhält sich an vielen Stellen, so wie das Rechnen mit Zahlen. Aber das merkt man eben erst, wenn man das Rechnen abstrahiert und von der Zahl weggeht. Solange man an den Zahlen klebt, merkt man nicht, dass man eigentlich viel mehr kann als mit

Zahlen rechnen. Und deswegen müssen wir das Rechnen abstrahieren, und dann stellen wir fest, wir kriegen Strukturen, die universell sind, in dem Sinne, dass sie unser Rechnen mit Zahlen beinhalten, aber eben zum Beispiel auch das Rechnen von Symmetrieeigenschaften in Kristallen. Also das, was ich jetzt hier mache, ist durchaus von

hoher Anwendung in der Chemie und in der Kristallographie, witzigerweise. Und dazu müssen wir uns abstrakt überlegen, was heißt denn das Rechnen? Und ich will jetzt gar nicht sofort abstrakt einsteigen, sondern wir fangen da an, wo Sie sich auskennen. Und das ist der Abschnitt 1. Wir rechnen

erst mal in einer Struktur, die wir gut kennen, und zwar in den ganzen Zahlen. Und schauen uns die Begriffe Primzahlen und Teile an. Da sollte auch mal jeder sich erstmal was drunter vorstellen können. Aber die Idee von dem Abschnitt ist durchaus schon, wir machen uns mal klar, was für

Strukturen beim Rechnen gelten, um dann hinterher zu sehen, wie können wir das abstrakt fassen. So, aber jetzt wie gesagt, vergessen Sie erst mal jede Angst vor dem Abstrakten. Wir gehen ganz konkret nach Z. Ich hatte Primzahlen und Teile angekündigt, also definieren wir das.

Definition 1, 1. Nehmen Sie sich mal zwei ganze Zahlen, A und B, her. Und eine Zahl P, die aus N ist. Dann definiere ich erst mal, was es heißt, eine Zahl teilt eine andere. Also wir sagen P teilt A. Und das hatten wir

schon ein, zwei Mal, als ich mit gerade und ungerade um mich geworfen habe. Was bedeutet das P teilt A? Das bedeutet, es gibt irgendeine Zahl M in Z,

sodass Sie das A schreiben können als M mal P. Wenn Sie A schreiben können als M mal P, dann ist P ein Teiler von A. Oder anders gesagt, P teilt A, wenn Sie A-Bombons auf P-Kinder verteilen können, ohne dass es Streit gibt.

Oder ohne dass Sie dann die restlichen drei aufessen müssen. Und dafür gibt es eine Notation, wie es in der Mathematik für fast alles irgendeinen Kürzel gibt. P teilt A schreibt man meistens P teilt A mit so einem Strich. Das heißt aber nichts anderes als P teilt A. So, das ist die erste

Definition. Jetzt kommt die Definition Primzahl. Also Teil B, die Zahl P aus N. Sofern sie denn größer 1 ist, merke, 1 ist nie eine Primzahl. Nennt sich Primzahl,

falls P nur durch 1 und sich selber teilbar ist. Das ist jetzt keine überraschende

Definition. Jede Zahl, die nur durch sich selber und durch 1 teilbar ist, ist eine Primzahl und 1 ist keine. Da gibt es immer mal wieder Missverständnisse. Und dann will ich als letztes noch den größten gemeinsamen Teiler definieren, üblicherweise GGT abgekürzt. Was ist der größte gemeinsame Teiler von zwei Zahlen?

Sie haben zwei Zahlen A und B. Der größte gemeinsame Teiler ist, na jetzt nehmen wir erstmal, was sind alle Teiler? Was sind gemeinsame Teiler? Gemeinsame Teiler sind alle die natürlichen Zahlen, die sowohl A als auch B teilen.

Also es suchen sich alle natürlichen Zahlen, die A und B teilen. Das sind die gemeinsamen Teiler, macht Sinn. Das ist eine Teilmenge von N, die nur endlich viele Elemente hat. Weil natürlich wird es keinen Teiler von A und B geben, der größer als B ist. Also sie haben höchstens B Stück da drin. Und wir hatten

am Anfang bei der Ordnungsrelation in dem Abschnitt mal gesagt, eine schöne Eigenschaft der natürlichen Zahlen ist, jede endliche Menge hat ein Maximum. Und dieses Maximum ist der GGT, die maximale Teiler von beiden.

Also GGT steht für größter gemeinsamer Teiler von A und B. So, und wenn wir in Z unterwegs sind, dann ist es relativ klar, was mit Rechnen

gemeint ist. Wir können addieren, wir können multiplizieren, wir können subtrahieren, funktioniert alles gut. Und die einzige Rechenoperation, die ein bisschen lästig ist, ist das Dividieren. Und das macht die ganze Arithmetik und das ganze Rechnen in Z so ätzend. Jetzt sind sie aber

Informatikerinnen und Informatiker und die müssen viel in Z rechnen. Und dann muss man sich überlegen, wie das damit im Dividieren ist. Und das Problem am Dividieren ist bekanntermaßen, dass es eigentlich nicht richtig geht in Z. Weil eins durch zwei ist halt nun mal keine ganze Zahl.

Und deswegen gibt es die sogenannte Division mit Rest. Auch das ist wahrscheinlich keine weltbewegende Neuigkeit. Was machen Sie, wenn Sie 35 Bonbons auf sechs Kinder verteilen müssen? 35 Bonbons auf sechs Kinder,

dann kriegt jedes Mal fünf. Soweit ist die Sache einfacher, dann bleiben fünf übrig und dann geht die Prügelei los. Und das ist genau die Division mit Rest. Das können schon die Vierjährigen. Nur, dass die es nicht so nennen. Und dann kommen sie eben manchmal auf die glorreiche Idee,

da muss halt Papi die fünf Restlichen essen. Also sein A aus Z und B aus N Stern. Also A ist eine ganze Zahl und B ist eine natürliche Zahl und nicht Null. Warum nicht Null? Weil ich durch B teilen will. Und durch Null teilen ist B. Das wissen Sie auch alle. Und in zwei Wochen wissen Sie auch, warum

durch Null teilen B ist und da gar nichts zu retten ist. Und dieser Satz sagt, wenn Sie eine ganze Zahl A und eine natürliche Zahl N haben, die nicht Null ist, dann können Sie eben mit Rest teilen. Das heißt, dann gibt es

eindeutige Werte Q in Z und R. Und dieses R ist der Rest. Q ist der Quotient und R ist der Rest. Die Buchstaben sind nicht zufällig gewählt. Der Rest ist nicht irgendeine ganze Zahl, sondern ist eine Zahl zwischen Null und B minus eins. Mehr als B werden nicht übrig bleiben, weil wenn B

übrig sind, können Sie die nochmal verteilen. Und was bedeutet jetzt dividieren mit Rest? Bedeutet, dass A, Ihre A-Bombons können Sie auf die B-Kinder verteilen, sodass jedes Q-Stück kriegt und es bleiben A übrig. Also Beispiel, Sie haben 23 Bombons und fünf Kinder, die die

A-Bombons verteilt kriegen sollen. Und dann wissen Sie selber, was rauskommt. Jedes Kind kriegt vier Bombons und drei bleiben übrig. Also 23 geteilt durch fünf ist vier, Rest drei. Und was dieser Satz hier sagt,

ist, diese Division mit Rest ist in Z eine vernünftig erklärte Aktion. Sprich, da kommen immer eindeutig bestimmte Werte raus. Das wird Sie nicht überraschen. Aber trotzdem ist es für den Mathematiker entscheidend,

das einmal gesichert hinzuschreiben und auch zu beweisen. Und diese Quotient und Rest kriegen jetzt noch den Namen, die Sie eben tragen. Also wenn Sie so eine ganze Zahl Z haben und eine natürliche Zahl B, die nicht Null ist, dann kriegen Sie dazu den Q und den R aus dem Satz

eins, zwei. Und dann heißen eben dieses Q und das R Quotient und Rest. Also dann heißt Q der Quotient und R der Rest der Division von A

durch B. Natürlich können Sie auch einfach A durch B teilen. Wenn Sie

in Q sind, dann kriegen Sie einen Bruch raus. Aber im Moment ist natürlich die Idee, unser Universum steht nur als Z. Sie haben einfach nur ganze Zahlen. Sie haben per ordnung und mufti nur integer Variablen zur Verfügung und mit dem müssen Sie auskommen. Und dann ist das die richtige Möglichkeit zu teilen, die Division mit Rest.

Also das sind Quotient und Rest der Division von A durch B. Und die kriegen auch wieder geweisene Formelnotation. Dieses Q schreibt man üblicherweise als A durch B mit so einer Klammer drum herum.

Diese Klammer soll das Ding unterscheiden von dem Bruch A durch B. Den gibt es natürlich auch. A durch B mit der eckigen Klammer drum herum ist eben der ganzzahlige Quotient von A und B. Und das R schreibt man als A modulo B. Also das R ist der Rest, wenn ich A

durch B teile und den schreibt man als A mod B. So, dann muss man jetzt den Satz 1, 2 beweisen. Da finden Sie den Beweis im Skript und ich habe beschlossen an der Stelle in der Vorlesung zu springen.

Das heißt, den erspare ich Ihnen und mir. Wen interessiert und wer noch mal einfach Lust hat, sich einen Beweis anzuschauen, ist herzlich eingeladen. Aber für die Vorlesung ist der erst mal irrelevant. Wichtig ist, dass Sie mitnehmen, dass es diesen Satz gibt und das ist die Division mit Rest. Eindeutige Ergebnisse liefert

für jedes Paar A und B. A aus Z und B aus N Stern. Also ich meine, das darf gerne ein Applaus dafür sein, dass ich den Beweis weglasse, das ist okay. Aber nicht dafür, dass ich jetzt sechs Minuten vorher aufhöre. Ich lasse diesen Beweis ja nicht weg. Ich lasse den Beweis ja im Wesentlichen

weg, weil wir so wahnsinnig hinterher hängen. Dann muss ich das jetzt auch nutzen. Ich meine, wenn ich die sechs Minuten verstreichen lasse, dann kann ich noch den Beweis zeigen. So, diese ganze Division mit Rest führt uns auf etwas,

was Ihnen alle die, die jetzt hier schon in höheren Semestern sitzen, bestätigen werden, in der Pharmatik ständig vorkommt und was Sie auch bald selber dort laufend erleben werden, eben Rechnen in ganzen Zahlen und die sogenannte modulare Arithmetik. Ist auch

wieder ein tolles Wort. Ich sage Ihnen gleich, was das ist. Also modulare Arithmetik. Worum es im Prinzip geht, ist jetzt eben dieses Rechnen in Quotienten und in Resten. Das heißt, worum es geht, ist die Frage,

wie kann man mit diesen Quotienten und mit diesen Resten rechnen? Und Sie werden dann feststellen, das ist Ihnen eigentlich total vertraut. Man nennt es also. Wir wählen jetzt einfach allemal für dieses

Kapitel ein N aus N Stern fest. Das ist das N, durch das wir teilen. Das ist das, was gerade das B war. Also durch dieses N wird jetzt ganz zahlig geteilt. Und dann gibt es jetzt als erstes mal einen Satz mit Rechenregeln für das Modulo. Also,

egal welche A und B aus Z Sie sich hier nehmen, gilt Folgendes, wenn Sie die beiden Zahlen addieren, A plus B und dann schauen, was ist der Rest Modulo N, dann können Sie das machen oder Sie machen Folgendes, Sie schauen zuerst, was ist der Rest von

A Modulo N und was ist der Rest von B Modulo N und addieren diese beiden Reste. Und die Reste, wenn Sie das gemacht haben, könnte es sein, wenn N 5 ist, dass A Modulo 5 ist 3 und B Modulo 5

ist 4, dann steht hier recht 7. Das kann natürlich nicht stimmen, weil 7 ist niemals ein Rest Modulo N bei Modulo 5. Das heißt, was Sie machen müssen, ist, Sie müssen hier am Schluss noch einmal Modulo N rechnen. Aber was hier steht, ist, Sie können

entweder die beiden Zahlen addieren und dann Modulo rechnen oder sofort Modulo, jede einzelne rechnen und dann die Reste addieren. Und das Gleiche gilt nicht nur für addieren, sondern auch für multiplizieren. Ob Sie zuerst A mit B multiplizieren und dann den Rest Modulo N berechnen oder ob Sie zuerst den Rest von A

Modulo N berechnen und den Rest von B Modulo N berechnen. Diese Zahlen multiplizieren und noch einmal Modulo N rechnen. Das ist egal. Und das Ähnliche gilt noch für die Potenz. Wenn Sie A hoch B haben Modulo N, dazu sollte B

aber bitte schön positiv sein, dann können Sie entweder A hoch B ausrechnen und dann Modulo N rechnen oder Sie dürfen auch erst das A Modulo N reduzieren und das hoch B nehmen und dann Modulo N rechnen. Hier ist bitte

schön B, zumindest mal aus N. So, warum ist das toll? Das ist deswegen toll, weil es Ihnen viel Rechenzeit spart. Also mit Ganzzahl

Arithmetik hat man bei vielen Programmen zu tun und mit dem Modulo schon doppelt. Und es ist eben, wenn Sie sich insbesondere den C Teil angucken, ein Unterschied, ob Sie eine 5-stellige Zahl hoch B nehmen und dann den Rest ausrechnen oder ob Sie die 5-stellige Zahl

erst Modulo rechnen, dann kommt 3 raus und dann müssen Sie 3 hoch B nehmen. Das ist ein ziemlicher Rechenunterschied. Und was Ihnen dieser Satz ermöglicht ist, wenn Sie am Schluss von einer ewig langen Rechnung, Sie haben einen Ausdruck, der geht über vier Zeilen und Sie interessieren sich am Schluss aber nur für den Rest Modulo 100,

soll heißen die zwei letzten Stellen oder Sie können nicht den ganzen Ausdruck ausrechnen und dann am Schluss Modulo 100 nehmen, sondern Sie können nach jedem Rechenschritt, nach jedem Plus, nach jedem Mal, bei jedem potenzieren, egal wo, immer erst mal Modulo rechnen und dann weiter rechnen. Das heißt, Sie rechnen nie mit Zahlen, die größer als 100 sind. Und das ist dem

Speicherplatz zuträglich. Gut, Teile dieses Satzes werde ich Ihnen in der nächsten Vorlesung beweisen. Und dann werden wir mit der Modulo Arithmetik weitermachen für heute. Vielen Dank für die Aufmerksamkeit.