\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{cancel}

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 1}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
\subsubsection*{(a)}
Es ist zu zeigen, dass der Begriff der Abzählbarkeit einer Menge $M$, so wie er in der Vorlesung definiert wurde, eine äquivalente Charakterisierung der Begriffe \textit{nummerierbar} und \textit{aufzählbar} ist. \\\\
Beweis:
\begin{itemize}
	\item $M$ \textbf{abzählbar} $\Rightarrow$ $M$ \textbf{aufzählbar} \\
		$M$ ist abzählbar, d.h. $M$ ist endlich oder $\exists$ bijektive Abbildung $f: M \to \SetN$. Wenn $M$ endlich ist, dann kann man jedem Element von $M$ genau eine Zahl $i$ mit $1 \le i \le |M|$ zuweisen, d.h. es gibt eine bijektive Abbildung $a: M \to \{1,...,|M|\}$. Fasst man $a$ nun als Abbildung von $M$ nach $\SetN$ auf, so ist $a$ immer noch injektiv. Wenn $M$ nicht endlich ist, dann gibt es eine bijektive Abbildung $f: M \to \SetN$. Daraus folgt insbesondere, dass $f$ injektiv ist.
	
	\item $M$ \textbf{abzählbar} $\Leftarrow$ $M$ \textbf{aufzählbar} \\
		$M$ aufzählbar, d.h. $\exists$ injektive Abbildung $a: M \to \SetN$. Wenn $M$ endlich ist dann ist es klar, dass $M$ auch abzählbar ist. Andernfalls muss man zeigen, dass es eine bijektive Abbildung $f: M \to T$ mit $T \subset \SetN$ gibt. Dazu schränke ich die Zielmenge $\SetN$ folgendermaßen ein:
		$$T:=\{a(x) \in \SetN \: | \: x \in M\}$$
		Betrachtet man nun die Abbildung $f: M \to T$ mit $f(m) = a(m)$ für alle $m \in M$ so ist $f$ wohl definiert. Weil $a$ injektiv war ist auch $f$ injektiv und aufgrund der Konstruktion von $T$ ist $f$ auch surjektiv.
\end{itemize}
$\Longrightarrow$ Abbildung $f: M \to T$ ist bijektiv. \\
$\Longrightarrow M$ ist abzählbar. \QED

\begin{itemize}
	\item $M$ \textbf{abzählbar} $\Rightarrow$ $M$ \textbf{nummerierbar} \\
		$M$ ist abzählbar, d.h. $M$ ist endlich oder $\exists$ bijektive Abbildung $f: M \to \SetN$. Wenn $M$ endlich ist, dann kann man jedem Element von $M$ genau eine Zahl $i$ mit $1 \le i \le |M|$ zuweisen, d.h. es gibt eine bijektive Abbildung $b: \{1,...,|M|\} \to M$. Erweitert man $b$ nun auf eine Abbildung $b: \SetN \to M$, indem man die Elemente $n \in \SetN$ mit $n > |M|$ auf ein beliebiges Element $m \in M$ abbildet, so ist $b$ immer noch surjektiv. Wenn $M$ nicht endlich ist, dann gibt es eine bijektive Abbildung $f^{-1}: \SetN \to M$. Daraus folgt insbesondere, dass $f^{-1}$ surjektiv ist.
	\item $M$ \textbf{abzählbar} $\Rightarrow$ $M$ \textbf{nummerierbar} \\
		$M$ nummerierbar, d.h. $\exists$ surjektive Abbildung $b: \SetN \to M$. Wenn $M$ endlich ist, dann ist es klar, dass $M$ auch abzählbar ist. Andernfalls muss man zeigen, dass es eine bijektive Abbildung $f: T \to M$ mit $T \subset \SetN$ gibt. Dazu betrachten wir die Funktion $k: M \to \SetN$, die definiert ist durch
		$$k(m) = \min\{n \in \SetN \: | \: b(n) = m\}$$
		und definieren
		$$T = \{k(m) \: | \: m \in M\}$$
\end{itemize}
$\Longrightarrow$ Die Funktion $f: T \to M$ mit $f(t) = b(t)$ ist nun nach Konstruktion bijektiv. \\
$\Longrightarrow M$ ist abzählbar. \QED

\subsubsection*{(b)}
Um zu zeigen, dass $\SetQ$ abzählbar ist, reicht es zu zeigen, dass $\SetQ^+$ abzählbar ist, da gilt $\SetQ = \SetQ^- \cup \{0\} \cup \SetQ^+$, die Menge $\{0\}$ abzählbar ist und sich analog beweisen lässt, dass $\SetQ^-$ abzählbar ist. Da des weiteren gilt, dass die Vereinigung von abzählbaren Mengen wieder abzählbar ist, wäre der Beweis fertig. \\
Es lässt sich ganz leicht beweisen, dass $\SetQ^+$ abzählbar ist, indem man alle Elemente von $\SetQ^+$ aufzählt. Man muss dabei nur gewährleisten, dass jedes Element von $\SetQ^+$ genau einmal in der Liste erscheint, d.h., dass folgender Fall nicht auftritt: $\frac{1}{1} = \frac{2}{2} = 1$. Um dies zu gewährleisten stellt man am besten eine Matrix wie folgt: \\
\begin{center}
\begin{tabular}{cccccc}
	1/1 & 1/2 & 1/3 & 1/4 & 1/5 & 1/6 \\
	2/1 & \cancel{2/2} & 2/3 & \cancel{2/4} & 2/5 & \cancel{2/6} \\
	3/1 & 3/2 & \cancel{3/3} & 3/4 & 3/5 & \cancel{3/6} \\
	4/1 & \cancel{4/2} & 4/3 & \cancel{4/4} & 4/5 & \cancel{4/6} \\
	5/1 & 5/2 & ... &&&
\end{tabular} \\
\end{center}
Die $i$-te Reihe enthält alle Elemente mit dem Zähler $i$, die $j$-te Spalte alle Elemente mit dem Nenner $j$. Diese Matrix wird nun in eine Liste umgewandelt. Die Elemente werden entsprechend ihrer Diagonalen aufgelistet, z.B. enthält die erste Diagonale das Element $\frac{1}{1}$ und die zweite Diagonale die Elemente $\frac{2}{1}$, $\frac{1}{2}$. In der dritten Diagonalen würden wir die Elemente $\frac{3}{1}$, $\frac{2}{2}$, $\frac{1}{3}$ hinzufügen. Elemente, die jedoch schon in der Liste enthalten sind, werden übersprungen (in dem Fall $\frac{2}{2}$, Begründung siehe oben). Auf diese Art und Weise bekommt man eine Auflistung von $\SetQ^+$. \\
$\Longrightarrow \SetQ^+$ ist abzählbar. \\
$\Longrightarrow \SetQ$ ist abzählbar. \QED

\newpage
\section*{Aufgabe 2}
\subsubsection*{(a) und (b)}
Sei $c(n)$ eine Funktion, die ein Tupel $n \in \N^*$ der Größe $|n|$ (stellvertretend für die Dimension) nummeriert. Sie ist folgendermaßen definiert:
\begin{eqnarray*}
	c(n) & = & n, \quad |n|=1 \\
	c(n) & = & Cantor\left(\frac{c(n[1...(|n|-1)])}{c(n[|n|])}\right)
\end{eqnarray*}
Das cantor'sche Diagonalisierungsverfahren wird hier mit $Cantor$ bezeichnet. \\\\
Beweis der Funktion von $c(n)$: \\
\textit{Anmerkung:} \\
Die Überführung eines Tupels $\left< ...,n,k\right>$ in eines der Form $\left<\left< ...,n\right>, k\right>$ ist trivial und erzeugt begründet durch die Definition auf dem Übungsblatt keine Redundanzen, da gilt: $\left<\left<...,...\right>,...\right> \notin \N^*$. \\\\
Beweis per Induktion \\
IA: $c(n) = n \in \N$ \\
IV: $c(n) \in \N, \quad |n|>1$ \\
IS:
\begin{eqnarray*}
	c(\left<n,k\right>) & = & Cantor\left(\frac{c(n)}{c(k)}\right) \\
	c(k) & \in & \N \quad \text{(vgl. IA)} \\
	c(n) & \in & \N \quad \text{(}\rightarrow \text{IV)} \\
\end{eqnarray*}
$$\Rightarrow Cantor\left(\frac{c(n)}{c(k)}\right) \in \N$$ \QED
$c(n)$ ist somit gewissermaßen eine $|n|$-dimensionale Cantor-Funktion. \\\\
Sei ferner $p(n)$ diejenige Funktion, die die $n$-te Primzahl liefert. Die Menge der Primzahlen ist unendlich (trivial). \\\\
Sei $o(n)$ diejenige Funktion, die in einer nach unten beschränkten Menge die Ordnungszahl der Zahl $n$ innerhalb der Menge, sortiert nach natürlicher Ordnung, liefert. Dann beschreibt
$$F(n) = o\left(p(|n|)^{c(n)}\right)$$
eine Bijektion zwischen $\N^*$ und $\N$. \\\\
Somit ist $\N^*$ abzählbar, insbesondere ist $f$ eine solche Bijektion.

\newpage
\section*{Aufgabe 3}
Folgendes ist bekannt: \\
Polynome $n$-ten Grades besitzen maximal $n$ reelle Nullstellen. In Aufgabe 2 wurde $\N^*$ definiert. Analog definiere ich die Menge $\Z^*$ wie folgt:
$$\Z^* = \bigcup_{k \in \N} \Z^k$$
Weiter wurde in Aufgabe 2 gezeigt, dass $\N^*$ abzählbar ist. Man stellt fest, dass $\Z^*$ ebenfalls abzählbar ist, wenn man anschließend die Funktion $f$
$$f: \Z \to \N; x \mapsto \begin{cases}2 \cdot x & , x \in \N \\ 2 \cdot |x| - 1 & , \text{sonst}\end{cases}$$
anwendet. \\
Setzt man diese Elemente von $\Z^*$ jetzt als Koeffizienten in Polynome entsprechenden Grades ein, so hat die resultierende Menge von Nullstellen maximal gleiche Mächtigkeit wie $\Z^*$. Damit lässt sich diese Menge auf eine Teilmenge von $\Z^*$ und damit auf $\N$ abbilden.

\newpage
\section*{Aufgabe 4}
Führt man die in der Aufgabe formulierte Konstruktion analog für die rationalen Zahlen durch, so wird im folgenden bewiesen, dass man damit keine vollständige Überdeckung des Intervalls [0,1] erreichen muss. Damit gilt eine wesentliche Beobachtung des Beweises hier nicht mehr, und man kann das Verfahren nicht wörtlich übertragen. \\
Ordne ich eine gegebene Aufzählung der rationalen Zahlen beliebig um, so erhalte ich wieder eine solche Aufzählung. \\
Wähle ich mir eine beliebige irrationale Zahl $r$ im Intervall [0,1], dann liegen in jeder noch so kleinen Umgebung um diese stets auch rationale Zahlen. Ist nun der Abstand zwischen einer rationalen Zahl $q$ und $r$ gleich $\varepsilon$, so gibt es ein $k \in \SetN$, sodass $\varepsilon > 10^{-k}$ ist. Ordne ich eine gegebene Aufzählung so um, dass $q$ darin frühestens an Position $k$ vorkommt, so ist $r$ nicht in dem $q$ umgebenden Intervall enthalten. Insgesamt kann man damit eine Umordnung konstruieren, in der alle Zahlen, die nahe bei $r$ liegen hinreichend spät aufgezählt werden. Danach wird $r$ auch nicht in der Vereinigung aller die rationalen Zahlen umgebenden Intervalle enthalten sein und die Überdeckung ist nicht vollständig.


\end{document}