% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}
\usepackage{listings}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 30
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die drei\ss{}igste Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Hinweis: Autoren sind f\"{u}r den Inhalt ihrer Artikel oder Werke selbst verantwortlich. Die in MATHEMATIQ ver\"{o}ffentlichten Beitr\"{a}ge widerspiegeln ausschlie\ss{}lich die Meinung ihrer Autoren und nicht jene des Vereins Mensa. Die Zusendung von Beitr\"{a}gen gilt auch als Einverst\"{a}ndnis zu deren Ver\"{o}ffentlichung in MATHEMATIQ.}
\\
\\ \textbf{Diese Ausgabe} behandelt nochmals die G\"{o}delschen Unvollst\"{a}ndigkeitss\"{a}tze.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{G\"{o}dels Unvollst\"{a}ndigkeitss\"{a}tze einfach erkl\"{a}rt}
\end{center}
\normalsize In den ersten Ausgaben von MATHEMATIQ habe ich \"{u}ber die Theorie der formalen Sprachen und G\"{o}dels Unvollst\"{a}ndigkeitss\"{a}tze geschrieben. Dabei habe ich gezeigt, wie G\"{o}dels S\"{a}tze logisch aus der Theorie der formalen Sprachen hergeleitet werden k\"{o}nnen. Wenngleich die Gedankeng\"{a}nge richtig sind, ist die Formulierung vielleicht f\"{u}r manche Leser zu knapp geraten, um von ihnen nachvollzogen zu werden. Deswegen versuche ich es noch einmal in leichter verst\"{a}ndlicher Sprache.
\\
\\ Der gro\ss{}e Mathematiker David Hilbert hatte in einem Mathematikerkongress zu Beginn des 20. Jahrhunderts gefordert, die mathematische Zunft m\"{o}ge sich bem\"{u}hen, ein logisch konsistentes und vollst\"{a}ndiges Axiomensystem zu entwickeln, aus dem die gesamte Mathematik hergeleitet werden k\"{o}nne. Kurt G\"{o}dels Leistung bestand haupts\"{a}chlich darin zu zeigen, dass es gar nicht m\"{o}glich ist, dieses Vorhaben zu realisieren, weil ein formales System nicht logisch konsistent und zugleich vollst\"{a}ndig sein kann (Erster Unvollst\"{a}ndigkeitssatz).
\\
\\ Computerprogramme, die Entscheidungsprobleme l\"{o}sen, sind formale Systeme im G\"{o}delschen Sinn, und jedes formale System im G\"{o}delschen Sinn kann durch ein Computerprogramm beschrieben werden. F\"{u}r einen modernen Menschen mag G\"{o}dels Satz daher leichter verst\"{a}ndlich sein, wenn er sich ein Computerprogramm denkt, das man mit mathematischen Aussagen f\"{u}ttern kann. Dieses Computerprogramm kann nur zwei m\"{o}gliche Ausgaben liefern: ``wahr'' oder ``falsch''. Ein logisch konsistentes Computerprogramm d\"{u}rfte nur dann ``wahr'' ausgeben, wenn die mathematische Aussage, die ihm als Parameter \"{u}bergeben worden ist, tats\"{a}chlich wahr ist, und ``falsch'' auch nur, wenn die Aussage tats\"{a}chlich falsch ist. Wenn die mathematische Aussage aber weder wahr noch falsch, sondern paradox ist, d\"{u}rfte das logisch konsistente Computerprogramm gar nichts ausgeben. Es w\"{u}rde also gar nicht terminieren, sondern in eine Endlosschleife geraten, sich ``aufh\"{a}ngen'', wie man umgangssprachlich sagt. Damit w\"{a}re dieses Computerprogramm aber nicht vollst\"{a}ndig. Ein vollst\"{a}ndiges Computerprogramm w\"{u}rde immer terminieren, egal mit welcher Eingabe man es f\"{u}tterte. Es m\"{u}sste also auch paradoxe Aussagen entweder als ``wahr'' oder als ``falsch'' klassifizieren, obwohl keine der beiden Alternativen zutrifft. Ein vollst\"{a}ndiges Computerprogramm w\"{a}re also gezwungen, in einigen F\"{a}llen zu ``l\"{u}gen'' - und w\"{a}re damit nicht logisch konsistent.
\\
\\ Ein Beispiel f\"{u}r eine paradoxe Aussage lautet: ``Dieser Satz ist falsch.'' Wenn man annimmt, dass der Satz wahr ist, dann sagt er \"{u}ber sich selbst aus, dass er falsch ist. Somit kann er nicht wahr sein. Nimmt man aber an, dass er falsch ist, dann folgt, dass er wahr sein muss. Somit kann er nicht falsch sein. Nun mag man vielleicht sagen, das sei eine sprachliche Aussage, keine mathematische, aber im Prinzip sind auch sprachliche Aussagen dieser Art mathematische Aussagen. Au\ss{}erdem hat Kurt G\"{o}del einen Formalismus entwickelt, mit dem er zeigen konnte, dass auch in der Mathematik im engeren Sinn solch paradoxe Aussagen auftreten k\"{o}nnen.
\\
\\ Das w\"{a}re der erste Unvollst\"{a}ndigkeitssatz gewesen. Der zweite besagt, dass ein logisch konsistentes System nicht in der Lage ist, seine eigene logische Konsistenz zu beweisen. Wie beweist man diese Aussage? Man stelle sich ein logisch konsistentes Computerprogramm vor, also eines, das in dem Fall, dass es nicht imstande ist zu sagen, ob die Aussage, die ihm als Parameter \"{u}bergeben worden ist, wahr oder falsch sei, ``ehrlich'' ist und die Konsequenzen zieht, also sich ``aufh\"{a}ngt''. Wie sollte ein solches Programm beweisen, dass es ``ehrlich'' ist? Es gibt nur eine einzige M\"{o}glichkeit: sich selbst mit einem Parameter aufzurufen, der dazu f\"{u}hrt, dass sich das Programm ``aufh\"{a}ngt''. Das Programm ist jedoch nicht in der Lage festzustellen, dass sich die von ihm aufgerufene Instanz seiner selbst aufgeh\"{a}ngt hat! Somit kann es in diesem Fall auch selbst nicht terminieren.
\\
\\ Ich hoffe, die G\"{o}delschen Unvollst\"{a}ndigkeitss\"{a}tze nun nachvollziehbar erkl\"{a}rt zu haben.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
