Kurs:Vorkurs Mathematik (Osnabrück 2014)/Vorlesung 1
- 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.
- Es ist
für beliebige (alle) Zahlen , d.h. die Addition ist assoziativ.
- Es ist
für beliebige Zahlen , d.h. die Addition ist kommutativ.
- Es gilt
für jedes (man sagt, dass das neutrale Element der Addition ist).
- Zu jedem
besitzt die Eigenschaft
(man sagt, dass das negative Element zu ist).
Die Multiplikation auf erfüllt die folgenden Eigenschaften.
- Es ist
für beliebige (alle) Zahlen , d.h. die Multiplikation ist assoziativ.
- Es ist
für beliebige Zahlen , d.h. die Multiplikation ist kommutativ.
- 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 mit gibt. 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 :
- Es ist (dies nennt man die Reflexivität der Ordnung).
- Aus und folgt (dies nennt man die Transitivität der Ordnung).
- Aus und folgt (dies nennt man die Antisymmetrie der Ordnung).
- Aus folgt (dies nennt man die Additivität der Ordnung).
- Aus und folgt (dies nennt man die Multiplikativität der Ordnung).
- Aus und (also negativ) folgt .
Bei der Multiplikation mit einer negativen Zahl dreht sich also die Ordnungsbeziehung um.
- Induktion
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.
Für jede natürliche Zahl sei eine Aussage gegeben. Es gelte
- ist wahr.
- 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.
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
Beweise durch Induktion die folgende Formel für .
Beim Induktionsanfang ist , daher besteht die Summe links nur aus einem Summanden, nämlich der , und daher ist die Summe . Die rechte Seite ist , sodass 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
Zeige durch vollständige Induktion, dass für jedes die Zahl
ein Vielfaches von ist.
Induktionsanfang. Für ist
ein Vielfaches von . Induktionsschritt. Es sei nun die Aussage für bewiesen und betrachten wir den Ausdruck für . Dieser ist
wobei im vorletzten 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.
Es 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
Zur Existenz. Dies wird durch Induktion über bewiesen. Es sei fixiert. Der Induktionsanfang für 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 , sodass 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.
Zu jeder natürlichen Zahl
gibt es eindeutig bestimmte natürliche Zahlen und mit und mit (außer bei ) mit der Eigenschaft
Wir beweisen die Existenzaussage durch Induktion über . Für wählt man und . Es 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
- ↑ Bei denke man an Quotient und bei an Rest.
Kurs:Vorkurs Mathematik (Osnabrück 2014) | >> |
---|