Kurs:Mathematik (Osnabrück 2009-2011)/Teil I/Vorlesung 3

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Zählen
Minutensprunguhr.gif

Der Sekundenanzeiger einer digitalen Uhr besitzt zwei Ziffern und „zählt“ von bis und fängt dann wieder bei an. Bei einem Countdown zählt man von bis und hört dann auf. Das natürliche Zählen startet bei und geht in Einerschritten gegen „unendlich“. Es gibt also verschiedene Arten, zu zählen, und diese wollen wir axiomatisch erfassen mit der Zielsetzung, letztlich das natürliche Zählen zu charakterisieren.


Definition (Zählsystem)  

Eine Menge mit einem ausgezeichneten Element und einer (Nachfolger-)Abbildung

heißt Zählsystem (oder induktives Zählsystem), wenn das folgende Induktionsaxiom erfüllt ist:

Für jede Teilmenge gilt: wenn die beiden Eigenschaften

    • ,
    • mit jedem Element ist auch ,
    gelten, so ist .

    Das Induktionsaxiom hört sich komplizierter an, als es ist. Es fordert einfach, dass man ausgehend vom „Anfangsglied“ durch sukzessives Anwenden der Nachfolgerabbildung letztlich jedes Element in der Menge erhält. Die mengentheoretische Formulierung im Induktionsaxiom ist ein präziser Ersatz für „sukzessive“ und „letztlich“.

    Das Zählen in der letzten Stelle eine digitalen Uhr ist ein Zählsystem: die zugrunde liegenden Menge ist

    das ausgezeichnete Element ist , und die Nachfolgerabbildung wird

    (wenn wir uns hier noch nicht auf die natürlichen Zahlen berufen wollen) durch die Wertetabelle

    gegeben. Ausgehend von erreicht man dabei jedes Element als einen sukzessiven Nachfolger, so dass das Induktionsaxiom erfüllt ist. Die Nachfolgerabbildung ist dabei eine Bijektion.

    Auch die folgende Wertetabelle beschreibt ein Zählsystem.

    Von ausgehend wird jedes Element erreicht. Die Nachfolgerabbildung ist nicht injektiv, sondern sowohl als auch werden beide auf abgebildet. Sie ist auch nicht surjektiv, da keinen Vorgänger hat.



    Die Peano-Axiome

    In den natürlichen Zahlen kann man zwei Elemente ihrer Größe nach vergleichen, man kann sie addieren, multiplizieren, potenzieren, teilweise abziehen, es gibt die Teilbarkeit, usw. Man kann sich nun fragen, welche Abhängigkeiten zwischen diesen mathematischen Strukturen bestehen und ob man manche davon auf andere, grundlegendere Strukturen zurückführen kann. Dies führt zum axiomatischen Aufbau der natürlichen Zahlen. Mit den Peano-Axiomen werden die natürlichen Zahlen definiert als ein induktives Zählsystem, bei dem die Nachfolgerabbildung injektiv ist und kein Nachfolger ist.


    Definition  

    Eine Menge mit einem ausgezeichneten Element (die Null) und einer (Nachfolger)-Abbildung

    heißt natürliche Zahlen (oder Dedekind-Peano-Modell für die natürlichen Zahlen), wenn die folgenden Dedekind-Peano-Axiome erfüllt sind.

    1. Das Element ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
    2. Jedes ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
    3. Für jede Teilmenge gilt: Wenn die beiden Eigenschaften
        • ,
        • mit jedem Element ist auch ,

      gelten, so ist .

      Das heißt, dass die natürlichen Zahlen durch das natürliche Zählen bestimmt sind. Zählen heißt, von einem Startwert ausgehend, nach und nach einen Schritt (einen Strich machen, einen Stab dazulegen, einen Punkt dazumalen) weiterzuzählen. Das „Weiter“-Zählen ist also fundamentaler als eine bestimmte Benennung von Zahlen. Eine natürliche Zahl repräsentiert, wie oft bis zu ihr gezählt werden musste. Die erste Eigenschaft legt den Start fest. Die zweite Eigenschaft besagt, dass wenn zwei Zahlen verschieden sind (oder zwei endliche Mengen mit unterschiedlicher Anzahl vorliegen), dann auch die beiden jeweiligen Nachfolger verschieden sind (die beiden jeweils um ein neues Element erweiterten Mengen ebenfalls eine unterschiedliche Anzahl haben). Die dritte Eigenschaft, die man auch das Induktionsprinzip für Mengen nennt, besagt, dass wenn man bei null anfängt und keinen einzelnen Zählvorgang auslässt, dass man dann vollständig alle natürlichen Zahlen abzählt.

      Es sei schon jetzt erwähnt, dass solche Überlegungen, die natürlichen Zahlen grundlegend zu begründen, manchmal eher verwirrend als hilfreich sein können. Bei den natürlichen Zahlen ist es erfahrungsgemäß nicht gefährlich, der Intuition zu vertrauen und mit einer naiven Vorstellung davon zu arbeiten (dies gilt für die reellen Zahlen nicht in dieser Deutlichkeit). Das ist beim Studienanfang jedenfalls wichtiger als Grundlagenfragen. Wir stellen einige Modelle für die natürlichen Zahlen vor.


      Beispiel  

      Wir betrachten die Menge aller endlichen Strichketten, einschließlich der leeren Kette, also

      Zwei Strichketten sind genau dann gleich, wenn sie „gleichlang“ sind.[1] Das augezeichnete Element ist . Die Nachfolgerabbildung ist dadurch gegeben, dass einer Strichkette die um einen Strich verlängerte Strichkette zugeordnet wird.


      Beispiel  

      Wir stellen ein Ziffernmodell (10er Modell) für die natürlichen Zahlen vor, das die Peanoaxiome erfüllt. Das Modell beruht auf endlichen[2] Symbolketten, wobei die zugrunde gelegte Symbolmenge die Ziffernmenge

      ist. In diesem Modell ist eine natürliche Zahl eine endliche, nichtleere Hintereinanderreihung von Ziffern aus , deren erste[3] Ziffer von der Ziffer verschieden ist, es sei denn, die Gesamtkette ist die -Kette, die aus der einzigen Ziffer besteht. Zwei solche Zahlen sind genau dann gleich, wenn die Ziffernfolgen an jeder Ziffer übereinstimmen. Die -Kette ist das ausgezeichnete Element.

      Die Festlegung der Nachfolgerabbildung erfordert einige Vorbereitungen[4]. Zunächst wird eine Abbildung

      durch

      definiert. Ferner setzten wir . Weiter wird auf der Menge der Ziffernfolgen, in denen ausschließlich die Ziffer vorkommt (wobei die leere Ziffernfolge zugelassen ist) die Abbildung dadurch definiert, dass jede durch eine ersetzt wird. Man kann nun jede erlaubte endliche Ziffernfolge eindeutig schreiben als die Verkettung , wobei eine reine (eventuell leere) Neunerfolge ist, eine einzelne Ziffer oder leer ist, und eine beliebige endliche (eventuell leere) Ziffernfolge ist, die leer sein muss, wenn auch leer ist. Mit diesen Vorbereitungen definieren wir die Nachfolgerabbildung durch


      Die natürliche Zahlen haben den Sinn, die Größe von zwei endlichen Mengen miteinander zu vergleichen. Wenn man von zwei Mengen feststellen möchte, ob sie „gleich groß“ sind, so braucht man dafür aber zunächst nicht die natürlichen Zahlen als „neutrale Vergleichswerte“, sondern man kann die Mengen direkt untereinander mittels bijektiven Abbildungen vergleichen. Dies führt zum Begriff der Gleichmächtigkeit.


      Definition (Gleichmächtigkeit von Mengen)  

      Zwei Mengen und heißen gleichmächtig, wenn es eine bijektive Abbildung

      gibt.

      Ausgehend von der Gleichmächtigkeit von endlichen Mengen gelangt man zu einem weiteren Peano-Modell von natürlichen Zahlen als Äquivalenzklassen von endlichen Mengen, was wir hier nur kurz besprechen werden, siehe auch hier.


      Beispiel  

      Ein Obstverkäufer verfüge über eine unendliche Menge von qualitativ gleichwertigen Äpfeln. Wenn man zu ihm geht und zehn Äpfel bestellt, so hat der Verkäufer verschiedene Möglichkeiten, diesen Wunsch zu verwirklichen, da ja jede Teilmenge seiner Gesamtmenge diesen Wunsch erfüllt, so lange sie eben genau aus Äpfeln besteht. Es sind also alle -elementigen Teilmengen hinsichtlich ihrer Anzahl als gleichwertig zu betrachten, auch wenn es sich um jeweils andere Äpfel handelt. Eine wichtige Beobachtung hierbei ist, dass diese Gleichmächtigkeit (Gleichanzahligkeit) zwischen Teilmengen besteht und festgestellt werden kann unabhängig davon, ob man die natürlichen Zahlen schon kennt oder nicht. Sondern zu zwei Teilmengen kann man durch direkten Vergleich untereinander feststellen, ob sie beide aus gleich vielen Äpfeln bestehen oder nicht. Diese Gleichmächtigkeit definiert eine Äquivalenzrelation auf der Menge der endlichen Teilmengen der Gesamtmenge .

      Es gibt also zu jeder unendlichen Menge auf der Menge der endlichen[5] Teilmengen von die Äquivalenzrelation der Gleichmächtigkeit. Zu jeder endlichen Teilmenge besteht die zugehörige Äquivalenzklasse aus sämtlichen Teilmengen von , die man zu in Bijektion bringen kann, die also die gleiche Anzahl wie besitzen. Die leere Menge ist nur zu sich selbst äquivalent, alle einelementigen Teilmengen sind untereinander äquivalent, etc. Die Quotientenmenge zu dieser Äquivalenzrelation, also die Menge der Äquivalenzklassen, ist ein Peano-Modell für die natürlichen Zahlen. Die durch die leere Menge bestimmte Äquivalenzklasse wird zum ausgezeichneten Element. Die Nachfolgerabbildung wird dadurch definiert, dass man zu einer Äquivalenzklasse die Menge zu einer Menge mit erweitert, was möglich ist, da endlich ist und unendlich. Dann setzt man und zeigt, dass dies unabhängig von der Wahl von und daher eine wohldefinierte Abbildung ist. Diese Quotientenmenge bildet ein Peano-Modell für die natürlichen Zahlen.


      Von nun an arbeiten wir mit einem beliebigen Peano-Modell für die natürlichen Zahlen, das wir mit bezeichnen.



      Das Induktionsprinzip für Aussagen

      Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion.



      Satz (Induktionsprinzip)  

      Für jede natürliche Zahl sei eine Aussage gegeben. Es gelte

      1. ist wahr.
      2. Für alle gilt: wenn gilt, so ist auch wahr.

      Dann gilt für alle .

      Beweis  

      Es sei

      Wir wollen zeigen, dass ist, denn genau dies bedeutet, dass die Aussage für alle gilt. Nach der ersten Bedingung ist

      Nach der zweiten Voraussetzung gilt für , dass aus stets folgt. Damit erfüllt beide Voraussetzungen im Induktionsprinzip für Mengen, so dass gilt.


      Alle mathematischen Strukturen auf den natürlichen Zahlen kann man ausgehend von den Peanoaxiomen konstruieren und ihre Eigenschaften beweisen. Wir werden dies in dieser Vorlesung nur teilweise tun. Der Haupteinwand gegen eine streng durchgeführte mengentheoretisch-axiomatische Deduktion der Strukturen auf den natürlichen Zahlen aus den Peanoaxiomen heraus liegt darin, dass der Aufwand (und zwar hinsichtlich der Arbeit, der Zeit und der Konzentration) unverhältnismäßig erscheint gegenüber dem Nutzen, Strukturen zu begründen, mit denen die Studierenden seit langem wohlvertraut sind. Weiterhin ist schwer zu vermitteln, dass die Sprache der Mengen fundamentaler als die natürlichen Zahlen selbst sein soll. Allerdings ist es schon eine wichtige Erkenntnis, dass nicht alle Operationen auf den natürlichen Zahlen gleichursprünglich sind, sondern dass es zwischen ihnen Abhängigkeiten und Hierarchien gibt. Wir werden nun schrittweise die wesentlichen Strukturen auf den natürlichen Zahlen einführen und dabei parallel das passende Vokabular wie Ordnungsrelationen oder Verknüpfungen einführen.

      Wir beginnen mit der Größergleichbeziehung, die wir schreiben. Für zwei natürliche Zahlen gilt , wenn man von ausgehend durch wiederholtes Nachfolgernehmen schließlich zu gelangt, also

      Diese Definition ist intuitiv klar, aber nicht streng axiomatisch, da die angedeuteten Punkte (mengentheoretisch) unpräzise sind. Eine mengentheoretische Fundierung dieser Beziehung ist etwas aufwändig, siehe hier. Wir geben uns mit der obigen Einführung zufrieden, betonen aber, dass wir die Größergleichrelation auf die Nachfolgeabbildung zurückführen. Um die wesentlichen Eigenschaften der Größergleichrelation formulieren zu können, brauchen wir den Begriff der Ordnungsrelation.



      Ordnungsrelationen

      Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie verwendet.


      Definition (Ordnungsrelation)  

      Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

      1. Es ist für alle .
      2. Aus und folgt stets .
      3. Aus und folgt .

      Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Wenn zusätzlich gilt, dass für je zwei Elemente oder gilt, so spricht man von einer total geordneten Menge.


      Beispiel (Inklusionsrelation auf Potenzmenge)  

      Sei eine beliebige Menge und

      die Potenzmenge davon. Dann sind die Elemente aus - also die Teilmengen von - durch die Inklusionsbeziehung geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus und die Inklusion folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen sind genau dann gleich, wenn und umgekehrt gilt.



      Beispiel (Teilerbeziehung)  

      Wir betrachten die positiven ganzen Zahlen zusammen mit der Teilbarkeitsbeziehung. Man sagt, dass eine Zahl die Zahl teilt, geschrieben

      wenn es eine weitere natürliche Zahl mit

      gibt. Die Bezeichnung ist nicht sonderlich glücklich gewählt, da ein symmetrisches Symbol für eine nichtsymmetrische Relation verwendet wird. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ist, wie zeigt. Die Transitivität sieht man so: sei und mit und . Dann ist und daher . Die Antisymmetrie folgt so: Aus und folgt . Da wir uns auf positive natürliche Zahlen beschränken, folgt und daraus . Also ist Einfache Beispiele wie und zeigen, dass hier keine totale Ordnung vorliegt, da weder von noch umgekehrt geteilt wird.




      Die Ordnungsrelation auf den natürlichen Zahlen

      Wir kommen nun zu den natürlichen Zahlen zurück.



      Lemma  

      Es sei ein Peano-Modell der natürlichen Zahlen. Dann ist die Größergleichrelation eine totale Ordnung.

      Beweis  

      Die Reflexivität und die Transitivität sind klar. Zum Beweis der Antisymmetrie sei und , es gibt also endliche Nachfolgerketten und (also endliche Strichketten ) mit und . Damit ist , wobei einfach die Hintereinanderkettung der Strichketten bedeutet. Wir haben zu zeigen, dass die leere Strichkette ist (dann ist auch die leere Strichkette und somit .). Wir zeigen durch Induktion, dass aus folgt, dass ist. Bei wäre andernfalls , wobei aus dadurch entsteht, dass man einen Strich weglässt, was man kann, sobald es mindestens einen Strich in gibt. Doch dann wäre ein Nachfolger. Sei die Aussage nun für bewiesen und sei . Dies kann man schreiben als . Wegen der Injektivität der Nachfolgerabbildung folgt , also nach Induktionsvoraussetzung.

      Wir beweisen nun, dass die Ordnung total ist, und zwar beweisen wir durch Induktion über die Aussage, dass für jedes die Aussage oder wahr ist. Bei gilt die erste Alternative für jedes und damit die Gesamtaussage. Sei nun die Aussage für schon bewiesen und betrachten wir und ein beliebiges . Nach Induktionsvoraussetzung ist oder . Bei ist auch und also wegen der Transitivität. Sei also . Bei sind wir wieder im ersten Fall, so dass wir also annehmen dürfen. Daher ist mit einer nichtleeren Strichkette , und damit ist auch ein sukzessiver Nachfolger von , also .


      Zu zwei Elementen verwenden wir die abkürzenden Schreibweisen

      Hierbei ist zwar erlaubt, führt aber zur leeren Menge. Besonders wichtig sind die Mengen , da diese die Parademengen für die -elementigen endlichen Mengen sind.



      Zählen und endliche Mengen

      Definition  

      Eine Menge heißt endlich mit Elementen, wenn es eine Bijektion

      gibt.

      Die natürliche Zahl ist dabei nach Aufgabe ***** eindeutig bestimmt und heißt die Anzahl (oder die Kardinalität) der Menge. Sie wird mit oder mit bezeichnet. Die bijektive Abbildung

      kann man eine Nummerierung der Menge nennen. Eine Menge besitzt also Elemente, wenn man sie mit den natürlichen Zahlen von bis durchnummerieren kann. Zwei endliche Mengen und , für die es eine Bijektion

      gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit für kein gibt, heißt unendlich.



      Lemma  

      Es sei eine endliche Menge mit Elementen und eine endliche Menge mit Elementen. Es sei .

      Dann gibt es keine injektive Abbildung

      Beweis  

       Wir nehmen an, dass es eine injektive Abbildung

      gibt. Es sei das Bild von unter der Abbildung . Dann ergibt sich eine Bijektion

      da sich die Injektivität überträgt und da eine Abbildung immer surjektiv auf ihr Bild ist. Daher haben und gleich viele Elemente. Nach Aufgabe ***** ist die Anzahl einer Teilmenge stets kleiner oder gleich der Anzahl der Menge. Also ist im Widerspruch zur Voraussetzung.


      TooManyPigeons.jpg

      Die vorstehende Aussage heißt Schubfachprinzip (oder Taubenschlagprinzip). Es besagt, dass wenn man Tauben auf Plätze verteilt mit , dass dann in mindestens einem Platz mindestens zwei Tauben landen.



      Lemma  

      Seien und endliche Mengen mit Elementen. Dann sind für eine Abbildung

      die Begriffe injektiv, surjektiv und bijektiv äquivalent.

      Beweis  

      Wir führen Induktion über die Anzahl der beiden Mengen und . Bei gibt es nur die leere Abbildung (von der leeren Menge in die leere Menge),

      und diese erfüllt alle drei Eigenschaften. Sei nun und die Aussage für alle Mengen mit einer Anzahl bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Sei zunächst injektiv. Wir wählen ein Element und setzen . Wir setzen

      Beide Mengen haben Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei

      Diese Abbildung ist wohldefiniert, da wegen der Injektivität nur das Element auf abgebildet wird, alle anderen Elemente aus werden auf andere Elemente abgebildet, d.h. sie landen in . Die Injektivität von überträgt sich auf die Teilmenge . Nach der Induktionsvoraussetzung ist also surjektiv. Damit ist aber insgesamt surjektiv, da einerseits im Bild liegt (mit als Urbild) und da andererseits jedes Element zu gehört und damit ein Urbild in besitzt.

      Sei nun surjektiv. Sei beliebig und . Wir betrachten die Einschränkung

      Diese Abbildung kann nicht surjektiv sein. Andernfalls würde sich nämlich der Widerspruch (hier geht auch Aufgabe ***** ein)

      ergeben. Daher muss im Bild fehlen, und das heißt, dass eine surjektive Abbildung

      vorliegt. Beide Mengen besitzen Elemente, so dass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.



      Fußnoten
      1. Das ist nicht einfach zu präzisieren; wenn man dies durch die Existenz einer bijektiven Abbildung zwischen zwei Strichfolgen erklärt, so landet man wieder in der Mengentheorie. Wenn man fordert, dass die Zwischenräume zwischen zwei benachbarten Strichen konstant sein müssen, so kann man Bezug auf die „geometrische Länge“ der Strichfolge nehmen.
      2. Dieser Zugang setzt also voraus, dass man endliche Mengen akzeptiert.
      3. Um von erster Ziffer reden zu können, muss man eine Reihenfolge fixiert haben. Wir gehen hier von der üblichen Reihenfolge aus.
      4. Die folgenden Festlegungen entsprechen denen für ein Computerprogramm, das die natürlichen Zahlen im Zehnersystem durchzählt.
      5. Zu einer Menge kann man die Menge der endlichen Teilmengen darin induktiv definieren, indem man die leere Menge als endlich erklärt und jede Menge, die aus einer endlichen (schon als endlich erwiesenen) Menge durch Hinzunahme von einem weiteren Element entsteht, ebenfalls als endlich erklärt. Eine Menge ist dann selbst unendlich, wenn sie nicht zu ihren endlichen Teilmengen gehört.


      << | Kurs:Mathematik (Osnabrück 2009-2011)/Teil I | >>

      PDF-Version dieser Vorlesung

      Arbeitsblatt zur Vorlesung (PDF)