nach oben

2010 | Buch

Kapitel lesen Erstes Kapitel lesen

Mathematische Logik

verfasst von: Martin Ziegler

Verlag: Birkhäuser Basel

Buchreihe : Mathematik Kompakt

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Ü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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

φ(x₁,…, x_n) ist genau dann allgemeingültig, wenn die Aussage ∀x₁,…, x_n φ(x₁,…, x_n) allgemeingültig ist.

Martin Ziegler

■ 4. Der Gödelsche Vollständigkeitssatz

Zusammenfassung

Das Ziel dieses Abschnitts ist es, den Gödelschen¹² Vollständigkeitssatz zu beweisen.

Martin Ziegler

■ 5. Der Sequenzenkalkül

Zusammenfassung

Der von Gentzen²⁰ aufgestellte Sequenzenkalkül hat gegenüber dem Hilbertschen Kalkül die folgenden Vorteile.

Martin Ziegler

■ 6. Der Herbrandsche Satz

Zusammenfassung

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 ∀x₁…∀x_n äquivalent zur existentiellen Formel ∃x₁…∃x_n¬ϕ ist. Die Negation einer existentiellen Formel ist äquivalent zu einer universellen Formel.

Martin Ziegler

■ 7. Die Resolutionsmethode

Zusammenfassung

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 2^{Zahl 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

Zusammenfassung

Die Sprache der Mengenlehre ist L_Me=ε. Man liest „xεy“ als x ist Element von y.

Martin Ziegler

■ 9. Die natürlichen Zahlen

Zusammenfassung

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

Zusammenfassung

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

Martin Ziegler

■ 11. Metamathematik von ZFC

Zusammenfassung

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 ψ=ζ₀ζ₁…ζ_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

Zusammenfassung

Eine Registermaschine M arbeitet mit endlichen vielen Registern R₀,..., R_R-1, in denen Wörter aus einem endlichen Alphabet A={a₁,...,a_L} stehen. Die Maschine kann den letzten Buchstaben dieser Wörter lesen, den letzten Buchstaben streichen oder einen Buchstaben anhängen¹. Das Programm von M ist eine Folge (b₀,…, b_N) von Befehlen der folgenden Art.

Martin Ziegler

■ 13. Primitiv rekursive Funktionen und Gödelisierung

Zusammenfassung

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

Zusammenfassung

Insbesondere sind rekursive Relationen rekursiv aufzählbar.

Martin Ziegler

■ 15. Gödelnummern von Formeln

Zusammenfassung

Sei L={λ₁,…, λ_l} eine endliche Sprache⁶. 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 φ=ζ₁ζ₂…ζ hat die Gödelnummer⁷

$$ \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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

Die Axiome der Peanoarithmetik⁴ 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

Zusammenfassung

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

Titel: Mathematische Logik
verfasst von: Martin Ziegler
Verlag: Birkhäuser Basel
Electronic ISBN: 978-3-0346-0652-3
Print ISBN: 978-3-7643-9973-3
DOI: https://doi.org/10.1007/978-3-0346-0652-3