Nachlesen

Addition von natürlichen Zahlen

Inhalt

Definition
Eigenschaften
Beweise

Definition

Bei der Addition von natürlichen Zahlen handelt es sich um eine innere zweistellige Verknüpfung $+ : \N \times \N \rightarrow \N$, die durch die folgende Rekursionsvorschrift definiert ist:

\begin{align*} n+0 &= n \\[0.5em] n+1 &= n^\star \\[0.5em] n+k^\star &= {\bigl( n + k \bigr)}^\star \end{align*}

Eigenschaften

Assoziativität

Die Addition von natürlichen Zahlen ist assoziativ. Für natürliche Zahlen $a,b,c \in \N$ gilt:

\bigl( a+b \bigr) + c = a + \bigl( b+c \bigr) = a + b + c.

Kommutativität

Die Addition von natürlichen Zahlen ist kommutativ. Für natürliche Zahlen $a,b \in \N$ gilt:

\[ a+b = b+a. \]

Neutrales Element

Die $0$ ist das neutrale Element der Addition von natürlichen Zahlen:

\[ n + 0 = n = 0 + n. \]

Beweise

Lemma 1

Behauptung: $n + k^\star = n^\star + k$.

(I) Induktionsanfang
Die Aussage ist für $k=0$ richtig. Gemäß der Definition der Addition natürlicher Zahlen gilt $n+0^\star = {(n+0)}^\star = n^\star$ sowie $n^\star + 0 = n^\star$. Hieraus folgt

n + 0^\star = n^\star + 0.

(II) Induktionsschritt
Induktionsannahme: Die Behauptung gelte für einen Wert $k \in \N$.

\begin{align*} n + {\bigl( k^\star \bigr)}^\star &= {\bigl( n + k^\star \bigr)}^\star && \text{(Definition von '$+$')} \\[0.5em] &= {\bigl( n^\star + k \bigr)}^\star && \text{(Induktionsannahme)} \\[0.5em] &= n^\star + k^\star && \text{(Definition von '$+$')} \end{align*}

$\Rightarrow$ Aus (I) und (II) folgt die Behauptung.

Lemma 2

Behauptung: $n + 0 = 0 + n$.

(I) Induktionsanfang
Die Aussage ist für $n=0$ richtig. Es gilt

\[ 0 + 0 = 0 + 0. \]

(II) Induktionsschritt
Induktionsannahme: Die Behauptung gelte für einen Wert $n \in \N$.

\begin{align*} n^\star + 0 &= n + 0^\star && \text{(Lemma 1)} \\[0.5em] &= {\bigl( n+0 \bigr)}^\star && \text{(Definition von '$+$')} \\[0.5em] &= {\bigl( 0+n \bigr)}^\star && \text{(Induktionsannahme)} \\[0.5em] &= 0 + n^\star && \text{(Definition von '$+$')} \end{align*}

$\Rightarrow$ Aus (I) und (II) folgt die Behauptung.

Beweis der Assoziativität

Behauptung: $\bigl( \ell + m \bigr) + n = \ell + \bigl( m + n \bigr)$.

(I) Induktionsanfang
Die Aussage ist für $m=0$ richtig. Es gilt:

\begin{align*} \bigl( \ell + 0 \bigr) + n &= \ell + n && \text{(Definition von '$+$')} \\[0.5em] &= \ell + \bigl( 0 + n \bigr) && \text{(Definition von '$+$')} \end{align*}

(II) Induktionsschritt
Induktionsannahme: Die Behauptung gelte für einen Wert $m \in \N$.

\begin{align*} \bigl( \ell + m^\star \bigr) + n &= \bigl( \ell^\star + m \bigr) + n && \text{(Lemma 1)} \\[0.5em] &= \ell^\star + \bigl( m + n \bigr) && \text{(Induktionsannahme)} \\[0.5em] &= \ell + {\bigl( m + n \bigr)}^\star && \text {(Lemma 1)} \\[0.5em] &= \ell + \bigl( m + n^\star \bigr) && \text{(Definition von '$+$')} \\[0.5em] &= \ell + \bigl( m^\star + n \bigr) && \text{(Lemma 1)} \end{align*}

$\Rightarrow$ Aus (I) und (II) folgt die Behauptung.

Beweis der Kommutativität

Behauptung: $m + n = n + m$.

(I) Induktionsanfang
Die Aussage ist für $m=0$ richtig. Dies folgt direkt aus Lemma 2.

(II) Induktionsschritt
Induktionsannahme: Die Behauptung gelte für einen Wert $m \in \N$.

\begin{align*} n + m^\star &= {\bigl( n+m \bigr)}^\star && \text{(Definition von '$+$')} \\[0.5em] &= {\bigl( m+n \bigr)}^\star && \text{(Induktionsannahme)} \\[0.5em] &= m + n^\star && \text{(Definition von '$+$')} \\[0.5em] &= m^\star + n && \text{(Lemma 1)} \end{align*}

$\Rightarrow$ Aus (I) und (II) folgt die Behauptung.