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

Induktive Definition von Abbildungen

Lemma

Es sei $(N,0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und es sei $M$ eine Menge mit einem fixierten Element  $s\in M$  und einer Abbildung $F:M\to M$.

Dann gibt es genau eine Abbildung

$\phi :N⟶M,n⟼\phi (n),$

die die beiden Eigenschaften

$\phi (0)=s\text{ und }\phi (n^{\prime })=F(\phi (n))\text{ für alle }n\in \mathbb{N}$

erfüllt.

Beweis

Wir zeigen zuerst durch Induktion über $k$, dass es auf der Menge $\{0,\dots ,k\}=\{n\in N\mid n\le k\}$ eine eindeutig bestimmte Abbildung

${\phi }_k:\{0,\dots ,k\}⟶M,n⟼{\phi }_k(n),$

gibt, die die erste Bedingung und die zweite Bedingung für alle $n<k$ erfüllt. Bei $k=0$ besteht die Menge aus dem einzigen Element $0$ und dafür legt die erste Bedingung ${\phi }_0(0)=s$ die Abbildung eindeutig fest. Sei die Aussage nun für $k$ bewiesen und betrachte $k^{\prime }$. Es ist $\{0,\dots ,k^{\prime }\}=\{0,\dots ,k\}\cup \{k^{\prime }\}$ und die Bedingungen legen nach Induktionsvoraussetzung eine eindeutige Abbildung $\phi ={\phi }_k:\{0,\dots ,k\}\to M$ fest. Für das zusätzliche Element $k^{\prime }$ muss $\phi (k^{\prime })=F(\phi (k))$ gelten, wodurch die Abbildung auch auf der größeren Menge eindeutig festgelegt ist.

Aufgrund der Eindeutigkeit gilt insbesondere, dass, wenn man ${\phi }_k$ auf $\{1,\dots ,\ell \}$ mit $\ell \le k$ einschränkt, sich ${\phi }_{\ell }$ ergibt. Daher gilt auch, dass die zu konstruierende Abbildung $\phi :N\to M$ eingeschränkt auf jeden Abschnitt $\{1,\dots ,k\}$ mit ${\phi }_k$ übereinstimmen muss. Daher setzen wir $\phi (n):={\phi }_n(n)$, und diese Abbildung erfüllt die Eigenschaften für alle $n$.

$◻$

Aufgrund dieser Eigenschaft kann man jetzt einfach zeigen (siehe Aufgabe 4.3), dass es zu je zwei Peanomodellen $({\mathbb{N}}_1,0_1,\prime )$ und $({\mathbb{N}}_2,0_2,\star )$ für natürliche Zahlen eine eindeutig bestimmte bijektive Abbildung

${\mathbb{N}}_1⟶{\mathbb{N}}_2$

gibt, die $0_1$ in $0_2$ überführt und die mit der Nachfolgeabbildung verträglich ist.

Verknüpfungen

Ausgehend von den Peano-Axiomen kann man eine Addition auf der Menge der natürlichen Zahlen definieren, wobei die Nachfolgefunktion der Addition mit $1=0^{\prime }$ entspricht. Die Definierbarkeit beruht selbst auf dem Induktionsprinzip. Ebenso kann man eine Multiplikation definieren. Beide Operationen fallen unter den Begriff der Verknüpfung, den wir nun allgemein einführen.

Definition

Eine Verknüpfung $\circ$ auf einer Menge $M$ ist eine Abbildung

$\circ :M\times M⟶M,(x,y)⟼\circ (x,y)=x\circ y.$

Eine Verknüpfung macht also aus einem Paar

$(x,y)\in M\times M$

ein einziges Element

$x\circ y\in M.$

Eine Vielzahl von mathematischen Konstruktionen fällt unter diesen Begriff: Die Addition, die Subtraktion, 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. $\circ ,\cdot ,+,-,\oplus ,\mathrm{♣},\mathrm{♡}$ usw. 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.

Definition

Eine Verknüpfung

$\circ :M\times M⟶M,(x,y)⟼x\circ y,$

auf einer Menge $M$ heißt kommutativ, wenn für alle  $x,y\in M$  die Gleichheit

$x\circ y=y\circ x$

gilt.

Definition

Eine Verknüpfung

$\circ :M\times M⟶M,(x,y)⟼x\circ y,$

auf einer Menge $M$ heißt assoziativ, wenn für alle  $x,y,z\in M$  die Gleichheit

$(x\circ y)\circ z=x\circ (y\circ z)$

gilt.

Definition

Es sei eine Menge $M$ mit einer Verknüpfung

$\circ :M\times M⟶M,(x,y)⟼x\circ y,$

gegeben. Dann heißt ein Element  $e\in M$  neutrales Element der Verknüpfung, wenn für alle  $x\in M$  die Gleichheit  $x\circ e=x=e\circ x$  gilt.

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

Definition

Es sei eine Menge $M$ mit einer Verknüpfung

$\circ :M\times M⟶M,(x,y)⟼x\circ y,$

und einem neutralen Element  $e\in M$  gegeben. Dann heißt zu einem Element  $x\in M$  ein Element  $y\in M$  inverses Element (zu $x$), wenn die Gleichheit

$x\circ y=e=y\circ x$

gilt.

Bei einer Verknüpfung auf einer Menge $M$ 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 $M$, und in der Überkreuzungsstelle zu $x$ und $y$ steht der Verknüpfungswert $x\circ y$ als Eintrag. Dabei muss man festlegen, welche Ordnung zwischen den Zeilen und Spalten gilt, also ob im Kreuzungspunkt der $x$-ten Spalte und der $y$-ten Zeile $x\circ y$ oder $y\circ x$ steht. Diese Festlegung ist insbesondere wichtig, da bei Matrizen und Koordinatensystemen andere Konventionen gelten.

Addition auf natürlichen Zahlen

Wir wollen die Addition auf den natürlichen Zahlen definieren, und zwar ausgehend von den Peanoaxiomen. Die Addition mit $0$ soll dabei das Element wiedergeben - d.h. $0$ soll das neutrale Element der Addition sein - und die Addition eines Elementes $n$ mit $1=0^{\prime }$ soll der Nachfolger von $n$ sein. Die Grundidee ist dabei, die Summe $n+k$ dadurch zu definieren, dass man sukzessive den ersten Summand um eins erhöht (also den Nachfolger nimmt) und den zweiten um eins vermindert (also den Vorgänger nimmt, falls $k\ne 0$ ist). Um dies präzise durchzuführen verwenden wir obiges induktives Definitionsprinzip. Wir wenden dieses Prinzip für die Nachfolgerabbildung und für eine natürliche Zahl $n\in \mathbb{N}$ als Startglied an. Die daraus gewonnene Abbildung beschreibt das Addieren mit dieser Zahl $n$ (es wird also die zweistellige Addition auf einstellige Operationen zurückgeführt).

Definition (Addition mit n)

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und  $n\in \mathbb{N}$.  Dann definieren wir die Addition mit $n$ als diejenige aufgrund von Lemma 4.1 eindeutig bestimmte Abbildung

${\alpha }_n:\mathbb{N}⟶\mathbb{N},k⟼{\alpha }_n(k),$

für die

${\alpha }_n(0)=n\text{ und }{\alpha }_n(k^{\prime })=({\alpha }_n(k){)}^{\prime }\text{ für alle }k\in \mathbb{N}$

gilt.

Damit definieren wir

$n+k:={\alpha }_n(k)$

und nennen das die Addition von natürlichen Zahlen. Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist.

Lemma

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen.

Dann gibt es genau eine Verknüpfung

$\mathbb{N}\times \mathbb{N}⟶\mathbb{N},(x,y)⟼x+y,$

mit

$x+0=x\text{ für alle }x\in \mathbb{N}\text{ und }x+y^{\prime }=(x+y{)}^{\prime }\text{ für alle }x,y\in \mathbb{N}.$

Beweis

Siehe Aufgabe *****.

$◻$

Lemma

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen mit der in Definition 4.7 festgelegten Addition.

Dann gelten folgende Aussagen.

1. $n+0=n=0+n$

   für alle $n$, d.h. $0$ ist das neutrale Element für die Addition.

2. $n+k^{\prime }=(n+k{)}^{\prime }=n^{\prime }+k$

   für alle  $n,k\in \mathbb{N}$. 

3. Die Addition ist kommutativ.
4. Die Addition ist assoziativ.
5. Aus einer Gleichung  $n+k=m+k$  folgt

   $n=m$

   (Abziehregel).

Beweis

(1). Die Gleichung links ergibt sich direkt aus der Definition, die rechte Gleichung, also  ${\alpha }_0(n)=n$,  folgt aus einer einfachen Induktion nach $n$.

(2). Die linke Gleichung folgt direkt aus der Definition, die rechte besagt  ${\alpha }_{n^{\prime }}(k)=({\alpha }_n(k){)}^{\prime }$.  Wir beweisen sie für beliebiges $n$ durch Induktion über $k$. Bei  $k=0$  steht beidseitig $n^{\prime }$. Es sei die Aussage nun für $k$ schon bewiesen und betrachten wir $k^{\prime }$. Dann ist

${\alpha }_{n^{\prime }}(k^{\prime })=({\alpha }_{n^{\prime }}(k){)}^{\prime }=(({\alpha }_n(k){)}^{\prime }{)}^{\prime }=({\alpha }_n(k^{\prime }){)}^{\prime }.$

Für die anderen Aussagen siehe Aufgabe 4.5.

$◻$

Multiplikation auf natürlichen Zahlen

Zur Definition der Multiplikation verwenden wir erneut das Prinzip der induktiven Definition. Zu einer natürlichen Zahl $n\in \mathbb{N}$ betrachten wir den Startwert $0$ und die durch die Addition mit $n$ definierte Abbildung ${\alpha }_n:\mathbb{N}\to \mathbb{N}$.

Definition (Multiplikation mit n)

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und  $n\in \mathbb{N}$.  Dann definieren wir die Multiplikation mit $n$ als diejenige aufgrund von Lemma 4.1 eindeutig bestimmte Abbildung

${\mu }_n:\mathbb{N}⟶\mathbb{N},k⟼{\mu }_n(k),$

für die

${\mu }_n(0)=0\text{ und }{\mu }_n(k^{\prime })={\mu }_n(k)+n\text{ für alle }k\in \mathbb{N}$

gilt.

Damit definieren wir die Multiplikation von zwei natürlichen Zahlen $n,k\in \mathbb{N}$ durch

$n\cdot k:={\mu }_n(k).$

Es gilt also $n\cdot 0=0$ und $n\cdot k^{\prime }=n\cdot k+n$. Diese beiden Eigenschaften legen bereits die Multiplikationsverknüpfung eindeutig fest.

Lemma

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen.

Dann gibt es eine eindeutig bestimmte Verknüpfung

$\mathbb{N}\times \mathbb{N}⟶\mathbb{N},(x,y)⟼x\cdot y,$

die

$x\cdot 0=0\text{ für alle }x\in \mathbb{N}\text{ und }x\cdot y^{\prime }=x\cdot y+x\text{ für alle }x,y\in \mathbb{N}$

erfüllt.

Beweis

Siehe Aufgabe *****.

$◻$

Lemma

Es sei $(\mathbb{N},0{,}^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen mit der in Definition 4.10 festgelegten Multiplikation.

Dann gelten folgende Aussagen.

1. Es gilt

   $0\cdot n=0=n\cdot 0$

   für alle $n$,

2. Es gilt

   $1\cdot n=n=n\cdot 1$

   für alle $n$, d.h.  $1=0^{\prime }$  ist das neutrale Element für die Multiplikation.

3. Es ist

   $n\cdot k^{\prime }=n\cdot k+n=k^{\prime }\cdot n$

   für alle  $n,k\in \mathbb{N}$. 

4. Die Multiplikation ist kommutativ.
5. Die Multiplikation ist assoziativ.
6. Aus einer Gleichung  $n\cdot k=m\cdot k$  mit  $k\ne 0$  folgt  $n=m$  (Kürzungsregel).
7. Für beliebige  $k,m,n\in \mathbb{N}$  gilt

   $k\cdot (m+n)=k\cdot m+k\cdot n$

   (Distributivgesetz).

Beweis

Siehe Aufgabe *****.

$◻$

Summen und Produktzeichen

Es seien nun $a_i$, $i=1,\dots ,n$, ($n\ge 1$) natürliche Zahlen (das wird später ebenso für reelle Zahlen oder Elemente in einem beliebigen Körper verwendet). Dann wird das Summen- und das Produktzeichen folgendermaßen definiert.

$\sum _{i=1}^n{a}_i=a_1+a_2+\cdots +a_n\text{ und }\prod _{i=1}^n{a}_i=a_1\cdot a_2\cdots a_n.$

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

$\sum _{i=1}^n{a}_i=(\sum _{i=1}^{n-1}{a}_i)+a_n\text{ und }\prod _{i=1}^n{a}_i=(\prod _{i=1}^{n-1}{a}_i)a_n$

zu erklären. Insbesondere sind für $n\in \mathbb{N}$ die Vielfachen durch

$na=\sum _{i=1}^{n}a=(n-1)a+a=\underset{n\text{-mal}}{\underbrace{a+a+\cdots +a}}$

und die Potenzen durch

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

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

Definition (Fakultät)

Zu einer natürlichen Zahl $n$ nennt man die Zahl

$n!:=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1$

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

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

Gruppen

Definition (Gruppe)

Eine Menge $G$ mit einem ausgezeichneten Element  $e\in G$  und mit einer Verknüpfung

$G\times G⟶G,(g,h)⟼g\mathrm{♡}h,$

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

1. Die Verknüpfung ist assoziativ, d.h. für alle  $f,g,h\in G$  gilt

   $(f\mathrm{♡}g)\mathrm{♡}h=f\mathrm{♡}(g\mathrm{♡}h).$

2. Das Element $e$ ist ein neutrales Element, d.h. für alle  $g\in G$  gilt

   $g\mathrm{♡}e=g=e\mathrm{♡}g.$

3. Zu jedem  $g\in G$  gibt es ein inverses Element, d.h. es gibt ein  $h\in G$  mit

   $h\mathrm{♡}g=g\mathrm{♡}h=e.$

Man beachte, dass kein Kommutativitätsgesetz vorausgesetzt wird, so dass man die zweifachen Formulierungen in Teil (2) und (3) benötigt (eine Gruppe, wo zusätzlich die Kommutativität gilt, heißt kommutative Gruppe). Die Symbole $\mathrm{♡}$ für die Verknüpfung und $e$ für das neutrale Element sind willkürlich gewählt, man könnte sie auch anders nennen. Es ist aber sinnvoll, bei der abstrakten Einführung eine Bezeichnung zu wählen, die intuitiv nicht vorbelastet ist. Eine Bezeichnung wie $\cdot$ für die Verknüpfung und $1$ für das neutrale Element birgt die Gefahr, dass man sich zu Schlüssen verleiten lässt, die von der Multiplikation von Zahlen her vertraut sind, die aber eventuell für eine beliebige Gruppe nicht gelten müssen.

Beispiele für Gruppen sind $(\mathbb{Z},+,0)$(die wir in der nächsten Vorlesung einführen werden), dagegen ist $\mathbb{Z}$ mit der Multiplikation und ebensowenig $\mathbb{Z}\setminus \{0\}$ keine Gruppe. Eine Gruppe ist niemals leer, da es ja ein neutrales Element enthalten muss. Die Menge, die nur aus einem einzigen Element besteht, ist mit der einzig darin möglichen Verknüpfung und dem einzig darin möglichen neutralen Element eine Gruppe. Man spricht von der trivialen Gruppe. Eine weitere Gruppe ist die zweielementige Menge

$(\{-1,1\},\cdot ,1)$

mit der von $\mathbb{Z}$ bekannten Multiplikation.

In einer Gruppe ist zu einem Element $x\in G$ das Element $y$ mit der Eigenschaft $x\circ y=e=y\circ x$ (das es aufgrund der Gruppenaxiome geben muss) eindeutig bestimmt. Wenn nämlich $y$ und $y^{\prime }$ beide diese Eigenschaft besitzen, so gilt

$y=y\circ e=y\circ (x\circ y^{\prime })=(y\circ x)\circ y^{\prime }=e\circ y^{\prime }=y^{\prime }.$

Man beachte, dass in diesen Beweis die Bedingungen an

$y$ und $y^{\prime }$ nicht völlig symmetrisch eingehen. Diese Eindeutigkeit erlaubt es, das zu einem Gruppenelement $x\in G$ eindeutig bestimmte inverse Element als

$x^{-1}$

zu bezeichnen.

In der Mathematik geht es zu einem beträchtlichen Teil um die Lösung von Gleichungen, und zwar um die Existenz von Lösungen, die Berechnung von Lösungen und die Eindeutigkeit von Lösungen. Bei einer Gruppe besitzen die formulierbaren Einzelgleichungen eine eindeutige Lösung. Insofern handelt es sich bei einer Gruppe um eine besonders einfache mathematische Struktur.

Lemma

Es sei $(G,e,\mathrm{♠})$ eine Gruppe.

Dann besitzen zu je zwei Gruppenelementen  $a,b\in G$  die beiden Gleichungen

$a\mathrm{♠}x=b\text{ und }y\mathrm{♠}a=b$

eindeutige Lösungen  $x,y\in G$. 

Beweis

Wir betrachten die linke Gleichung. Aus beidseitiger Multiplikation mit $a^{-1}$ von links folgt, dass nur

$x=a^{-1}\mathrm{♠}b$

als Lösung in Frage kommt. Wenn man dies einsetzt, so sieht man, dass es sich in der Tat um eine Lösung handelt.

$◻$

Fußnoten

<< | Kurs:Mathematik (Osnabrück 2009-2011)/Teil I | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)