Skip to main content
main-content

Über dieses Buch

Dieses Buch bietet eine Einführung in die verschiedenen Aspekte der mathematischen Logik, die jeder Mathematiker und Informatiker kennen sollte. Nach dem Prädikatenkalkül und seinen Anwendungen auf die Anfänge der künstlichen Intelligenz wird die Mengenlehre axiomatisch dargestellt. Im dritten und vierten Teil werden die notwendigen Grundbegriffe der Berechenbarkeitstheorie und die Hierarchie der in den natürlichen Zahlen definierbaren Teilmengen eingeführt, um schließlich die Gödelschen Unvollständigkeitssätze zu beweisen. Durch seinen klaren Stil und die eingefügten Übungsaufgaben ist dieses Buch eine konzise Einführung in diese Grundlagen der gesamten Mathematik.

Inhaltsverzeichnis

Frontmatter

Prädikatenkalkül

Frontmatter

■ 1. Strukturen und Formeln

Eine Struktur ist eine nicht-leere Menge mit ausgezeichneten Elementen, Operationen und Relationen. Zum Beispiel
$$ \begin{gathered} ein Ring: (R, 0, 1, + , - , \cdot ) \hfill \\ eine Gruppe: (G, e, ^\circ ,^{ - 1} ) \hfill \\ die reellen Zahlen (\mathbb{R}, 0, 1, + , - , \cdot , < ) \hfill \\ die nat\& \# x00FC;tlichen Zahlen \mathfrak{N} = (\mathbb{N}, 0, S, + , \cdot , < ) \hfill \\ (S ist Nachfolgeroperation x \mapsto x + 1.) \hfill \\ \end{gathered} $$
Martin Ziegler

■ 2. Semantik

Ein L-Term t hat erst dann einenWert in einer L-Struktur,wenn man die Variablen von t durch Elemente von A belegt.
Martin Ziegler

■ 3. Allgemeingültige Formeln

φ(x1,…, x n ) ist genau dann allgemeingültig, wenn die Aussage ∀x1,…, x n φ(x1,…, x n ) allgemeingültig ist.
Martin Ziegler

■ 4. Der Gödelsche Vollständigkeitssatz

Das Ziel dieses Abschnitts ist es, den Gödelschen12 Vollständigkeitssatz zu beweisen.
Martin Ziegler

■ 5. Der Sequenzenkalkül

Der von Gentzen20 aufgestellte Sequenzenkalkül hat gegenüber dem Hilbertschen Kalkül die folgenden Vorteile.
Martin Ziegler

■ 6. Der Herbrandsche Satz

Zwei Formeln φ und heißen äquivalent, wenn sie in allen Strukturen auf die gleichen Elemente zutreffen, oder anders gesagt, wenn φ↔ϕ allgemeingültig ist. Man sieht nun, daß die Negation einer universellen Formel ∀x1…∀x n äquivalent zur existentiellen Formel ∃x1…∃x n ¬ϕ ist. Die Negation einer existentiellen Formel ist äquivalent zu einer universellen Formel.
Martin Ziegler

■ 7. Die Resolutionsmethode

Die Allgemeingültigkeit einer aussagenlogischen Formel f läßt sich feststellen, indem man überprüft, daß es keine Belegung der Variablen von f den Wahrheitswert Wergibt. Weil es 2Zahl der Variablen viele Belegungen gibt, ist dieses Verfahren f ür große Formeln nicht praktikabel. Ob es überhaupt ein Verfahren zur überprüfung der Allgemeingültigkeit aussagenlogischer Formeln gibt, dessen Schrittzahl durch ein Polynomin der Zahl der Variablen beschränkt ist, ist äquivalent zum P=NP Problem der Informatik, das bis heute ungelöst ist. Siehe dazu [5].
Martin Ziegler

Mengenlehre

Frontmatter

■ 8. Die Axiome

Die Sprache der Mengenlehre ist L Me =ε. Man liest „xεy“ als x ist Element von y.
Martin Ziegler

■ 9. Die natürlichen Zahlen

Die rekursive Definition
$$ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{n} = \{ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{1} , \ldots ,\underline {n - 1} \} $$
ordnet jeder natürlichen Zahl n eine Menge n zu. Es ist zum Beispiel
$$ \begin{gathered} \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} = \O \hfill \\ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{1} = \{ \O \} \hfill \\ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} = \{ \O , \{ \O \} \} \hfill \\ \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{3} = \{ \O , \{ \O \} , \{ \O , \{ \O \} \} \} . \hfill \\ \end{gathered} $$
Martin Ziegler

■ 10. Ordinalzahlen und Kardinalzahlen

Alle natürlichen Zahlen und ω selbst sind Ordinalzahlen. Wir bezeichnen mit On die Klasse der Ordinalzahlen.
Martin Ziegler

■ 11. Metamathematik von ZFC

Wir ordnen jeder L Me -Formel ψ eine Konstante ⌜ψ⌝ in einer definitorischen Erweiterung von ZFCzu (siehe Satz 8.1).Zunächst ordnen wir allen Zeichen einen Termzu:
$$ \begin{gathered} \left\lceil {\dot = } \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ) \hfill \\ \left\lceil \wedge \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ) \hfill \\ \left\lceil \neg \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} ) \hfill \\ \left\lceil ( \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{3} ) \hfill \\ \left\lceil ) \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{4} ) \hfill \\ \left\lceil \exists \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{5} ) \hfill \\ \left\lceil \varepsilon \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{6} ) \hfill \\ \left\lceil {\nu _0 } \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{1} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ) \hfill \\ \left\lceil {\nu _1 } \right\rceil = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{1} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{1} ) \hfill \\ \ldots = \ldots \hfill \\ \end{gathered} $$
Für eine Formel ψ=ζ0ζ1…ζn−1 der Länge n setzen wir
$$ \left\lceil \psi \right\rceil = \left\{ {(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ,\left\lceil {\zeta _0 } \right\rceil ), \ldots ,(\underline {n - 1,} \left\lceil {\zeta _{n - 1} } \right\rceil )} \right\}. $$
Martin Ziegler

Rekursionstheorie

Frontmatter

■ 12. Registermaschinen

Eine Registermaschine M arbeitet mit endlichen vielen Registern R0,..., R R-1 , in denen Wörter aus einem endlichen Alphabet A={a1,...,a L } stehen. Die Maschine kann den letzten Buchstaben dieser Wörter lesen, den letzten Buchstaben streichen oder einen Buchstaben anhängen1. Das Programm von M ist eine Folge (b0,…, b N ) von Befehlen der folgenden Art.
Martin Ziegler

■ 13. Primitiv rekursive Funktionen und Gödelisierung

Dabei ist
$$ x\dot - y = \left\{ {_{0 sonst}^{x - y wenn y \leqslant x} } \right.. $$
Beweis. x+y läßt sich, wie die anderen Funktionen, leicht durch primitive Rekursion definieren:
$$ x + 0 = x, x + (y + 1) = S(x + y). $$
Martin Ziegler

■ 14. Rekursiv aufzählbare Mengen

Insbesondere sind rekursive Relationen rekursiv aufzählbar.
Martin Ziegler

■ 15. Gödelnummern von Formeln

Sei L={λ1,…, λl} eine endliche Sprache6. Wir ordnen den Zeichen ζ
$$ _{\lambda _1 \ldots \lambda _1 \nu _0 \nu _1 \ldots }^{\dot = \wedge \neg ( ) \exists } $$
die folgenden Gödelnummern ⌜ζ⌝ zu:
$$ \begin{gathered} \left\langle {0, 0} \right\rangle \left\langle {0, 1} \right\rangle \left\langle {0, 2} \right\rangle \left\langle {0, 3} \right\rangle \left\langle {0, 4} \right\rangle \left\langle {0, 5} \right\rangle \hfill \\ \left\langle {0, 6} \right\rangle \ldots \left\langle {0, l + 5} \right\rangle \left\langle {1, 0} \right\rangle \left\langle {1, 0} \right\rangle \ldots \hfill \\ \end{gathered} $$
Eine Zeichenreihe φ=ζ1ζ2…ζ hat die Gödelnummer7
$$ \left\lceil \phi \right\rceil = \left\langle {\left\lceil {\zeta _1 } \right\rceil ,\left\lceil {\zeta _2 } \right\rceil , \ldots ,\left\lceil {\zeta _n } \right\rceil } \right\rangle . $$
Martin Ziegler

■ 16. Ein anderer Aufbau der rekursiven Funktionen

Wir werden den Satz im Rest dieses Abschnitts beweisen. Funktionen, die wie in Satz 16.1 aufgebaut sind, nennen wir *-rekursiv. Wenn wir zeigen können, daß die Klasse der *-rekursiven Funktionen abgeschlossen ist unter primitiver Rekursion (Regel R2), sind wir fertig.
Martin Ziegler

Arithmetik

Frontmatter

■ 17. Definierbare Relationen

Das bedeutet, daß für eine L N -Formel φ
$$ R(a_1 , \ldots ,a_n ) \Leftrightarrow \mathfrak{N} \vDash \phi [a_1 , \ldots ,a_n ]. $$
Eine Funktion f heißt arithmetisch, wenn ihr Graph arithmetisch ist:
$$ f(a_1 , \ldots ,a_n ) = a_0 \Leftrightarrow \mathfrak{N} \vDash \phi _f [a_0 , \ldots ,a_n ]. $$
Martin Ziegler

■ 18. Das System Q

Die Axiome des Systems Q sind
$$ \begin{gathered} Q1{\text{ }}\forall x{\text{ }}x + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} \dot = x \hfill \\ Q2{\text{ }}\forall x,{\text{ }}y x + S(y)\dot = S(x + y) \hfill \\ Q3{\text{ }}\forall x{\text{ }}x \cdot \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} \dot = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} \hfill \\ Q4{\text{ }}\forall x,{\text{ }}y x \cdot S(y)\dot = x \cdot y + x \hfill \\ Q5{\text{ }}\forall x{\text{ }}\neg x < \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} \hfill \\ Q6{\text{ }}\forall x,{\text{ }}y x < S(y) \leftrightarrow (x\dot = y \vee x < y). \hfill \\ \end{gathered} $$
Martin Ziegler

■ 19. Peanoarithmetik

Die Axiome der Peanoarithmetik4 P sind die Axiome von Q und das Induktionsschema:
$$ \forall x_1 , \ldots ,x_n \left[ {\left( {\phi (\bar x,0){\text{ }} \wedge {\text{ }}\forall y(\phi (\bar x,y) \to \phi (\bar x,{\text{ }}S(y))} \right) \to \forall y\phi (\bar x,y)} \right] $$
Ein Modell von Q ist genau dann ein Modell von P, wenn jede definierbare Menge von Elementen, die 0 enthält und unter S abgeschlossen ist, alle Elemente enthält. Insbesondere sind die natürlichen Zahlen ein Modell von P.
Martin Ziegler

■ 20. Der Zweite Gödelsche Unvollständigkeitssatz

Wir beginnen mit einer allgemeinen Beobachtung. Wir sagen, daß eine Formel
$$ \phi = \phi (\bar x) $$
logisch aus T folgt, wenn
$$ \forall \bar x\phi $$
in allen Modellen von T gilt (vergleiche die Definition auf Seite 23.)
Martin Ziegler

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise