Aufgabensammlung Mathematik: Partitionierung der natürlichen Zahlen

Aus Wikibooks

Partitionierung der natürlichen Zahlen

Zeige, dass die Menge der positiven geraden Zahlen und die Menge der positiven ungeraden Zahlen die Menge partitionieren.

Lösungshinweis

Frage: Was musst du zeigen, wenn du beweisen willst, dass und die Menge partitionieren?
  1. sowie .
  2. .
  3. .

Beweis

1. Behauptung: sowie

Weil und ist, sind beide Mengen und nicht leer.

2. Behauptung:

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 sowie . Offensichtlich ist und , folglich .

Nun die andere Richtung: Sei . Jedes Element lässt sich via Division durch 2 in der Form mit und darstellen. Ist nun , so gilt , d.h. ist eine gerade Zahl. Ist hingegen der Rest gleich 1, so ist und . Somit folgt . Damit ist bewiesen.

3. Behauptung:

Angenommen , d.h. es gibt ein . Zu so einem sowohl geraden als auch ungeraden müssten dann existieren mit sowie . Dann gilt bzw. . 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 .