Kurs:Vorkurs Mathematik (Osnabrück 2009)/Vorlesung 5



Verknüpfungen

Die Addition und die Multiplikation auf den natürlichen Zahlen und die Hintereinanderschaltung von Abbildungen auf einer Menge sind wichtige Beispiele für das Konzept der Verknüpfung.


Eine Verknüpfung auf einer Menge ist eine Abbildung

Eine Verknüpfung macht also aus einem Paar

ein einziges Element

Eine Vielzahl von mathematischen Konstruktionen fällt unter diesen Begriff: Die Addition, die Differenz, die Multiplikation, die Division von Zahlen, die Verknüpfung von Abbildungen, der Durchschnitt oder die Vereinigung von Mengen, etc. Als Verknüpfungssymbol kommt eine ganze Reihe in Frage, z.B. u.s.w. Je nach dem gewählten Symbol spricht man statt Verknüpfung auch von Multiplikation oder Addition, ohne dass man damit eine inhaltliche Bedeutung verbinden sollte. Wichtige strukturelle Eigenschaften einer Verknüpfung werden in den folgenden Definitionen aufgelistet.


Eine Verknüpfung

auf einer Menge heißt kommutativ, wenn für alle die Gleichheit

gilt.


Eine Verknüpfung

auf einer Menge heißt assoziativ, wenn für alle die Gleichheit

gilt.


Es sei eine Menge mit einer Verknüpfung

gegeben. Dann heißt ein Element neutrales Element der Verknüpfung, wenn für alle die Gleichheit gilt.

Im kommutativen Fall muss man natürlich für das neutrale Element nur eine Reihenfolge betrachten.


Es sei eine Menge mit einer Verknüpfung

und einem neutralen Element gegeben. Dann heißt zu einem Element ein Element inverses Element (zu ). wenn die Gleichheit

gilt.

Bei einer Verknüpfung auf einer Menge bezeichnet man eine (vollständige) Wertetabelle auch als Verknüpfungstafel. In einer solchen Tabelle stehen sowohl in der Leitzeile als auch in der Leitspalte die (linear geordneten) Elemente aus , und in der Überkreuzungsstelle zu und steht der Verknüpfungswert als Eintrag. Dabei muss man festlegen, welche Ordnung zwischen den Zeilen und Spalten gilt, also ob im Kreuzungspunkt der -ten Spalte und der -ten Zeile oder steht. Diese Festlegung ist insbesondere wichtig, da bei Matrizen und Koordinatensystemen andere Konventionen gelten.



Die Peano-Axiome

In den natürlichen Zahlen kann man addieren, multiplizieren, potenzieren, teilweise abziehen, es gibt die kleiner/gleich-Relation, 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.


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 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.

    Ausgehend von den Peano-Axiomen kann man eine Addition auf der Menge der natürlichen Zahlen definieren, wobei die Nachfolgefunktion der Addition mit entspricht. Die Definierbarkeit beruht selbst auf dem Induktionsprinzip. Ebenso kann man eine Multiplikation definieren und die üblichen Eigenschaften wie Kommutativität und Assoziativität nachweisen.

    Wir werden im Folgenden von einem Modell der natürlichen Zahlen ausgehen, bei dem bereits eine Addition und eine Multiplikation definiert wurde, und wir werden die übliche Zifferndarstellung für natürliche Zahlen (im Zehnersystem) verwenden. Wir schreiben also

    und sprechen von der Menge der natürlichen Zahlen. Des weiteren werden wir die lineare (totale) Ordnung auf benutzen, wobei bedeutet, dass es ein gibt mit .



    Das Induktionsprinzip für Aussagen

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


    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 .

    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, sodass gilt.


    Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft. Vom intuitiven Standpunkt her ist sie selbstverständlich, wir führen sie aber trotzdem auf das Induktionsprinzip zurück. Es geht in diesem Beweis weniger dadrum, sich über die Satzaussage zu vergewissern, sondern vielmehr Einblicke in mathematisches Argumentieren zu gewinnen. Es ist auch ein Beispiel dafür, wie man eine Aussage über Teilmengen zu einer Aussage über natürliche Zahlen macht, um das Induktionsprinzip anwenden zu können.


    Jede nichtleere Teilmenge

    besitzt ein Minimum.

    Wir betrachten die Aussage

    = Alle Teilmengen von , die enthalten, besitzen ein Minimum.

    Da jede nichtleere Teilmenge mindestens ein besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von für alle . Diese Aussage können wir durch Induktion beweisen. Die Aussage besagt, dass jede Teilmenge , die die enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben das Minimum ist. Es sei die Aussage nun für alle schon bewiesen. Wir müssen beweisen. Es sei also eine Teilmenge, die enthält. Wenn auch eine Zahl besitzt, so besitzt nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt keine Zahl, die kleiner als ist. Dann ist aber das Minimum von .




    Fakultät und Binomialkoeffizienten

    Es seien nun , , () reelle Zahlen (oder Elemente in einem Körper, ein Begriff, den wir bald einführen werden). Dann wird das Summen- und das Produktzeichen folgendermaßen definiert.

    Dies sind geschlossene und einfach zu verstehende Ausdrücke. Formal korrekter und auch beweistechnisch vorteilhaft ist es, diese Zeichen induktiv durch

    zu erklären. Insbesondere sind für die Vielfachen durch

    und die Potenzen durch

    definiert. Dabei gelten die Konventionen und (die erste lässt sich auch über die Multiplikation begründen, die zweite ist aber auch sinnvoll). [1]


    Zu einer natürlichen Zahl nennt man die Zahl

    die Fakultät von (sprich Fakultät).

    Bei einer -elementigen Menge gibt es bijektive Abbildungen von nach . Gleichbedeutend damit ist, dass es Möglichkeiten, Objekte auf Plätze zu verteilen.


    Es seien und natürliche Zahlen mit . Dann nennt man

    den Binomialkoeffizienten über “.

    Von dieser Definition her ist es nicht sofort klar, dass es sich dabei um natürliche Zahlen handelt. Dies folgt aus der folgenden Beziehung.

    Das Dreieck der Binomialkoeffizienten war in Indien und in Persien schon um 1000 bekannt,
    in China heißt es Yanghui-Dreieck (nach Yang Hui (um 1238-1298)),
    in Europa heißt es das Pascalsche Dreieck (nach Blaise Pascal (1623-1662)).



    Die Binomialkoeffizienten

    erfüllen die rekursive Beziehung

    Beweis

    Siehe Aufgabe 5.21.


    Die folgende Formel bringt die Addition und die Multiplikation miteinander in Beziehung.


    Es seien reelle (oder ganze)

    Zahlen. Ferner sei eine natürliche Zahl. Dann gilt

    Wir führen Induktion nach . Für steht einerseits und andererseits . Es sei die Aussage bereits für bewiesen. Dann ist





    Fußnoten
    1. Bei einer Menge mit einer Verknüpfung setzt man für eine endliche Familie von Elementen generell
      Das leere -Produkt wird dabei als neutrales Element interpretiert, wenn es ein solches gibt

      (es gibt maximal ein neutrales Element)



    << | Kurs:Vorkurs Mathematik (Osnabrück 2009) | >>

    PDF-Version dieser Vorlesung

    Arbeitsblatt zur Vorlesung (PDF)