Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 8/latex
\setcounter{section}{8}
\zwischenueberschrift{Allgemeingültige Ausdrücke}
Es sei
\mathl{L^S}{} eine Sprache erster Stufe über einem Symbolalphabet $S$. Für einen Ausdruck
\mathl{\alpha \in L^S}{} und eine Interpretation $I$ haben wir in der letzten Vorlesung die Gültigkeit
\mathl{I \vDash \alpha}{} über den Aufbau der Sprache rekursiv definiert. Wie im aussagenlogischen Kontext führen wir semantische Tautologien über die Gültigkeit bei jeder Interpretation ein.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $\alpha$ ein
$S$-\definitionsverweis {Ausdruck}{}{}
in der Prädikatenlogik erster Stufe. Man nennt $\alpha$
\definitionswort {allgemeingültig}{}
\zusatzklammer {oder eine
\definitionswort {semantische Tautologie}{}} {} {,}
wenn er in jeder
$S$-\definitionsverweis {Interpretation}{}{}
$I$ gilt, also
\mathl{I \vDash \alpha}{} wahr ist.
}
Allgemeingültige Ausdrücke sind \stichwort {Tautologien} {} im semantischen Sinn. Wir werden später noch Tautologien im syntaktischen Sinn kennenlernen und die Übereinstimmung der beiden Konzepte zeigen
\zusatzklammer {Vollständigkeitssatz der Prädikatenlogik} {} {.}
Beispiele sind die Ausdrücke
\mathdisp {\forall x \forall y \forall z ((x=y \wedge y=z) \rightarrow x=z)} { }
oder
\mathdisp {(\forall x \alpha) \rightarrow \alpha} { }
\zusatzklammer {wobei $\alpha$ ein Ausdruck ist} {} {,}
siehe
Aufgabe 8.1.
Wenn man in eine aussagenlogische Tautologie für die Aussagenvariablen beliebige prädikatenlogische Ausdrücke einsetzt\zusatzfussnote {Insofern ist auch die Bezeichnung Aussagenvariable gerechtfertigt, da für sie prädikatenlogische Ausdrücke eingesetzt werden können} {.} {,}
so erhält man auch eine Tautologie im obigen Sinn, siehe
Aufgabe 8.3
\zusatzklammer {die entprechende syntaktische Version wird in
Lemma 10.2
behandelt} {} {.}
Beispielsweise erhält man aus der aussagenlogischen Tautologie
\mathdisp {\alpha \rightarrow { \left( \beta \rightarrow \alpha \right) }} { }
die prädikatenlogische Tautologie
\zusatzklammer {mit naheliegenden Zugehörigkeiten der Symbole} {} {}
\mathdisp {\forall x (fx = y) \rightarrow { \left( \exists u (Rgz u) \rightarrow \forall x (fx = y) \right) }} { , }
die aber keinen eigentlichen prädikatenlogischen Sachverhalt ausdrückt.
\zwischenueberschrift{Gültigkeit von Ausdrucksmengen}
Für eine Menge
\mathl{\Gamma \subseteq L^S}{} von Ausdrücken und einer $S$-Interpretation schreibt man
\mathl{I \vDash \Gamma}{,} wenn in $I$ jeder Ausdruck aus $\Gamma$ gilt. Man sagt, dass $I$ ein \stichwort {Modell} {} für $\Gamma$ ist. Eine $S$-Struktur heißt ein \stichwort {Modell} {} für $\Gamma$, wenn jede Variablenbelegung zu dieser Struktur eine Interpretation liefert, die ein Modell für $\Gamma$ ist.
Diese Sprechweise wird insbesondere für Axiomensysteme $\Gamma$ verwendet, die eine mathematisch wichtige Struktur festlegen. Die erfüllenden Modelle heißen dann so, wie der Definitionsname in der Definition lautet, die dieses Axiomensystem verwendet. Die Modelle nennt man im üblichen mathematischen Sprachgebrauch Beispiele für diejenige mathematische Struktur, die durch die Definition festgelegt wird.
\zwischenueberschrift{Axiomensysteme}
Grundsätzlich gibt es zwei Bedeutungen von Axiomensystemen. Einerseits wird ein Axiomensystem aufgestellt, um eine in einem gewissen Sinn vertraute Struktur präzise zu erfassen und ihre Eigenschaften aus den fixierten Grundeigenschaften zu folgern. Man spricht von einem \stichwort {intendierten Modell} {,} das durch das Aufstellen eines Axiomensystems mathematisch beschrieben werden soll. Die Axiome selbst werden dann durch die Gültigkeit im intendierten Modell gerechtfertigt und können nicht weiter hinterfragt werden. In diesem Sinne gibt es in der Geometrie die euklidische Axiome für die Ebene bzw. den Raum, oder die Dedekind-Peano-Axiome für die natürlichen Zahlen, die wir später behandeln werden, oder die Axiome für die reellen Zahlen, die man in der Analysis I einführt, oder die Axiome für die Mengenlehre \zusatzklammer {typischerweise Zermelo-Fraenkel mit Auswahlaxiom} {} {,} die eine Festlegung für den mengentheoretischen Rahmen der gesamten Mathematik bilden. Eine wichtige Fragestellung hierbei ist, ob die Axiome die Struktur eindeutig festlegen.
Andererseits kann man jede willkürliche Vorgabe einer Menge von Ausdrücken als ein Axiomensystem ansehen. Es gibt dann jeweils mehrere verschiedene Strukturen, die diese Axiome erfüllen. Ein Axiomensystem in diesem Sinn will nicht ein bestimmtes Modell charakterisieren, sondern abstrakte Eigenschaft, die in unterschiedlichen Kontexten auftreten, bereitstellen. Eigenschaften, die man aus den Axiomen erschließen kann, gelten dann für sämtliche Modelle, die die Axiome erfüllen. Die Ökonomie dieses mathematischen Ansatzes liegt eben darin, dass man Schlüsse nicht am Objekt durchführt, sondern abstrakt und allgemein. Wichtige Axiomensysteme sind die Axiome für Gruppen, Ringe, Körper, angeordnete Körper, Vektorräume, metrische Räume, topologische Räume, Maßräume, Mannigfaltigkeiten.
Wichtige Bewertungskriterien für beide Arten von Axiomensystemen sind. \aufzaehlungvier{Die Axiome sollen möglichst einfach formuliert sein. }{Die Axiome sollen möglichst einfach \zusatzklammer {in einem Modell} {} {} überprüfbar sein. }{Die Axiome sollen reichhaltige Folgerungen erlauben. }{Die Axiome eines Systems sollen untereinander unabhängig sein; es darf kein Axiom re\-dundant sein. }
Für uns stehen zunächst Axiomensysteme im zweiten Sinne im Mittelpunkt; grundsätzlich kann man jede Ausdrucksmenge
\mathl{\Gamma \subseteq L^S}{} als ein Axiomensystem auffassen. Als Beispiele betrachten wir aber nur mathematisch relevante Axiomensysteme. Um ein Axiomensystem prädikatenlogisch zu repräsentieren, muss man zuerst das Symbolalphabet und anschließend die Axiome festlegen. Betrachten wir beispielsweise die mathematische Definition einer Gruppe.
\inputdefinition
{
}
{
Eine Menge $G$ mit einem ausgezeichneten Element
\mavergleichskette
{\vergleichskette
{e
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und mit einer
\definitionsverweis {Verknüpfung}{}{}
\maabbeledisp {} {G \times G} {G
} {(g,h)} { g * h
} {,}
heißt
\definitionswort {Gruppe}{,}
wenn folgende Eigenschaften erfüllt sind.
\aufzaehlungdrei{Die Verknüpfung ist \stichwort {assoziativ} {,} d.h. für alle
\mavergleichskette
{\vergleichskette
{ f,g,h
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskettedisp
{\vergleichskette
{ (f * g) * h
}
{ =} { f * (g * h)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Das Element $e$ ist ein \stichwort {neutrales Element} {,} d.h. für alle
\mavergleichskette
{\vergleichskette
{g
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskettedisp
{\vergleichskette
{ g * e
}
{ =} { g
}
{ =} { e * g
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Zu jedem
\mavergleichskette
{\vergleichskette
{g
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es ein \stichwort {inverses Element} {,} d.h. es gibt ein
\mavergleichskette
{\vergleichskette
{h
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ h * g
}
{ =} { g * h
}
{ =} { e
}
{ } {
}
{ } {
}
}
{}{}{.}
}
}
In formal-prädikatenlogischer Formulierung besteht das Symbolalphabet
\zusatzklammer {neben den Variablen} {} {}
aus einer Konstanten $e$ und aus einem zweistelligen Funktionssymbol $\mu$. Die in der Gruppendefinition auftretenden Axiome
\zusatzklammer {die Gruppenaxiome, also die drei auftretenden Bedingungen} {} {}
kann man mit diesen Symbolen einfach schreiben als
\aufzaehlungdrei{
\mathdisp {\forall x (\forall y (\forall z \, \mu x \mu y z = \mu \mu x y z))} { . }
}{
\mathdisp {\forall x (\mu x e = x \wedge \mu e x = x )} { . }
}{
\mathdisp {\forall x \exists y (\mu x y = e \wedge \mu y x = e)} { . }
}
Nennen wir diese drei Ausdrücke zusammen $\Gamma$. Dann ist eine Gruppe eine Menge $G$ mit einer Interpretation $I$ für $e$ und für $\mu$, d.h. es muss ein ausgezeichnetes Element $e^G$
\zusatzklammer {häufig schreibt man $e_G$ oder $e$} {} {}
geben und eine zweistellige Funktion auf $G$
\zusatzklammer {eine Verknüpfung} {} {,}
derart, dass
\mathl{I \vDash \Gamma}{} gilt. Eine Gruppe ist also ein Modell für $\Gamma$.
Als weiteres Beispiel wiederholen wir die Definition der Ordnungsrelation, die wir in der fünften Vorlesung behandelt haben.
Eine
\definitionsverweis {Relation}{}{}
$\preccurlyeq$ auf einer Menge $I$ heißt \definitionswort {Ordnungsrelation}{} oder \definitionswort {Ordnung}{,} wenn folgende drei Bedingungen erfüllt sind.
\aufzaehlungdrei{Es ist
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt stets
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{i
}
{ = }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Neben den Variablen besteht das zugehörige Symbolalphabet allein aus einem zweistelligen Relationssymbol, das wir ebenfalls mit $\preccurlyeq$ bezeichnen. Die für eine Ordnung verlangten Eigenschaften führen zu dem folgenden Axiomensystem $\Gamma$.
\aufzaehlungdrei{
\mathdisp {\forall x (x \preccurlyeq x)} { . }
}{
\mathdisp {\forall x \forall y \forall z ( x \preccurlyeq y \wedge y \preccurlyeq z \rightarrow x \preccurlyeq z)} { . }
}{
\mathdisp {\forall x \forall y ( x \preccurlyeq y \wedge y \preccurlyeq x \rightarrow x = y)} { . }
}
In einer Menge $M$ mit einer zweistelligen Relation $R$ gilt das Axiomensystem $\Gamma$ genau dann, wenn die Relation eine Ordnungsrelation ist. Eine geordnete Menge ist also ein Modell für $\Gamma$.
\zwischenueberschrift{Die Folgerungsbeziehung}
Mit Axiomensystemen verbindet man die Vorstellung, dass daraus \anfuehrung{wichtige}{} weitere Eigenschaften beweisbar sind. In einer jeden Gruppe gelten nicht nur die Gruppenaxiome, sondern auch alle Gesetzmäßigkeiten, die man aus den Gruppenaxiomen folgern kann. Dies wird in der mathematischen Logik durch den Folgerungsbegriff präzisiert.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
erster Stufe, $\Gamma$ eine Menge von
$S$-\definitionsverweis {Ausdrücken}{}{}
und $\alpha$ ein $S$-Ausdruck. Man sagt, dass $\alpha$ aus $\Gamma$
\definitionswort {folgt}{,}
geschrieben
\mathl{\Gamma \vDash \alpha}{,} wenn für jede
$S$-\definitionsverweis {Interpretation}{}{}
$I$ mit
\mathl{I \vDash \Gamma}{} auch
\mathl{I \vDash \alpha}{} gilt.
}
Die Folgerungsbeziehung verwendet also \zusatzklammer {wie schon im aussagenlogischen Kontext} {} {} das gleiche Symbol wie die Gültigkeitsbeziehung. Dass aus einer gewissen Ausdrucksmenge $\Gamma$ ein gewisser Ausdruck $\alpha$ folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit gewissen zusätzlichen Strukturen, die $\Gamma$ erfüllt, stets auch $\alpha$ erfüllen muss.
\inputbeispiel{}
{
In einer
\definitionsverweis {Gruppe}{}{}
ist das inverse Element zu einem jeden Element, das es aufgrund der Definition einer Gruppe geben muss, eindeutig bestimmt. Mathematisch wird dies so bewiesen: Es sei $e$ das neutrale Element der Gruppe, sei
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorgegeben und seien
\mavergleichskette
{\vergleichskette
{y,z
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
inverse Elemente zu $x$, d.h. es gelte
\mavergleichskette
{\vergleichskette
{yx
}
{ = }{xy
}
{ = }{e
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{zx
}
{ = }{xz
}
{ = }{e
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist insgesamt
\mavergleichskettedisp
{\vergleichskette
{ y
}
{ =} {y e
}
{ =} { y (xz)
}
{ =} { (yx) z
}
{ =} { ez
}
}
{
\vergleichskettefortsetzung
{ =} {z
}
{ } {}
{ } {}
{ } {}
}{}{.}
Die Eindeutigkeit des inversen Elementes kann man mit den Symbolen
\mathl{\{e, \mu\}}{,} wobei $e$ eine Konstante und $\mu$ ein zweistelliges Funktionssymbol ist, als den Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ \defeq} { \forall x ( \forall y ( \forall z ( \mu yx = e \wedge \mu xy = e \wedge \mu zx = e \wedge \mu xz = e \rightarrow y = z )))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ansetzen, und die obige mathematische Argumentation bedeutet, dass der Ausdruck $\alpha$ aus den Gruppenaxiomen $\Gamma$ folgt, also die Folgerungsbeziehung
\mathdisp {\Gamma \vDash \alpha} { }
vorliegt.
}
Da ein allgemeingültiger Ausdruck $\alpha$ in jeder Interpretation gilt, kann man auch sagen, dass $\alpha$ aus der leeren Ausdrucksmenge folgt, also
\mathl{\emptyset \vDash \alpha}{} gilt. Wenn
\mathl{\alpha_1,\alpha_2,\alpha_3}{} die Gruppenaxiome sind, und $\alpha$ die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das inverse Element ist, so ist auch
\mathdisp {\alpha_1 \wedge \alpha_2 \wedge \alpha_3 \rightarrow \alpha} { }
allgemeingültig.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und es sei $\alpha$ ein
$S$-\definitionsverweis {Ausdruck}{}{}
in der Prädikatenlogik erster Stufe. Man nennt $\alpha$
\definitionswort {erfüllbar}{,}
wenn es eine
$S$-\definitionsverweis {Interpretation}{}{}
$I$ mit
\mathl{I \vDash \alpha}{} gibt.
}
Für eine Ausdrucksmenge $\Gamma$ bedeutet die Erfüllbarkeit, dass die darin enthaltenen Ausdrücke simultan in einer Interpretation erfüllbar sind. Zwischen Allgemeingültigkeit und Erfüllbarkeit besteht die Beziehung, dass $\alpha$ genau dann allgemeingültig ist, wenn die Negation
\mathl{\neg \alpha}{} nicht erfüllbar ist.
Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.
{Prädikatenlogik/Folgerung/Unerfüllbarkeit/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Es gilt
\mathl{\Gamma \vDash \alpha}{} genau dann, wenn
\mathl{\Gamma \cup \{\neg \alpha\}}{} nicht
\definitionsverweis {erfüllbar}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 8.12. }
\zwischenueberschrift{Sortenprädikate}
Bei vielen mathematischen Strukturen bewegen sich die Objekte, über die quantifiziert werden soll, nicht in einer einzigen Menge, sondern in mehreren. Beispielsweise interessiert man sich nicht nur für Abbildungen von einer Menge in sich selbst, sondern auch für Abbildungen zwischen zwei Mengen. Bei einem Vektorraum wird ein Körper zugrunde gelegt, aus dem die \anfuehrung{Skalare}{} herrühren, während die Vektoren aus dem Vektorraum sind; die Axiome eines Vektorraums nehmen Bezug auf beide Arten. Bei einem metrischen Raum ist der Abstand zwischen zwei Punkten des Raumes eine reelle Zahl bzw. ein Element in einem angeordneten Körper. Man spricht von verschiedenen \anfuehrung{Sorten}{}
\zusatzklammer {von Termen, von Objekten} {} {.}
Solche mathematische Strukturen lassen sich ebenfalls mit der Sprache erster Stufe beschreiben, wobei man einen einfachen Kniff anwendet, der von der mathematischen Praxis her etwas künstlich wirkt. Man wirft die Mengen zunächst zusammen und führt dann für jede Sorte ein \stichwort {Sortenprädikat} {} ein, um sie wieder trennen zu können. Ein Sortenprädikat ist eine einstellige Relation, und
\mathl{Pt}{} bedeutet inhaltlich gesprochen, dass der Term $t$ zur Sorte gehört, die durch $P$ repräsentiert wird. Wir erläutern dieses Vorgehen an zwei Beispielen.
\inputbeispiel{}
{
Eine angemessene prädikatenlogische Formulierung für Abbildungen zwischen zwei Mengen wird durch das Symbolalphabet beschrieben, das neben Variablen aus
\mathl{\{ F,D,Z\}}{} besteht, wobei $F$ ein einstelliges Funktionssymbol und $D$
\zusatzklammer {für \anfuehrung{Definitionsbereich}{}} {} {}
und $Z$
\zusatzklammer {für \anfuehrung{Zielbereich}{}} {} {}
zwei einstellige Relationssymbole sind, mit denen man den Definitionsbereich und den Zielbereich einer Abbildung erfassen möchte. Bei Interpretation in einer Menge $M$ ist die Funktion
\mavergleichskette
{\vergleichskette
{f
}
{ = }{F^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zwar auf jedes Element aus $M$ anwendbar, man kann aber relevante Eigenschaften einer Abbildung
spezifisch für die durch
\mathkor {} {D} {bzw.} {Z} {}
bestimmten Teilmengen
\zusatzklammer {den Definitionsbereich bzw. Zielbereich} {} {}
formulieren. Beispielsweise besagt der Ausdruck
\mathdisp {\forall x (Dx \rightarrow Zfx)} { , }
dass für jedes $x$, das zum Definitionsbereich gehört, der Funktionswert zu $Z$ gehören muss. Die Surjektivität
\zusatzklammer {als Abbildung von der durch $D$ beschriebenen Menge, also \mathlk{D^M}{,} in die durch $Z$ beschriebene Menge, also \mathlk{Z^M}{}} {} {}
wird durch
\mathdisp {\forall y { \left( Zy \rightarrow \exists x { \left( Dx \wedge fx = y \right) } \right) }} { }
beschrieben.
}
\inputbeispiel{}
{
Eine angemessene prädikatenlogische Formulierung für Vektorräume wird neben Variablen durch
\mathdisp {\{0_K,1,+_K, \cdot_K, 0_V, +_V,\cdot, K,V\}} { }
beschrieben, wobei $\{0_K,1,0_V\}$ Konstanten,
\mathl{\{+_K,\cdot_K,+_V, \cdot \}}{} zweistellige Funktionssymbole und $K$
\zusatzklammer {für Körper} {} {}
und $V$
\zusatzklammer {für Vektorraum} {} {}
zwei einstellige Relationssymbole sind, mit denen man den Körper und den Vektorraum erfassen möchte. Die grundlegende Skalarmultiplikation wird durch
\mathdisp {\forall x \forall y { \left( Kx \wedge Vy \rightarrow V x \cdot y \right) }} { }
beschrieben, die beiden Distributivgesetze durch
\mathdisp {\forall x \forall y \forall z { \left( Kx \wedge Ky \wedge Vz \rightarrow { \left( x +_K y \right) } \cdot z = { \left( { \left( x \cdot z \right) } +_V { \left( y \cdot z \right) } \right) } \right) }} { }
und
\mathdisp {\forall x \forall y \forall z { \left( Kx \wedge Vy \wedge Vz \rightarrow x \cdot { \left( y +_V z \right) } = { \left( x \cdot y \right) } +_V { \left( x \cdot z \right) } \right) }} { . }
}