\section{Der Gödelsche Satz}
\inhalta{7-13}
\begin{frame}
\only<article>{
 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<presentation>{
Informal: Zusammenhänge zwischen\pause\begin{itemize}
\item (Nicht)-Berechenbarkeit \pause
\item Beweisbarkeit in der Zahlentheorie 
\end{itemize}
}
\label{arithmetische Formeln}
\only<article>{
Die Menge der \Fb{arithmetischen Formeln} können wir als (kontextfreie) Sprache $\cal F$ über
folgendem Alphabet darstellen:}
\only<presentation>{
\pause Dazu: \Fb{arithmetische Formeln} \pause als (kontextfreie) Sprache $\cal F$ \pause über }
\[\{0,1,x,(,),+,*,=,\neg,\wedge,\vee,\exists,\forall\}\]
\only<article>{
Zunächst definierern wir die Menge  $\cal T$ aller Terme durch
}
\only<presentation>{
\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<article>{
Die Sprache $\cal F$ der \Fb{Formeln} wird dann definiert durch:
}
\only<presentation>{
\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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}}
