s3tomack
Aus ProgrammingWiki
Archivierte Version vom 2015-04-15T18:47:57+00:00. Aktuelle Version
Inhaltsverzeichnis |
Übungsaufgaben
Dieses Kapitel enthält die Übungsaufgaben geordnet nach den Vorlesungen.
Vorlesung 1: Vorbereitungen
Vorlesung 2: Berechenbarkeitsbegriff
abzählbar unendliche Mengen
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.
Für \Z:
z.z.: Die Menge \Z ist abzählbar unendlich.
- abzählbar, d.h. \exists f : \N \rightarrow \Z | \text{ bijektiv }
| | \N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ... |
| | \Z | 0 | -1 | 1 | -2 | 2 | -3 | 3 | ... |
Für \Q:
z.z.: Die Menge \Q ist abzählbar unendlich.
- abzählbar, d.h. \exists f : \N \rightarrow \Q | \text{ bijektiv }
- Elemente von \Q sind darstellbar durch: \frac{p}{q} | q \neq 0 \text{ und } p, q \in \Z
| | p / q | -1 | 1 | -2 | 2 | -3 | 3 | -4 | 4 | -5 | 5 | \ldots |
| | 1 | \frac{-1}{1} | \frac{1}{1} | \frac{-2}{1} | \frac{2}{1} | \frac{-3}{1} | \frac{3}{1} | \frac{-4}{1} | \frac{4}{1} | \frac{-5}{1} | \frac{5}{1} | \ldots |
| | 2 | \frac{-1}{2} | \frac{1}{2} | \frac{-2}{2} | \frac{2}{2} | \frac{-3}{2} | \frac{3}{2} | \frac{-4}{2} | \frac{4}{2} | \frac{-5}{2} | \frac{5}{2} | \ldots |
| | 3 | \frac{-1}{3} | \frac{1}{3} | \frac{-2}{3} | \frac{2}{3} | \frac{-3}{3} | \frac{3}{3} | \frac{-4}{3} | \frac{4}{3} | \frac{-5}{3} | \frac{5}{3} | \ldots |
| | 4 | \frac{-1}{4} | \frac{1}{4} | \frac{-2}{4} | \frac{2}{4} | \frac{-3}{4} | \frac{3}{4} | \frac{-4}{4} | \frac{4}{4} | \frac{-5}{4} | \frac{5}{4} | \ldots |
| | 5 | \frac{-1}{5} | \frac{1}{5} | \frac{-2}{5} | \frac{2}{5} | \frac{-3}{5} | \frac{3}{5} | \frac{-4}{5} | \frac{4}{5} | \frac{-5}{5} | \frac{5}{5} | \ldots |
| | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \ddots |
Unter Zuhilfenahme des Cantorschen Diagonalisierungsverfahren 1. Art lassen sich alle Elemente erreichen.
Für die Menge der Primzahlen P:
z.z.: Die Menge P ist abzählbar unendlich.
- abzählbar, d.h. \exists f : \N \rightarrow P | \text{ bijektiv }
- Die Menge der Primzahlen P ist nach dem Satz von Euklid unendlich.
- Die Menge der Primzahlen P ist abzählbar, da gilt P \subset \N (nach Definition der Primzahlen).
Für die Menge der geraden Zahlen G:
z.z.: Die Menge P ist abzählbar unendlich.
- abzählbar, d.h. \exists f : \N \rightarrow G | \text{ bijektiv }
- Die Menge der geraden Zahlen G ist abzählbar, da gilt G \subset \Z.