\documentclass[10pt]{article}

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

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}


\begin{center}
	{\Large Der Gödelsche Unvollständigkeitssatz \newline \newline}
\end{center}
Betrachte mathematische Ausdrücke der Form:
\begin{enumerate}
	\item
		$ \forall q \in \SetN_0 \quad \exists p \in \SetN_0 \quad \forall x,y \in \SetN_0 \left(p>q \AND (x,y>1 \Rightarrow x \cdot y \neq p)\right)$
	\item
		$ \forall a,b,c,n \in \SetN_0 ((a,b,c>0 \AND n>2) \Rightarrow a^n+b^n \neq c^n)$
	\item
		$ \forall q \in \SetN_0 \quad \exists p\in \SetN_0 \quad \forall x,y \in \SetN_0 (p>q \AND (x,y,>1 \Rightarrow (x \cdot y \neq p \AND x \cdot y \neq p+2)))$
\end{enumerate}
Es sei $\Sigma=\{\AND, \OR, \neg, (, ), \forall, \exists, x, R_1, ..., R_k\}$. Das Symbol \glqq $x$\grqq\ wird verwendet, um Variablen über $\SetN_0$ zu kodieren. \\
Wir verwenden im Folgenden auch $x_i := xxx...x=x^i$ für $i>1$.\\
$R_1, ..., R_k$ stellen Relationen auf $x_1, x_2, x_3, ...$ dar. \\ \\
%
\underline{Beispiele:}
\begin{itemize}
	\item Additionsrelation:
		$$ R_1(x_i, x_j, x_k) = \text{\glqq wahr\grqq } \Leftrightarrow x_i + x_j = x_k $$
	\item Multiplikationsrelation:
		$$ R_2(x_i, x_j, x_k) = \text{\glqq wahr\grqq } \Leftrightarrow x_i \cdot x_j = x_k $$
	\item \glqq $\leq $ \grqq -Relation:
		$$ R_3(x_i, x_j) = \text{\glqq wahr \grqq } \Leftrightarrow x_i \leq x_j $$
\end{itemize}
%
\underline{Definition:}
Ein \underline{Satz} ist ein Ausdruck $w \in \Sigma^*$ der Form:
$$ Q_1x_1 Q_2x_2 Q_3x_3 ... Q_lx_l \Phi$$
wobei $Q_1, ..., Q_l \in \{\forall, \exists\}$ und die  \glqq Formel\grqq\ $\Phi$ wie folgt definiert ist: \\
Rekursive Definition von \glqq Formel\grqq : $\Phi$ ist eine Formel, falls
\begin{enumerate}
	\item
		$$ \Phi = R_j(x_{i_1}, x_{i_2}, ..., x_{i_n}) \text{ für } 1 \leq j \leq k, 1 \leq i_n \leq l $$
	\item
		$$ \Phi = \Phi_1 \AND \Phi_2 \text{ oder } \Phi = \Phi_1 \OR \Phi_2 \text{ oder } \Phi = \neg \Phi_1 \text{, wobei } \Phi_1, \Phi_2 \text{ kürzere Formeln sind.} $$
\end{enumerate}
$\Rightarrow$ Ein Satz ist ein logischer Ausdruck, der entweder wahr oder falsch ist. \\
%
\underline{Bsp.:}\\
$$ \forall x_1 \forall x_2 (R_{\leq}(x_1,x_2) \OR R_{\leq}(x_2,x_1)) $$
%
\underline{Definition:}\\
Für fest vorgegebene Relationen $R_1, ..., R_k$ sei die Sprache $L$ der wahren Sätze definiert als:
$$ L=\{ s=Q_1x_1 Q_2x_2 ... Q_lx_l \Phi \; | \; s \text{ ist wahr}\} $$
%
\underline{Satz 1: {\itshape Satz von Church}}\\
Falls $k=2$ und $R_1$ die Additionsrelation, $R_2$ die Multiplikationsrelation, so ist $L$ nicht rekursiv.\\ \\
%
Der Gödelsche Unvollständigkeitssatz beruht auf folgender Annahme über Beweise:
\begin{enumerate}
	\item
		Ein Beweis $\pi$ eines Satzes $s$ kann von einer TM überprüft werden, d.h. die Sprache
		$$ \{ s \pi \; | \; \pi \text{ ist Beweis von } s \} $$
		ist rekursiv.
	\item
		Ist $\pi$ ein Beweis des Satzes $s$, dann ist $s$ wahr.
\end{enumerate}
\underline{Satz 2:}\\
Die Sprache $L'$ aller beweisbaren Sätze ist rekursiv aufzählbar.\\
($L' = \{ s \text{ Satz} \; | \; \exists \text{ Beweis } \pi \text{ für } s \}$) \\
\underline{Beweis:}\\
Konstruiere TM, die alle möglichen Beweise der Reihe nach durchprobiert. Die TM hält an und akzeptiert, sobald sie einen gültigen Beweis gefunden hat. \QED \\ \\
%
\underline{Satz (Gödel):}\\
Es sei $L$ die Sprache, die mittels Additions- und Multiplikationsrelation definiert ist. Dann gibt es Sätze in $L$, die nicht beweisbar sind. \\
\underline{Beweis:}\\
Annahme: $L'=L$. Gegeben sei Satz $s$. Frage: $s \in L$? (ist $s$ wahr?) \\
Betrachte auch die Negation von $s$: $\neg s$. Beobachtung: $\neg s$ ist selbst wieder ein Satz.\\
Nehme jetzt die TM aus Beweis von Satz 2 und lasse sie parallel auf $s$ und $\neg s$ laufen. Nach endlicher Zeit findet die TM einen Beweis für $s$ oder für $\neg s$. \QED \\
$\lightning$ zu Satz 1.


\end{document}
