\documentclass[12pt]{article}

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

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 1}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Di, 9-11 Uhr, Andreas Augustin
	}
\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{\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)}
\begin{enumerate}
	\item Zu zeigen: $M$ abzählbar $\Rightarrow M$ nummerierbar. \\
		Beweis: \\
		{\bfseries 1. Fall:} $M$ ist endlich: $M := \{a_0,a_1,...,a_{n-1}\}, \; n \in \SetN_{\ge 1}$ \\
		Definiere folgende Abbildung
		$$f: \SetN \to \SetN; \; k \mapsto \left\{ \begin{array}{cl} a_k & , k \in \{0,...,n-1\} \\ a_{n-1} & , k \in \{n,n+1,...\} \end{array} \right.$$
		Es ist $f(\SetN) = M$, d.h. $f$ ist surjektiv. \\
		$\Rightarrow M$ ist nummerierbar. \\
		{\bfseries 2. Fall:} $M$ ist nicht endlich, dann gibt es n. Vor. ($M$ abzählbar) eine Bijektion $f: M \to \SetN$ \\
		$\Rightarrow \exists$ die Umkehrabbildung $f^{-1}: \SetN \to M$ und $f^{-1}$ ist ebenfalls bijektiv. \\
		$\Rightarrow f^{-1}: M \to \SetN$ ist insbesondere surjektiv, d.h. $M$ nummerierbar.
	\item Zu zeigen: $M$ abzählbar $\Rightarrow M$ aufzählbar. \\
		Beweis: \\
		{\bfseries 1. Fall:} $M$ ist endlich: $M := \{a_0,a_1,...,a_{n-1}\}, \; n \in \SetN_{\ge 1}$ \\
		Definiere folgende Abbildung
		$$g: M \to \SetN; \; a_k \mapsto k+1 \quad, k \in \{0,...,n-1\}$$
		$g$ ist injektiv, denn:
		\begin{eqnarray*}
			a_i, a_j \in M \AND a_i \ne a_j & \Rightarrow & i \ne j \\
			& \Leftrightarrow & i + 1 \ne j + 1 \\
			& \Leftrightarrow & g(a_i) \ne g(a_j)
		\end{eqnarray*}
		Aus $g: M \to \SetN$ injektiv $\Rightarrow M$ ist aufzählbar. \\
		{\bfseries 2. Fall:} $M$ ist nicht endlich, dann gibt es n. Vor. ($M$ abzählbar) eine Bijektion $g: M \to \SetN$ \\
		$\Rightarrow g: M \to \SetN$ ist insbesondere injektiv, d.h. $M$ ist aufzählbar.
	\item Es bleibt noch zu zeigen: $M$ nummerierbar und $M$ aufzählbar $\Rightarrow M$ abzählbar
\end{enumerate}

\subsubsection*{(b)}
Die Menge $\SetQ$ der rationalen Zahlen ist abzählbar. \\
Beweis:
\begin{enumerate}[(I)]
	\item Zeige zunächst: die Menge $\SetZ$ der ganzen Zahlen ist abzählbar. \\
		Betrachte dazu folgende Abbildung
		$$\varphi: \SetZ \to \SetN; \; n \mapsto \left\{ \begin{array}{cl} 2n & , n \in \SetZ^+ \cup \{0\} \\ -2n - 1 & , n \in \SetZ^- \end{array} \right.$$
		\begin{enumerate}[(1)]
			\item $\varphi$ ist surjektiv, denn:
				\begin{eqnarray*}
					\varphi (\SetZ^+ \cup \{0\}) & = & \{0,2,4,6,...\} =: G \\
					\varphi (\SetZ^-) & = & \{1,3,5,...\} =: U \\
					\Rightarrow \varphi (\SetZ) & = & \varphi(\SetZ^+ \cup \{0\}) \cup \varphi(\SetZ^-) \\
					& = & G \cup U \\
					& = & \SetN
				\end{eqnarray*}
			\item $\varphi$ ist injektiv, denn:
				\begin{eqnarray*}
					n_1,n_2 \in \SetZ^+ \cup \{0\} \AND n_1 \ne n_2 & \Rightarrow & 2n_1 \ne 2n_2 \\
					& \Leftrightarrow & \varphi(n_1) \ne \varphi(n_2) \\
					n_1,n_2 \in \SetZ^- \AND n_1 \ne n_2 & \Rightarrow & -2n_1-1 \ne -2n_2-1 \\
					& \Leftrightarrow & \varphi(n_1) \ne \varphi(n_2) \\
					n_1 \in \SetZ^+ \cup \{0\} \AND n_2 \in \SetZ^- & \Rightarrow & \varphi(n_1) \in G \AND \varphi(n_2) \in U \\
					& \Leftrightarrow & \varphi(n_1) \ne \varphi(n_2)
				\end{eqnarray*}
		\end{enumerate}
		Aus (1) und (2) folgt: \\
		$\varphi: \SetZ \to \SetN$ ist bijektiv, d.h. $\SetZ$ und $\SetN$ sind gleichmächtig und somit ist $\SetZ$ abzählbar.
	\item Betrachte für jede feste natürliche Zahl $k \ge 1$ die Menge
		$$B_k := \left\{ \frac{n}{k} \left| n \in \SetZ \right. \right\}$$
		Da $\SetZ$ abzählbar ist, ist $B_k$ für jedes $k \in \SetN_{\ge 1}$ abzählbar. Da $\SetN$ abzählbar ist, ist die Menge aller $B_k$ abzählbar. \\
		Nach einem Satz aus der Vorlesung ist die Vereinigung abzählbar vieler abzählbarer Mengen ebenfalls abzählbar.
		$$\Rightarrow \bigcup_{k \in \SetN_{\ge 1}} B_k \text{ ist abzählbar}$$
		und wegen
		$$\SetQ = \bigcup_{k \in \SetN_{\ge 1}} B_k$$
		ist auch $\SetQ$ abzählbar.
\end{enumerate}

\section*{Aufgabe 2}
$A$ endliche Menge $\Leftrightarrow A := \{a_0,a_1,...,a_{n-1}\} \quad , n \in \SetN$. $M := \{f: A \to \SetN\}$ \\
Definiere eine Funktion
$$f: A \to \SetN; a_i \mapsto i \quad , i \in \SetN$$
Somit ist die Menge $M$ endlich, da die Menge $A$ endlich ist und es dadurch nur endlich viele Funktionen $f: A \to \SetN$ gibt. Da $M$ endlich ist, ist sie auch abzählbar.

\end{document}
