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

Ganze Zahlen und Rechengesetze

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

$\mathbb {N} =\{0,1,2,\ldots \},$

die Menge der natürlichen Zahlen (mit der ${}0$).

$\mathbb {Z} =\{\ldots ,-2,-1,0,1,2,\ldots \},$

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 ${}\mathbb {Z}$ erfüllt die folgenden Eigenschaften.

1. Es ist

   ${}(a+b)+c=a+(b+c)\,$

   für beliebige (alle) Zahlen ${}a,b,c\in \mathbb {Z}$, d.h. die Addition ist assoziativ.

2. Es ist

   ${}a+b=b+a\,$

   für beliebige Zahlen ${}a,b\in \mathbb {Z}$, d.h. die Addition ist kommutativ.

3. Es gilt

   ${}a+0=a\,$

   für jedes ${}a\in \mathbb {Z}$ (man sagt, dass ${}0$ das neutrale Element der Addition ist).

4. Zu jedem ${}a\in \mathbb {Z}$ besitzt ${}-a$ die Eigenschaft

   ${}a+(-a)=0\,$

   (man sagt, dass ${}-a$ das negative Element zu ${}a$ ist).

Die Multiplikation auf ${}\mathbb {Z}$ erfüllt die folgenden Eigenschaften.

1. Es ist

   ${}(a\cdot b)\cdot c=a\cdot (b\cdot c)\,$

   für beliebige (alle) Zahlen ${}a,b,c\in \mathbb {Z}$, d.h. die Multiplikation ist assoziativ.

2. Es ist

   ${}a\cdot b=b\cdot a\,$

   für beliebige Zahlen ${}a,b\in \mathbb {Z}$, d.h. die Multiplikation ist kommutativ.

3. Es gilt

   ${}a\cdot 1=a\,$

   für jedes ${}a\in \mathbb {Z}$ (man sagt, dass ${}1$ 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

${}a\cdot (b+c)={\left(a\cdot b\right)}+{\left(a\cdot c\right)}\,$

für alle ${}a,b,c\in \mathbb {Z}$.

Wir erinnern an einige weitere Begriffe. Man sagt, dass eine ganze Zahl ${}a$ eine ganze Zahl ${}b$ teilt (oder dass ${}a$ ein Teiler von ${}b$ ist oder dass ${}b$ ein Vielfaches von ${}a$ ist), wenn es eine weitere ganze Zahl ${}c$ mit ${}b=ac$ gibt. Beispielsweise ist ${}3$ ein Teiler von ${}15$, aber ${}2$ ist kein Teiler von ${}15$. Eine gerade Zahl ist eine ganze Zahl, die ein Vielfaches von ${}2$ ist, eine ungerade Zahl ist eine ganze Zahl, die kein Vielfaches von ${}2$ ist. Wenn ${}a$ ein Teiler von ${}b$ ist, so verwenden wir die Bezeichnung ${}{\frac {b}{a}}$ für diejenige (eindeutig bestimmte) ganze Zahl ${}c$, für die die Gleichheit ${}b=ac$ gilt.

Auf den ganzen Zahlen ist auch die Größer/Gleich-Beziehung (oder Ordnungsbeziehung) definiert. Man schreibt ${}a\geq b$, wenn ${}a$ mindestens so groß wie ${}b$ ist. Eine ganze Zahl ${}a$ ist genau dann eine natürliche Zahl, wenn ${}a\geq 0$ ist. Die Beziehung ${}a\geq b$ gilt genau dann, wenn es eine natürliche Zahl ${}c$ mit ${}a=b+c$ gibt. Für die Ordnungsbeziehung gelten die folgenden Regeln, und zwar für beliebige ganze Zahlen ${}a,b,c\in \mathbb {Z}$:

1. Es ist ${}a\geq a$ (dies nennt man die Reflexivität der Ordnung).
2. Aus ${}a\geq b$ und ${}b\geq c$ folgt ${}a\geq c$ (dies nennt man die Transitivität der Ordnung).
3. Aus ${}a\geq b$ und ${}b\geq a$ folgt ${}a=b$ (dies nennt man die Antisymmetrie der Ordnung).
4. Aus ${}a\geq b$ folgt ${}a+c\geq b+c$ (dies nennt man die Additivität der Ordnung).
5. Aus ${}a\geq b$ und ${}c\in \mathbb {N}$ folgt ${}c\cdot a=c\cdot b$ (dies nennt man die Multiplikativität der Ordnung).
6. Aus ${}a\geq b$ und ${}c\in \mathbb {Z} _{-}$ (also ${}c$ negativ) folgt ${}c\cdot a\leq c\cdot b$.

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.

Satz

Für jede natürliche Zahl ${}n$ sei eine Aussage ${}A(n)$ gegeben. Es gelte

1. ${}A(0)$ ist wahr.
2. Für alle ${}n$ gilt: wenn ${}A(n)$ gilt, so ist auch ${}A(n+1)$ wahr.

Dann gilt ${}A(n)$ für alle ${}n$.

Beweis

Es sei

${}M={\left\{n\in \mathbb {N} \mid A(n){\text{ ist wahr}}\right\}}\,.$

Wir wollen zeigen, dass ${}M=\mathbb {N}$ ist, denn genau dies bedeutet, dass die Aussage für alle ${}n$ gilt. Nach der ersten Bedingung ist

${}0\in M\,.$

Nach der zweiten Voraussetzung gilt für ${}M$, dass aus ${}n\in M$ stets ${}n+1\in M$ folgt. Damit erfüllt ${}M$ beide Voraussetzungen im Induktionsprinzip für Mengen, sodass ${}M=\mathbb {N}$ gilt.

$\Box$

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

Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene reelle Zahlen ${}a_{1},\ldots ,a_{n}$ bedeutet

${}\sum _{k=1}^{n}a_{k}:=a_{1}+a_{2}+\cdots +a_{n-1}+a_{n}\,.$

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

${}\prod _{k=1}^{n}a_{k}:=a_{1}\cdot a_{2}{\cdots }a_{n-1}\cdot a_{n}\,.$

Insbesondere sind für ${}n\in \mathbb {N}$ die Potenzen durch

${}a^{n}=\prod _{i=1}^{n}a=a^{n-1}\cdot a=\underbrace {a\cdot a{\cdots }a} _{n{\text{-mal}}}\,$

definiert. Dabei gelten die Konventionen ${}0a=0$ und ${}a^{0}=1$ (die erste lässt sich auch über die Multiplikation begründen, die zweite ist aber auch sinnvoll). Als Rechenregeln für das Potenzieren gelten

1. ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,$

2. ${}a^{n+m}=a^{n}\cdot a^{m}\,$

3. ${}(a^{n})^{m}=a^{nm}\,.$

Aufgabe

Beweise durch Induktion die folgende Formel für ${}n\geq 1$.

${}\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,.$

Lösung

Beim Induktionsanfang ist ${}n=1$, daher besteht die Summe links nur aus einem Summanden, nämlich der ${}1$, und daher ist die Summe ${}1$. Die rechte Seite ist ${}{\frac {1\cdot 2}{2}}=1$, sodass die Formel für ${}n=1$ stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein ${}n\geq 1$ gilt, und müssen zeigen, dass sie auch für ${}n+1$ gilt. Dabei ist ${}n$ beliebig. Es ist

${}{\begin{aligned}\sum _{k=1}^{n+1}k&=\left(\sum _{k=1}^{n}k\right)+n+1\\&={\frac {n(n+1)}{2}}+n+1\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+2)(n+1)}{2}}.\end{aligned}}$

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für ${}n+1$, 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

$1\,\,\,\,\,\,\,\,\,\,\,\,2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,3\,\,\,\,{\cdots }\,\,\,\,n-2\,\,\,\,n-1\,\,\,\,n$

$n\,\,\,\,\,n-1\,\,\,\,\,\,n-2\,\,\,\,{\cdots }\,\,\,\,3\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2\,\,\,\,\,\,\,\,\,\,\,\,1$

Spaltenweise ergibt sich ${}n+1$, und diese Summe kommt ${}n$-mal vor. Also ist

${}2{\left(\sum _{i=1}^{n}i\right)}=n{\left(n+1\right)}\,.$

Aufgabe

Zeige durch vollständige Induktion, dass für jedes ${}n\in \mathbb {N}$ die Zahl

$6^{n+2}+7^{2n+1}$

ein Vielfaches von ${}43$ ist.

Lösung

Induktionsanfang. Für ${}n=0$ ist

${}6^{2}+7=43\,$

ein Vielfaches von ${}43$. Induktionsschritt. Es sei nun die Aussage für ${}n$ bewiesen und betrachten wir den Ausdruck für ${}n+1$. Dieser ist

${}{\begin{aligned}6^{n+1+2}+7^{2(n+1)+1}&=6\cdot 6^{n+2}+7^{2}\cdot 7^{2n+1}\\&=6\cdot 6^{n+2}+(6+43)7^{2n+1}\\&=6{\left(6^{n+2}+7^{2n+1}\right)}+43\cdot 7^{2n+1}\\&=6\cdot 43\cdot s+43\cdot 7^{2n+1}\\&=43\cdot {\left(6\cdot s+7^{2n+1}\right)},\end{aligned}}$

wobei im vorletzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass $6^{n+2}+7^{2n+1}$ ein Vielfaches von ${}43$ ist). Daher ist diese Zahl ein Vielfaches von ${}43$.

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

Es sei ${}d$ eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder natürlichen Zahl ${}n$ eine eindeutig bestimmte natürliche Zahl ${}q$ und eine eindeutig bestimmte natürliche Zahl ${}r$, ${}0\leq r\leq d-1$, mit

${}n=qd+r\,.$

Beweis

Zur Existenz.  Dies wird durch Induktion über ${}n$ bewiesen. Es sei ${}d>0$ fixiert. Der Induktionsanfang für ${}n=0$ ergibt sich direkt mit ${}q=0$ und ${}r=0$. Für den Induktionsschluss sei die Aussage für ${}n$ bewiesen, d.h. wir haben eine Darstellung ${}n=dq+r$ mit ${}r<d$ und müssen eine ebensolche Darstellung für ${}n+1$ finden. Wenn ${}r<d-1$ ist, so ist

${}n+1=dq+r+1\,$

und wegen ${}r+1<d$ ist dies eine gesuchte Darstellung. Ist hingegen ${}r=d-1$, so ist

${}n+1=dq+r+1=dq+d=d(q+1)+0\,,$

und dies ist eine gesuchte Darstellung.
Zur Eindeutigkeit. Sei ${}qd+r=n={\tilde {q}}d+{\tilde {r}}$, wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung ${}{\tilde {r}}\geq r$. Dann gilt ${}(q-{\tilde {q}})d={\tilde {r}}-r$. Diese Differenz ist nichtnegativ und kleiner als ${}d$, links steht aber ein Vielfaches von ${}d$, sodass die Differenz ${}0$ sein muss und die beiden Darstellungen übereinstimmen.

$\Box$

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 ${}n$

gibt es eindeutig bestimmte natürliche Zahlen ${}k$ und ${}r_{0},r_{1},r_{2},\ldots ,r_{k}$ mit ${}0\leq r_{i}\leq 9$ und mit ${}r_{k}\neq 0$ (außer bei ${}n=0$) mit der Eigenschaft

${}n=\sum _{i=0}^{k}r_{i}10^{i}\,.$

Beweis

Wir beweisen die Existenzaussage durch Induktion über ${}n$. Für ${}n=0$ wählt man ${}k=0$ und ${}r_{0}=0$. Es sei nun ${}n\geq 1$ und die Aussage für kleinere Zahlen schon bewiesen. Nach Satz 1.4 mit ${}d=10$ gibt es eine Darstellung

${}n=q\cdot 10+r_{0}\,$

mit ${}r_{0}$ zwischen ${}0$ und ${}9$. Es ist ${}q<n$, deshalb gilt nach Induktionsvoraussetzung die Aussage für ${}q$. D.h. man kann

${}q=\sum _{i=0}^{\ell }s_{i}10^{i}\,$

mit ${}0\leq s_{i}\leq 9$ (bei $q=0$ ist dies als leere Summe zu lesen) und mit ${}s_{\ell }\neq 0$ schreiben. Daher ist

${}{\begin{aligned}n&=q\cdot 10+r_{0}\\&={\left(\sum _{i=0}^{\ell }s_{i}10^{i}\right)}\cdot 10+r_{0}\\&=\sum _{i=0}^{\ell }{\left(s_{i}10^{i+1}\right)}+r_{0}\\&=\sum _{j=1}^{\ell +1}{\left(s_{j-1}10^{j}\right)}+r_{0}\end{aligned}}$

eine Darstellung der gesuchten Art. Dabei ist ${}r_{j}=s_{j-1}$ für ${}j\geq 1$ und ${}k=\ell +1$.
Die Eindeutigkeit folgt ebenfalls aus der Eindeutigkeit bei der Division mit Rest, siehe Aufgabe 1.18.

$\Box$

Eine entsprechende Aussage gilt für jede Basis ${}g\geq 2$ statt ${}g=10$. Bei ${}g=2$ spricht man vom Dualsystem, die einzigen Ziffern sind ${}0$ und ${}1$, bei ${}g=3$ vom Dreiersystem mit den Ziffern ${}0,1,2$ u.s.w.. Bei ${}g=16$ spricht man vom Hexadezimalsystem und verwendet die Ziffern ${}0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$.

Fußnoten

Kurs:Vorkurs Mathematik (Osnabrück 2013) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)