Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 7/latex
\setcounter{section}{7}
\zwischenueberschrift{Sprachen erster Sufe}
Die in der letzten Vorlesung erwähnten Konstruktionsmöglichkeiten für Aussagen sind im Wesentlichen schon erschöpfend. Mit ihnen kann man ausgehend von einer Grundtermmenge formale Sprachen aufbauen, deren Aussagekraft prinzipiell groß genug ist, um die gesamte Mathematik auszudrücken \zusatzklammer {für viele Bereiche wäre es aber künstlich, sich auf diese Sprachen zu beschränken} {} {.} Diese formalen Sprachen nennt man \stichwort {Sprachen erster Stufe} {,} deren syntaktischen Aufbau wir hier beschreiben. Wir beginnen mit den zugehörigen Alphabeten.
\inputdefinition
{}
{
Ein
\definitionswort {Alphabet einer Sprache erster Stufe}{}
umfasst die folgenden Daten.
\aufzaehlungsechs{Eine
\definitionsverweis {Grundtermmenge}{}{,}
also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
}{Zu jeder natürlichen Zahl
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Menge $R_n$ von $n$-stelligen Relationssymbolen.
}{Die aussagenlogischen Junktoren
\mathdisp {\neg, \, \wedge, \, \vee, \, \rightarrow , \, \leftrightarrow} { . }
}{Das Gleichheitszeichen
\mathl{=}{.}
}{Die Quantoren
\mathkor {} {\forall} {und} {\exists} {.}
}{Klammern, also $($ und $)$.
}
}
Die aussagenlogischen Junktoren werden als \stichwort {Negation} {,} \stichwort {Konjunktion} {}
\zusatzklammer {und} {} {,}
\stichwort {Disjunktion} {}
\zusatzklammer {\stichwort {Alteration} {}, einschließliches Oder} {} {,}
\stichwort {Implikation} {}
\zusatzklammer {wenn, dann} {} {}
und \stichwort {Äquivalenz} {}
\zusatzklammer {genau dann, wenn} {} {}
bezeichnet. Der Quantor $\forall$ heißt \stichwort {Allquantor} {} und $\exists$ heißt \stichwort {Existenzquantor} {.} Diese Liste ist etwas redundant, da man, von der späteren Interpretation her gesehen, einige aussagenlogische Junktoren durch andere ersetzen kann, beispielsweise ist für zwei Aussagen
\mathkor {} {\alpha} {und} {\beta} {}
die Aussage
\mathl{\alpha \rightarrow \beta}{} gleichwertig mit
\mathl{\neg \alpha \vee \beta}{,} und so könnte man den Implikationspfeil auch weglassen. Ebenso kann man den einen Quantor mit Hilfe des anderen und der Negation ausdrücken, es ist nämlich
\mathl{\forall x \alpha}{} gleichbedeutend mit
\mathl{\neg \exists x \neg \alpha}{.} Um die Lesbarkeit der Ausdrücke zu erhöhen, ist es aber alles in allem vorteilhaft, nicht allzu minimalistisch sein zu wollen
\zusatzklammer {man könnte die unnötigen Symbole auch als Abkürzungen einführen} {} {.}
Das Gleichheitszeichen könnte man zwar auch als ein weiteres zweistelliges Relationssymbol auffassen, allerdings sind die weiter unten einzuführenden Schlussregeln für das Gleichheitszeichen
\zusatzklammer {insbesondere die Möglichkeit einzusetzen} {} {}
für die Logik erster Stufe konstitutiv. Da ein Alphabet einer Sprache erster Stufe eine Termgrundmenge enthält, ist klar, was als Term in der Sprache zu gelten hat. Als nächstes erklären wir formal, was wir als einen Ausdruck
\zusatzklammer {oder eine formale Aussage} {} {}
in dieser Sprache ansehen.
\inputdefinition
{}
{
Es sei ein
\definitionsverweis {Alphabet einer Sprache erster Stufe}{}{}
gegeben. Dann nennt man die folgenden rekursiv definierten Wörter über diesem Alphabet die
\definitionswort {Ausdrücke}{}
dieser Sprache.
\aufzaehlungvier{Wenn
\mathkor {} {t_1} {und} {t_2} {}
Terme sind, so ist
\mavergleichskettedisp
{\vergleichskette
{t_1
}
{ =} {t_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein Ausdruck.
}{Wenn $R$ ein $n$-stelliges Relationssymbol ist und
\mathl{t_1 , \ldots , t_n}{} Terme sind, so ist
\mathdisp {R t_1 { \ldots } t_n} { }
ein Ausdruck.
}{Wenn
\mathkor {} {\alpha} {und} {\beta} {}
Ausdrücke sind, so sind auch
\mathdisp {\neg { \left( \alpha \right) } ,\, { \left( \alpha \right) } \wedge { \left( \beta \right) },\, { \left( \alpha \right) } \vee { \left( \beta \right) },\, { \left( \alpha \right) } \rightarrow { \left( \beta \right) }, \, { \left( \alpha \right) } \leftrightarrow { \left( \beta \right) }} { }
Ausdrücke.
}{Wenn $\alpha$ ein Ausdruck und $x$ eine Variable ist, so sind auch
\mathdisp {\forall x { \left( \alpha \right) } \text{ und } \exists x { \left( \alpha \right) }} { }
Ausdrücke.
}
} Die Klammern sind hier auch nur nötig, weil wir die zweistelligen Junktoren anders als die Funktionssymbole in der Mitte schreiben. Die Menge der Konstanten, der Variablen, der Funktionssymbole und der Relationssymbole nennt man zusammen auch das \stichwort {Symbolalphabet} {} der Sprache, das wir mit $S$ bezeichnen. Die anderen Symbole \zusatzklammer {Junktoren, Quantoren, Gleichheitszeichen, Klammern} {} {} sind immer gleich, sodass eine Sprache erster Stufe im Wesentlichen nur von der gewählten Symbolmenge $S$ abhängt. Für die zugehörige Sprache schreibt man $L^S$.
\zwischenueberschrift{Semantik der Prädikatenlogik}
Gelegentlich haben wir schon angedeutet, was die zuletzt eingeführten prädikatenlogischen Symbole, die wir rein formal als Zeichenreihen behandelt haben, eigentlich bedeuten sollen, was also ihr logisch-mathematischer Gehalt sein soll. Bei einer solchen Interpretation werden die Junktoren, die Quantoren und das Gleichheitszeichen stets in der gleichen Weise interpretiert \zusatzklammer {die Junktoren werden wie im aussagenlogischen Kontext interpretiert} {} {,} die Variablen, Konstanten, Relations- und Funktionssymbole aber unterschiedlich. Dazu erinnern wir an einige grundlegende mathematische Begriffe. Wir setzen eine naive Mengenlehre und die natürlichen Zahlen \anfuehrung{zum Zählen}{} \zusatzklammer {wie schon weiter oben} {} {} voraus.
\inputdefinition
{}
{
Es seien zwei Mengen
\mathkor {} {L} {und} {M} {}
gegeben. Dann nennt man die Menge
\mavergleichskettedisp
{\vergleichskette
{ L \times M
}
{ =} { { \left\{ (x,y) \mid x \in L , \, y \in M \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \definitionswort {Produktmenge}{} der beiden Mengen.
}
Für uns ist insbesondere das $n$-fache Produkt einer Menge $M$ mit sich selbst, also
\mathdisp {M^n = M \times M \times \cdots \times M} { }
\zusatzklammer {mit $n$ Faktoren} {} {}
wichtig.
\inputdefinition
{}
{
Unter einer
\definitionswortpraemath {n}{ stelligen Relation }{}
$R$ auf einer Menge $M$ versteht man eine Teilmenge der $n$-fachen Produktmenge
\mathl{M \times \cdots \times M}{.}
}
Ein, zwei- und dreistellige Relationen haben wir in der letzten Vorlesung erwähnt
\zusatzklammer {$x$ ist eine Primzahl, \mathlk{x \leq y}{,} \mathlk{x,y,z}{} bilden ein gleichseitiges Dreieck} {} {}
\inputdefinition
{}
{
Es seien
\mathkor {} {L} {und} {M} {}
Mengen. Eine \definitionswort {Abbildung}{} $F$ von $L$ nach $M$ ist dadurch gegeben, dass jedem Element der Menge $L$ genau ein Element der Menge $M$ zugeordnet wird. Das zu
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eindeutig bestimmte Element wird mit
\mathl{F(x)}{} bezeichnet. Die Abbildung drückt man als Ganzes häufig durch
\maabbeledisp {F} {L} {M
} {x} {F(x)
} {,}
aus.
}
\inputdefinition
{}
{
Es sei $M$ eine Menge. Unter einer \definitionswortpraemath {n}{ stelligen Abbildung }{} auf $M$ versteht man eine Abbildung \maabbeledisp {f} {M \times \cdots \times M} {M } {(x_1 , \ldots , x_n)} {f(x_1 , \ldots , x_n) } {,} vom $n$-\definitionsverweis {fachen Produkt}{}{} von $M$ mit sich selbst nach $M$.
}
Eine $n$-stellige Funktion kann auch als eine $(n+1)$-stellige Relation aufgefasst werden, bei der es zu jedem $n$-Tupel
\mathl{(x_1 , \ldots , x_n)}{} genau ein
\mathl{x_{n+1}}{} gibt derart, dass
\mathl{(x_1 , \ldots , x_n,x_{n+1})}{} zur Relation gehört. Dieses
\mathl{x_{n+1}}{} ist dann der Funktionswert der zugehörigen Funktion an der Stelle
\mathl{(x_1 , \ldots , x_n)}{.}
\zwischenueberschrift{Interpretationen}
\inputdefinition
{}
{
Es sei $S$ das
\definitionsverweis {Symbolalphabet}{}{}
einer Sprache erster Stufe. Unter einer
\definitionswortpraemath {S}{ Struktur }{}
versteht man eine nichtleere Menge $M$ mit den folgenden Festlegungen.
\aufzaehlungdrei{Für jede Konstante
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist ein Element
\mavergleichskette
{\vergleichskette
{c^M
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
festgelegt.
}{Zu jedem $n$-stelligen Funktionssymbol $f$
\zusatzklammer {aus $S$} {} {}
ist eine $n$-stellige Funktion
\maabbdisp {f^M} {M^n} {M
} {}
festgelegt.
}{Zu jedem $n$-stelligen Relationssymbol $R$
\zusatzklammer {aus $S$} {} {}
ist eine $n$-stellige Relation
\mavergleichskettedisp
{\vergleichskette
{ R^M
}
{ \subseteq} {M^n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
festgelegt.
}
Unter einer
\definitionswortpraemath {S}{ (Variablen)belegung }{}
in $M$ versteht man eine Festlegung
\mavergleichskette
{\vergleichskette
{x^M
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jede Variable
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Unter einer \definitionswortpraemath {S}{ Interpretation }{} versteht man eine $S$-Struktur zusammen mit einer $S$-Belegung.
}
Die Menge $M$ heißt auch \stichwort {Grundmenge} {} der $S$-Struktur bzw. der $S$-Interpreta\-tion. Die Festlegung für die Konstanten und die Variablen ist einfach eine Abbildung von $K$ bzw. von der Variablenmenge in die Menge $M$. Statt
\mathl{c^M, x^M, F^M, R^M}{} schreibt man auch
\mathl{I(c), I(x), F^I, R^I}{,} wobei $I$ eine Interpretation bezeichnet. Die Strukturen sind die üblichen Gegenstände der Mathematik
\zusatzklammer {die Belegung von freien Variablen ist der mathematischen Praxis eigentlich fremd; durch sie wird sichergestellt, dass bei einer Interpretation jeder Ausdruck wahr oder falsch wird} {} {.}
\inputbeispiel{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{,}
das außer einer Variablenmenge $V$ aus einem einzigen einstelligen Funktionssymbol $F$ bestehe
\zusatzklammer {die Konstantenmenge und die Relationssymbolmengen seien also leer} {} {.}
Eine
$S$-\definitionsverweis {Struktur}{}{}
besteht dann aus einer nichtleeren Menge $M$ zusammen mit einer Abbildung
\maabbeledisp {f = F^M} {M } {M
} {a} { f(a)
} {.}
Beispiele sind
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der Nachfolgerfunktion,
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit dem Quadrieren
\mathl{x \mapsto x^2}{} oder der Sinusfunktion oder der Exponentialfunktion, oder eine beliebige Menge mit der Identität, eine endliche Menge mit einer
\definitionsverweis {Permutation}{}{,}
u.s.w.
}
\inputbeispiel{}
{
Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{,} das außer einer Variablenmenge $V$ aus einem einzigen zweistelligen Funktionssymbol $F$ bestehe \zusatzklammer {die Konstantenmenge und die Relationssymbolmengen seien also leer} {} {.} Eine $S$-\definitionsverweis {Struktur}{}{} besteht dann aus einer nichtleeren Menge $M$ zusammen mit einer Abbildung \maabbeledisp {f = F^M} {M \times M} {M } {(a,b)} { f(a,b) } {.} Eine solche Abbildung nennt man auch eine \definitionsverweis {Verknüpfung}{}{} auf $M$
- sie ordnet
\zusatzklammer {einem geordneten Paar aus} {} {} zwei Elementen der Menge ein weiteres Element der Menge zu. Die Addition oder die Multiplikation auf den natürlichen Zahlen sind jeweils eine solche Verknüpfung. Weitere Beispiele sind die Verknüpfung in einer Gruppe, die Vektorraumaddition, das Maximum von zwei reellen Zahlen, u.s.w.
}
\inputbeispiel{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{,}
das außer einer Variablenmenge $V$ aus einem einzigen einstelligen Relationssymbol $R$ bestehe
\zusatzklammer {die Konstantenmenge und die Funktionssymbolmengen seien also leer} {} {.}
Eine
$S$-\definitionsverweis {Struktur}{}{}
besteht dann aus einer nichtleeren Menge $M$ zusammen mit einer fixierten Teilmenge
\mavergleichskette
{\vergleichskette
{U
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Beispiele sind
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der Teilmenge der Primzahlen, oder der Teilmenge der Quadratzahlen, oder
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der Teilmenge der positiven Zahlen, oder der Teilmenge der rationalen Zahlen, u.s.w.
}
\zwischenueberschrift{Interpretation von Termen}
Mit einer solchen Interpretation wird das Symbol\-alphabet, das neben den Junktoren, Quantoren, dem Gleichheitszeichen und den Klammern das Alphabet der Sprache bildet, interpretiert. Man möchte aber die gesamte Sprache in $M$, ausgehend von der Interpretation dieser Symbole, interpretieren. Der erste Schritt dazu ist die Interpretation der Terme. Die Wohldefiniertheit der folgenden Festlegung ergibt sich durch einen Beweis über den Aufbau der Terme.
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Symbolalphabet}{}{}
$S$ erster Stufe und einer
$S$-\definitionsverweis {Interpretation}{}{}
in einer Menge $M$ wird induktiv über den Aufbau der Terme für jeden
$S$-\definitionsverweis {Term}{}{}
$t$ eine Interpretation
\mathl{I(t)}{} in $M$ definiert.
\aufzaehlungzwei {Für jede Konstante $c$ und jede Variable $x$ ist die Term\-interpretation durch die Interpretation bzw. die Belegung direkt gegeben, also
\mavergleichskette
{\vergleichskette
{ I(c)
}
{ = }{ c^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{I(x)
}
{ = }{x^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
} {Wenn
\mathl{t_1 , \ldots , t_n}{} Terme mit den Interpretationen
\mathl{I(t_1) , \ldots , I(t_n)}{} sind und wenn $f$ ein $n$-stelliges Funktionssymbol ist, so wird der Term
\mathl{\! ft_1 \ldots t_n}{} als
\mathl{f^M(I(t_1) , \ldots , I(t_n))}{} interpretiert.
}
}
Damit werden alle Terme in der Grundmenge $M$ interpretiert. In vielen Situationen bleibt die Grundmenge und die Interpretation der Konstanten und der Relations- und Funktionssymbole gleich, während man die Variablenbelegung ändern möchte. Insbesondere möchte man Interpretationen für eine einzelne Variable abändern.
\inputdefinition
{}
{
Es sei ein
\definitionsverweis {Symbolalphabet}{}{}
$S$ erster Stufe und eine
$S$-\definitionsverweis {Interpretation}{}{}
$I$ in einer Menge $M$ gegeben. Es sei $x$ eine Variable und
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Element der Grundmenge. Dann versteht man unter der
\definitionswort {Uminterpretation}{}
\mathl{I \frac{m}{x}}{} diejenige Interpretation von $S$ in $M$, die strukturgleich zu $I$ ist und für deren Variablenbelegung
\mavergleichskettedisp
{\vergleichskette
{ { \left( I \frac{m}{x} \right) } (y)
}
{ =} { \begin{cases} I(y), \, \text{ falls } y \neq x\, , \\ m, \, \text{ falls } y = x \, , \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
Entsprechend schreibt man
\mathl{I \frac{m_1 , \ldots , m_k}{x_1 , \ldots , x_k}}{} für
\mathl{{ \left( { \left( I \frac{m_1}{x_1} \right) } \frac{m_2}{x_2} \right) } \ldots \frac{m_k}{x_k}}{,} wobei es bei verschiedenen Variablen nicht auf die Reihenfolge ankommt.
\zwischenueberschrift{Interpretation von Ausdrücken}
Nachdem wir alle Terme bei einer gegebenen $S$-Interpretation interpretieren können, wenden wir uns nun den Ausdrücken zu. Es ist das Ziel, jedem $S$-Ausdruck eine Aussage (unter Bezug auf die Grundmenge $M$ und die Interpretation des Symbolalphabets) zuzuordnen, die wahr oder falsch ist.
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Symbolalphabet}{}{}
$S$ erster Stufe und einer
$S$-\definitionsverweis {Interpretation}{}{}
$I$ in einer Menge $M$ werden die
$S$-\definitionsverweis {Ausdrücke}{}{}
folgendermaßen
\zusatzklammer {induktiv über den Aufbau der Ausdrücke} {} {}
interpretiert und als gültig
\zusatzklammer {oder ungültig} {} {}
charakterisiert
\zusatzklammer {die Gültigkeit einer Aussage $\alpha$ unter der Interpretation wird dabei als
\mathl{I \vDash \alpha}{} geschrieben} {} {.}
Es seien
\mathl{s,t,t_1 , \ldots , t_n}{} Terme, $R$ ein $n$-stelliges Relationssymbol und $\alpha,\beta$ Ausdrücke.
\aufzaehlungsieben{
\mathl{I \vDash s = t}{,} wenn
\mavergleichskette
{\vergleichskette
{I(s)
}
{ = }{I(t)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{
\mathl{I \vDash Rt_1 \ldots t_n}{,} wenn
\mavergleichskette
{\vergleichskette
{ (I(t_1) , \ldots , I(t_n))
}
{ \in }{ R^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{
\mathl{I \vDash \neg { \left( \alpha \right) }}{,} wenn nicht
\mathl{I \vDash \alpha}{} gilt.
}{
\mathl{I \vDash { \left( \alpha \right) } \wedge { \left( \beta \right) }}{,} wenn
\mathl{I \vDash \alpha}{} und
\mathl{I \vDash \beta}{} gilt.
}{
\mathl{I \vDash { \left( \alpha \right) } \rightarrow { \left( \beta \right) }}{,} wenn die Gültigkeit
\mathl{I \vDash \alpha}{} die Gültigkeit
\mathl{I \vDash \beta}{} impliziert.
}{
\mathl{I \vDash \exists x \alpha}{,} wenn es ein
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{I \frac{m}{x} \vDash \alpha}{} gibt.
}{
\mathl{I \vDash \forall x \alpha}{,} wenn für alle
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Beziehung
\mathl{I \frac{m}{x} \vDash \alpha}{} gilt.
}
}
Dabei ist, wie bei jeder Definition, \anfuehrung{wenn}{} als \anfuehrung{genau dann, wenn}{} zu lesen. Auf der linken Seite stehen die formalen Ausdrücke zusammen mit der Erklärung, ob sie in der Interpretation gelten, und auf der rechten Seite steht eine logisch-mathematische Bedingung. Diese ist im Sinne des üblichen Gebrauchs in der Mathematik zu verstehen. Für die Gültigkeitsbeziehung
\mathl{I \vDash \alpha}{} sagt man auch, dass die Interpretation $I$ ein \stichwort {Modell} {} für den Ausdruck $\alpha$ ist oder den Ausdruck $\alpha$ erfüllt.
Da bei dieser Zuordnung alle möglichen Konstruktionsweisen für Ausdrücke auftauchen, ergibt sich eine Erklärung für jeden Ausdruck durch deren induktiven Aufbau. Für jeden Ausdruck $\alpha$ gilt in einer Interpretation $I$ entweder
\mathl{I \vDash \alpha}{} oder nicht, wobei die Nichtgültigkeit zur Gültigkeit von
\mathl{I \vDash \neg \alpha}{} äquivalent ist. Eine Interpretation liefert also insbesondere eine \stichwort {vollständige Aufteilung} {} der $S$-Ausdrücke in wahre und falsche Ausdrücke.
\zwischenueberschrift{Beispiele}
\inputbeispiel{}
{
Es sei $S$ ein Symbolalphabet, das außer einer Variablenmenge $V$ aus einem einzigen einstelligen Funktionssymbol $F$ bestehe
\zusatzklammer {die Konstantenmenge und die Relationssymbolmengen seien also leer} {} {,}
sodass eine
$S$-\definitionsverweis {Struktur}{}{}
aus einer Menge $M$ zusammen mit einer Abbildung
\maabbeledisp {f = F^M} {M } {M
} {a} { f(a)
} {,}
besteht. In einer solchen Interpretation wird jeder $S$-Ausdruck interpretiert. Der Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} {\forall y (\exists x (Fx = y))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besagt die Surjektivität von
\mavergleichskette
{\vergleichskette
{f
}
{ = }{F^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
D.h. in einer $S $-Interpretation gilt
\mathdisp {I \vDash \alpha} { }
genau dann, wenn die durch die Interpretation festgelegte Abbildung $f$
\definitionsverweis {surjektiv}{}{}
ist. Der Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \beta
}
{ =} {\forall x ( \forall y ( (Fx = F y) \rightarrow (x = y )))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besagt die Injektivität von $f$. D.h. in einer $S $-Interpretation gilt
\mathdisp {I \vDash \beta} { }
genau dann, wenn die durch die Interpretation festgelegte Abbildung $f$
\definitionsverweis {injektiv}{}{}
ist.
}
\inputbeispiel{}
{
Es sei $S$ das Symbolalphabet für einen angeordneten Körper, d.h. es gebe eine zweielementige Konstantenmenge
\mavergleichskette
{\vergleichskette
{K
}
{ = }{\{0,1\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
eine zweielementige Menge für die zweistelligen Funktionssymbole
\mathl{\{+, \cdot \}}{} und eine einelementige Menge
\mathl{\{ \geq \}}{} für ein zweistelliges Relationssymbol Wir betrachten die Interpretation $I_1$ mit der Grundmenge $\Q$ und die Interpretation $I_2$ mit der Grundmenge $\R$, wobei Konstanten, Funktionssymbole und das Relationssymbol in natürlicher Weise interpretiert werden
\zusatzklammer {und die Variablenbelegung irgendwie festgelegt sei} {} {.}
Der
$S$-\definitionsverweis {Ausdruck}{}{}
\mavergleichskette
{\vergleichskette
{ 1+1
}
{ \geq }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {also der Ausdruck \mathlk{\geq + 1 1 1}{} in vorgestellter Notation} {} {}
wird unter den Interpretationen als
\mavergleichskette
{\vergleichskette
{1_\Q + 1_\Q
}
{ \geq }{ 1_\Q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bzw. als
\mavergleichskette
{\vergleichskette
{1_\R + 1_\R
}
{ \geq }{ 1_\R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
interpretiert und daher gelten
\mathkor {} {I_1 \vDash 1 +1 \geq 1} {und} {I_2 \vDash 1 +1 \geq 1} {.}
Dagegen ist der Ausdruck
\mathl{\forall x (x \geq 0 \rightarrow \exists y (x =y \cdot y))}{} unter $I_1$ falsch und unter $I_2$ richtig, also
\mathdisp {I_1 \vDash \neg ( \forall x (x \geq 0 \rightarrow \exists y (x =y \cdot y))) \text{ und } I_2 \vDash \forall x (x \geq 0 \rightarrow \exists y (x =y \cdot y))} { . }
}
Das vorstehende Beispiel zeigt, dass die Gültigkeit von Ausdrücken unter einer bestimmten Interpretation von Eigenschaften der Grundmenge abhängt und durch eine mathematische Argumentation erwiesen oder zurückgewiesen werden muss. Diese kann beliebig kompliziert sein. Insbesondere bedeutet die Modellbeziehung nicht, dass man für jeden Ausdruck entscheiden kann, ob er in einer Interpretation wahr oder falsch ist.