Aufgabensammlung Mathematik: Partitionierung der natürlichen Zahlen

Partitionierung der natürlichen Zahlen

Zeige, dass die Menge der positiven geraden Zahlen $G$ und die Menge der positiven ungeraden Zahlen $U$ die Menge $\mathbb {N} _{\geq {1}}$ partitionieren.

Lösungshinweis

Frage: Was musst du zeigen, wenn du beweisen willst, dass $G$ und $U$ die Menge $\mathbb {N} _{\geq 1}$ partitionieren?

1. $G\neq \emptyset$ sowie $U\neq \emptyset$.
2. $G\cup U=\mathbb {N} _{\geq 1}$.
3. $G\cap U=\emptyset$.

Beweis

1. Behauptung: $G\neq \emptyset$ sowie $U\neq \emptyset$

Weil $1\in U$ und $2\in G$ ist, sind beide Mengen $G$ und $U$ nicht leer.

2. Behauptung: $G\cup U=\mathbb {N} _{\geq 1}$

Um die Gleichheit zweier Mengen nachzuweisen, zeigt man, dass die eine Menge Teilmenge der anderen Menge ist und vice versa. Hier musst du also zeigen, dass $G\cup U\subseteq \mathbb {N} _{\geq 1}$ sowie $\mathbb {N} _{\geq 1}\subseteq G\cup U$. Offensichtlich ist $G\subseteq \mathbb {N} _{\geq 1}$ und $U\subseteq \mathbb {N} _{\geq 1}$, folglich $G\cup U\subseteq \mathbb {N} _{\geq 1}$.

Nun die andere Richtung: Sei $x\in \mathbb {N} _{\geq 1}$. Jedes Element lässt sich via Division durch 2 in der Form $x=2\cdot k+r,$ mit $k\in \mathbb {N} _{\geq 0}$ und $r\in \{0,1\}$ darstellen. Ist nun $r=0$, so gilt $x=2\cdot k$, d.h. $x$ ist eine gerade Zahl. Ist hingegen der Rest gleich 1, so ist $x=2\cdot k+1$ und $x\in U$. Somit folgt $\mathbb {N} _{\geq 1}\subseteq G\cup U$. Damit ist $G\cup U=\mathbb {N} _{\geq 1}$ bewiesen.

3. Behauptung: $G\cap U=\emptyset$

Angenommen $G\cap U\neq \emptyset$, d.h. es gibt ein $x\in G\cap U$. Zu so einem sowohl geraden als auch ungeraden $x$ müssten dann $l,k\in \ \mathbb {N} _{\geq 0}$ existieren mit $x=2\cdot k$ sowie $x=2\cdot l+1$. Dann gilt $2\cdot k=2\cdot l+1$ bzw. $2\left(k-l\right)=1$. Nun ist 1 aber gewiss kein Vielfaches von 2 und wir sind bei einem Widerspruch gelandet. Also war die Annahme falsch und es muss gelten $G\cap U=\emptyset$.