BuK/IIm14/Studenten/s3tomack

Wiki-Quelltext dieser Seite.

== Ü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 }$
{| border="1" cellpadding="5" cellspacing="0"
|-
|| $\N$ || 0 || 1 || 2 || 3 || 4 || 5 || 6 || ...
|-
|| $\Z$ || 0 || -1 || 1 || -2 || 2 || -3 || 3 || ...
|-
|}
$$f(n) = \begin{cases}
\frac{n}{2}, & \text{wenn } n \text{ gerade}\\
-\left(\frac{n+1}{2}\right), & \text{wenn } n \text{ ungerade}\\
\end{cases}$$

'''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$
{| border="1" cellpadding="5" cellspacing="0"
|-
|| $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$.
$$f(n)=2n$$

=== Vorlesung 3: Entscheidbarkeit und Aufzählbarkeit ===

=== Vorlesung 4: Sätze und Zusammenhänge ===

== Kreativaufgaben ==