\section{Der Gödelsche Satz} \inhalta{7-13} \begin{frame} \only
{ In einem Ausblick wollen wir über die Auswirkungen der Nichtberechenbarkeit auf die Axiomatik und Beweisbarkeit in der Zahlentheorie und Geometrie sprechen. Dies soll aber in einer eher informellen Form geschehen. } \only{ Informal: Zusammenhänge zwischen\pause\begin{itemize} \item (Nicht)-Berechenbarkeit \pause \item Beweisbarkeit in der Zahlentheorie \end{itemize} } \label{arithmetische Formeln} \only
{ Die Menge der \Fb{arithmetischen Formeln} können wir als (kontextfreie) Sprache $\cal F$ über folgendem Alphabet darstellen:} \only{ \pause Dazu: \Fb{arithmetische Formeln} \pause als (kontextfreie) Sprache $\cal F$ \pause über } \[\{0,1,x,(,),+,*,=,\neg,\wedge,\vee,\exists,\forall\}\] \only
{ Zunächst definierern wir die Menge $\cal T$ aller Terme durch } \only{ \pause Zunächst Sprache $\cal T$ der \Fb{Terme}:\pause} \begin{itemize} \item Jede natürliche Zahl $i\in\nz$ ist ein Term\pause \item Jede Variable $x_i$ ist ein Term (mit $i\in\nz$), \pause setze $V:=\{x_i\mid i\in\nz\}$\pause \item Sind $t_1$, $t_2$ Terme, dann auch $(t_1+t_2)$ und $(t_1* t_2)$ \end{itemize} \only
{ Die Sprache $\cal F$ der \Fb{Formeln} wird dann definiert durch: } \only{ \pause Sprache $\cal F$ der \Fb{Formeln}:\pause } \begin{itemize} \item Sind $t_1$, $t_2$ Terme, \pause so ist $(t_1=t_2)$ eine Formel\pause \item Sind $F,G$ Formeln, \pause so auch $\neg F$, \pause $(F\wedge G)$ \pause und $(F\vee G)$\pause \item Ist $x$ Variable und $F$ Formel, \pause so sind $\exists x~ F$ \pause und $\forall x~ F$ Formeln. \end{itemize} \pause Dabei werden Zahlen $i$ und die Indizes bei $x_i$ binär notiert. \end{frame} \begin{frame} Terme können \Fb{ausgewertet} werden, \pause wenn den Variablen Werte zugewiesen werden:\pause \begin{itemize} \item Eine Belegung $\phi$ ist eine Abbildung $\phi:V\rightarrow \nz$\pause \item $\phi$ kann auf Terme erweitert werden \pause durch \GLA \phi(n)&=&n\\ \pause\phi(~(t_1+t_2)~) & \pause=& \pause \phi(t_1)+\phi(t_2)\\ \pause\phi(~(t_1* t_2)~) & \pause=& \pause \phi(t_1)\cdot \phi(t_2) \GLE \end{itemize} \pause Beispiel: \pause Mit $\phi(x_1)=5$ und $\phi(x_2)=6$ \pause ist $\phi(~(x_1*(2+x_2))~) \pause =40$ \end{frame} \begin{frame} $\phi$ kann auf Formeln erweitert werden; \pause\\ $\phi(F)$ ist dabei einer der Wahrheitswerte '$wahr$' oder '$falsch$' \pause \begin{itemize} \item $\phi(~(t_1 = t_2)~)=wahr$ \pause genau dann, wenn $\phi(t_1)=\phi(t_2)$ \pause \item $\phi(\neg F)$ ist $wahr$, \pause falls $\phi(F)$ nicht $wahr$ ist, \pause \item $\phi(~(F \wedge G)~)$ ist $wahr$, \pause falls $\phi(F)$ und $\phi(G)$ $wahr$ sind, \pause \item $\phi(~(F \vee G)~)$ ist $wahr$, \pause falls $\phi(F)$ oder $\phi(G)$ $wahr$ ist, \pause \item $\phi(~\exists y~F) $ ist $wahr$, \pause falls $\phi'(F)=wahr$ \pause \\ bei einer beliebigen Belegung $\phi'$ \pause mit $\phi'(x)=\phi(x)$ für $x\neq y$, \pause \item $\phi(~\forall y~F~ )$ ist $wahr$, \pause falls $\phi'(F)=wahr$ \pause \\ bei allen Belegungen $\phi'$ \pause mit $\phi'(x)=\phi(x)$ für $x\neq y$. \end{itemize} \pause Beispiele: \pause \begin{itemize} \item $\phi(~(x_1+1)=x_2~)=wahr$ \pause für jedes $\phi$ mit $\phi(x_1)+1=\phi(x_2)$ \pause \item $\phi(~\exists x_1~((x_1+1)=x_2)~)=wahr$ \pause für jedes $\phi$ mit $\phi(x_2)>0$ \pause \item $\phi(~\exists x_1~((x_1+1)=x_2)~)=falsch$ \pause für jedes $\phi$ mit $\phi(x_2)=0$ \pause \item $\phi(~\exists x_2~((x_1+1)=x_2)~)=wahr$ \pause für jedes beliebige $\phi$ \end{itemize} \end{frame} \begin{frame} Eine Funktion $f: \nz^k\Partial \nz$ hei"st \Fb{arithmetisch repräsentierbar}, \pause wenn es eine arithmetische Formel $F$ gibt, so dass für alle $n_0,n_1,..., n_k\in\nz$ gilt: \pause \GLA&f(n_1,..., n_k) = n_0\textrm{ genau dann,} \\ &\pause\textrm{ wenn }\phi(F)=wahr \pause\textrm{ für alle }\phi \textrm{ mit }\phi(x_i)=n_i, 0{\leq} i{\leq}k \GLE \pause Beispiele: \pause\begin{itemize} \item Die Addition wird repräsentiert durch \pause $x_0=x_1+x_2$ \pause \item Die Subtraktion wird repräsentiert durch \pause $(x_2+x_0=x_1) \pause\vee(x_0=0\wedge \exists x_3 (x_1+x_3+1=x_2))$ \end{itemize} \pause Es gilt nun der folgende Satz: \pause \begin{lemma} Jede WHILE-berechenbare Funktion ist arithmetisch repräsentierbar. \end{lemma} \pause Beweis: durch Induktion über den Aufbau von WHILE-Programmen. \pause \\ Der Beweis ist allerdings technisch etwas aufwändig... \end{frame} \begin{frame} Eine arithmetische Formel $F$ heißt wahr (oder gültig), \pause wenn für alle $\phi$ stets $\phi(F)= wahr$ ist, \pause z.B \GLA&x_1+x_2=x_2+x_1\\ &\pause\neg \exists x_4~((x_1+1)^{x_4+3}+(x_2+1)^{x_4+3}=x_3^{x_4+3}) \GLE \pause Mit Reduktion eines unserer Halteprobleme auf die Menge der wahren arithmetischen Formeln zeigt man:\pause \begin{lemma} Die Menge der wahren arithmetischen Formeln ist nicht rekursiv aufzählbar. \end{lemma} \end{frame} \only
{\begin{frame} Ein \Fb{Beweissystem} $(B,\Psi)$ für eine Formelmenge $A$ besteht aus einer Menge $B$ von \Fb{Beweisen} und einer \Fb{Interpretationsfunktion} $\Psi: B \rightarrow A$. Ein Beweis $b\in B$ ist eine Zeichenkette über einem Alphabet $E$ , die nach gewissen syntaktischen Regeln und Schlussschemata aufgebaut sein muss. Eine Minimalforderung ist sicherlich, dass die Menge der Beweise $B$ entscheidbar ist: Man sollte einer Zeichenkette ansehen können, ob sie ein Beweis ist oder nicht. Au"serdem sollte man aus einem Beweis auch die dadurch bewiesene Aussage herauslesen können. Dies leistet die Interpretationsfunktion $\Psi $ mit Definitionsbereich $B$, die angibt, welche Formel $y\in A$ durch den Beweis $b\in B$ bewiesen wurde. $\Psi$ sollte sinnvollerweise eine berechenbare Funktion sein. \end{frame}} \only{\begin{frame} Ein \Fb{Beweissystem} $(B,\Psi)$ für eine Formelmenge $A$ \pause besteht aus \begin{itemize}\item einer Menge $B$ von \Fb{Beweisen} \pause und \item einer \Fb{Interpretationsfunktion} $\Psi: B \rightarrow A$. \end{itemize} \pause Ein Beweis $b\in B$ ist eine Zeichenkette über einem Alphabet $E$,\pause \begin{itemize} \item die nach gewissen syntaktischen Regeln und Schlussschemata aufgebaut sein muss; \pause\\ \emph{diese inhaltlichen Zusammenhänge brauchen wir hier nicht!!!}\pause \item statt dessen als Minimalforderung: \pause\\die Menge der Beweise $B$ sei \emph{entscheidbar} ; \pause man sollte einer Zeichenkette ansehen können, ob sie ein Beweis ist oder nicht. \end{itemize} \pause Au"serdem: \pause\begin{itemize} \item aus einem Beweis $b$ sollte man die bewiesene Aussage $y\in A$ herauslesen können\pause \item Dazu: Interpretationsfunktion $\Psi $ mit Definitionsbereich $B$,\pause \item $\Psi(b)=y$ bedeutet, dass $y$ durch $b\in B$ bewiesen wurde.\pause \item $\Psi$ sollte sinnvollerweise eine berechenbare Funktion sein. \end{itemize} \end{frame}} \only
{\begin{frame} Mit \[Bew(B, \Psi) = \{y\in E^* \mid \textrm{ es gibt }b\in B\textrm{ mit }\Psi(b) =y\}\] wird dann die Gesamtheit der durch $(B, \Psi)$ beweisbaren Formeln bezeichnet. Der folgende Satz ist eine Version des 'Gödelschen Unvollständigkeitssatzes': \begin{theorem}[Gödelscher Unvollständigkeitssatz] Für jedes Beweissystem $(B, \Psi)$ für wahre arithmetische Formeln gilt: Die Menge der wahren arithmetischen Formeln ist eine echte Obermenge der Menge $Bew(B, \Psi)$. \end{theorem} Beweis: Da die Menge $B $ der Beweise eines Beweissystems entscheidbar ist und die Funktion $\Psi$, die jedem Beweis die von ihm bewiesene Formel zuordnet, berechenbar ist, ist die Menge aller in diesem Beweissystem beweisbaren Formeln rekursiv aufzählbar. Wir hatten oben aber angemerkt, dass die Menge der wahren arithmetischen Formeln nicht rekursiv aufzählbar ist. Da wir annehmen, dass das Beweissystem korrekt ist, d.h. nur wahre arithmetische Formeln beweist, bleiben demnach wahre arithmetische Formeln übrig, die nicht beweisbar sind. \end{frame}} \only{\begin{frame} Die Menge aller durch $(B, \Psi)$ beweisbaren Formeln \pause ist \GLA Bew(B, \Psi) = \{y\in E^* \mid \textrm{ es gibt }b\in B\textrm{ mit }\Psi(b) =y\} \GLE\pause \begin{theorem}[Gödelscher Unvollständigkeitssatz]\pause Für jedes Beweissystem $(B, \Psi)$ für wahre arithmetische Formeln gilt:\pause Die Menge der wahren arithmetischen Formeln ist eine echte Obermenge der Menge $Bew(B, \Psi)$. \end{theorem} \pause Beweis: \pause \begin{itemize} \item Menge $B $ der Beweise entscheidbar\pause \item Interpretationsfunktion $\Psi$ berechenbar\pause \item damit $Bew(B, \Psi)$ rekursiv aufzählbar \pause \item jedoch: Menge der wahren arithmetischen Formeln ist nicht rekursiv aufzählbar \end{itemize} \pause Da das Beweissystem nur wahre arithmetische Formeln beweisen soll \pause('Korrektheit'), \pause gibt es wahre Formeln, die nicht beweisbar sind! \end{frame}}