Kurs:Vorkurs Mathematik (Osnabrück 2014)/Vorlesung 1

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Ganze Zahlen und Rechengesetze

Wir arbeiten mit den folgenden Mengen, deren Kenntnis wir voraussetzen.

die Menge der natürlichen Zahlen (mit der ).

die Menge der ganzen Zahlen.

Diese Mengen sind mit den natürlichen Operationen Addition und Multiplikation versehen, an deren Eigenschaften wir erinnern.

Die Addition auf erfüllt die folgenden Eigenschaften.

  1. Es ist

    für beliebige (alle) Zahlen , d.h. die Addition ist assoziativ.

  2. Es ist

    für beliebige Zahlen , d.h. die Addition ist kommutativ.

  3. Es gilt

    für jedes (man sagt, dass das neutrale Element der Addition ist).

  4. Zu jedem besitzt die Eigenschaft

    (man sagt, dass das negative Element zu ist).

Die Multiplikation auf erfüllt die folgenden Eigenschaften.

  1. Es ist

    für beliebige (alle) Zahlen , d.h. die Multiplikation ist assoziativ.

  2. Es ist

    für beliebige Zahlen , d.h. die Multiplikation ist kommutativ.

  3. Es gilt

    für jedes (man sagt, dass das neutrale Element der Multiplikation ist).

Man spricht auch vom Assoziativgesetz der Addition u.s.w.. Addition und Multiplikation sind durch das sogenannte Distributivgesetz miteinander verbunden. Dieses besagt

für alle .

Wir erinnern an einige weitere Begriffe. Man sagt, dass eine ganze Zahl eine ganze Zahl teilt (oder dass ein Teiler von ist oder dass ein Vielfaches von ist), wenn es eine weitere ganze Zahl gibt mit . Beispielsweise ist ein Teiler von , aber ist kein Teiler von . Eine gerade Zahl ist eine ganze Zahl, die ein Vielfaches von ist, eine ungerade Zahl ist eine ganze Zahl, die kein Vielfaches von ist. Wenn ein Teiler von ist, so verwenden wir die Bezeichnung für diejenige (eindeutig bestimmte) ganze Zahl , für die die Gleichheit gilt.

Auf den ganzen Zahlen ist auch die Größer/Gleich-Beziehung (oder Ordnungsbeziehung) definiert. Man schreibt , wenn mindestens so groß wie ist. Eine ganze Zahl ist genau dann eine natürliche Zahl, wenn ist. Die Beziehung gilt genau dann, wenn es eine natürliche Zahl mit gibt. Für die Ordnungsbeziehung gelten die folgenden Regeln, und zwar für beliebige ganze Zahlen  :

  1. Es ist (dies nennt man die Reflexivität der Ordnung).
  2. Aus und folgt (dies nennt man die Transitivität der Ordnung).
  3. Aus und folgt (dies nennt man die Antisymmetrie der Ordnung).
  4. Aus folgt (dies nennt man die Additivität der Ordnung).
  5. Aus und folgt (dies nennt man die Multiplikativität der Ordnung).
  6. Aus und (also negativ) folgt .

Bei der Multiplikation mit einer negativen Zahl dreht sich also die Ordnungsbeziehung um.



Induktion
Domen-indukto.png

Mathematische Aussagen, die von natürlichen Zahlen abhängen, können mit dem Beweisprinzip der vollständigen Induktion bewiesen werden. Die folgende Aussage präzisiert und begründet dieses Prinzip.



Satz  

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.


Der Nachweis von (der Gültigkeit von) heißt dabei der Induktionsanfang und der Schluss von auf heißt der Induktionsschluss. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage erst für für ein gewisses (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage und den Induktionsschluss führt man für alle durch.

Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene reelle Zahlen bedeutet

Dabei hängen im Allgemeinen die in einer formelhaften Weise von ab. Entsprechend ist das Produktzeichen definiert, nämlich

Insbesondere sind für 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). Als Rechenregeln für das Potenzieren gelten


Aufgabe

Beweise durch Induktion die folgende Formel für .


Lösung

Beim Induktionsanfang ist , daher besteht die Summe links nur aus einem Summanden, nämlich der , und daher ist die Summe . Die rechte Seite ist , so dass die Formel für stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein gilt, und müssen zeigen, dass sie auch für gilt. Dabei ist beliebig. Es ist

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für , also ist die Formel bewiesen.


Aussagen, die durch Induktion bewiesen werden können, können manchmal auch auf andere Art bewiesen werden. Im vorstehenden Beispiel gibt es die elegantere und einsichtigere Lösung, die Zahlen einmal aufsteigend und einmal absteigend untereinander hinzuschreiben, also

Spaltenweise ergibt sich , und diese Summe kommt -mal vor. Also ist


Aufgabe

Zeige durch vollständige Induktion, dass für jedes die Zahl

ein Vielfaches von ist.


Lösung

Induktionsanfang. Für ist

ein Vielfaches von . Induktionsschritt. Sei nun die Aussage für bewiesen und betrachten wir den Ausdruck für . Dieser ist

wobei im letzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass ein Vielfaches von ist). Daher ist diese Zahl ein Vielfaches von .




Division mit Rest

Jede natürliche Zahl lässt sich bekanntlich als eine Ziffernfolge „im Zehnersystem“ ausdrücken. Dies beruht auf der (sukzessiven) Division mit Rest.



Satz  

Sei eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder natürlichen Zahl eine eindeutig bestimmte natürliche Zahl und eine eindeutig bestimmte natürliche Zahl[1] , , mit

Beweis  

Zur Existenz.  Dies wird durch Induktion über bewiesen. Es sei fixiert. Der Induktionsanfang ergibt sich direkt mit und . Für den Induktionsschluss sei die Aussage für bewiesen, d.h. wir haben eine Darstellung mit und müssen eine ebensolche Darstellung für finden. Wenn ist, so ist

und wegen ist dies eine gesuchte Darstellung. Ist hingegen , so ist

und dies ist eine gesuchte Darstellung.
Zur Eindeutigkeit. Sei , wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung . Dann gilt . Diese Differenz ist nichtnegativ und kleiner als , links steht aber ein Vielfaches von , so dass die Differenz sein muss und die beiden Darstellungen übereinstimmen.


Mit der Division mit Rest können wir die Existenz und Eindeutigkeit der üblichen Zifferndarstellung einer natürlichen Zahl beweisen. Hinter der Zifferndarstellung verbirgt sich eine Mischung aus Addition, Multiplikation und Potenzierung.



Satz  

Zu jeder natürlichen Zahl

gibt es eindeutig bestimmte natürliche Zahlen und mit und mit (außer bei ) mit der Eigenschaft

Beweis  

Wir beweisen die Existenzaussage durch Induktion über . Für wählt man und . Sei nun und die Aussage für kleinere Zahlen schon bewiesen. Nach Satz 1.4 mit gibt es eine Darstellung

mit zwischen und . Es ist , deshalb gilt nach Induktionsvoraussetzung die Aussage für . D.h. man kann

mit (bei ist dies als leere Summe zu lesen) und mit schreiben. Daher ist

eine Darstellung der gesuchten Art. Dabei ist für und .
Die Eindeutigkeit folgt ebenfalls aus der Eindeutigkeit bei der Division mit Rest, siehe Aufgabe 1.18.


Eine entsprechende Aussage gilt für jede Basis statt . Bei spricht man vom Dualsystem, die einzigen Ziffern sind und , bei vom Dreiersystem mit den Ziffern u.s.w.. Bei spricht man vom Hexadezimalsystem und verwendet die Ziffern .



Fußnoten
  1. Bei denke man an Quotient und bei an Rest.


Kurs:Vorkurs Mathematik (Osnabrück 2014) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)