Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Definitionsliste

Eine natürliche Zahl${\displaystyle {}n\geq 2}$heißt eine Primzahl, wenn die einzigen natürlichen Teilervon ihr ${\displaystyle {}1}$ und ${\displaystyle {}n}$ sind.

Eine Primzahlder Form ${\displaystyle {}2^{n}-1}$ heißt Mersennesche Primzahl.

Ein Primzahlzwilling ist ein Paar bestehend aus${\displaystyle {}p}$ und ${\displaystyle {}p+2}$,wobei diese beiden Zahlen Primzahlensind.

Es sei ${\displaystyle {}A}$ eine Menge von Symbolen. Dann nennt man jede endliche Zeichenreihe, die man mit den Elementen aus ${\displaystyle {}A}$ aufstellen kann, einWort über dem Alphabet${\displaystyle {}A}$.

Es sei ${\displaystyle {}V}$ eine Menge(deren Elemente wir als Aussagenvariablebezeichnen).Dann wird die zugehörigeSprache der Aussagenlogik${\displaystyle {}L^{V}}$ (zu ${\displaystyle {}V}$)rekursiv durch folgende Regeln definiert.

1. Jedes${\displaystyle {}p\in V}$gehört zu ${\displaystyle {}L^{V}}$.
2. Wenn${\displaystyle {}\alpha \in L^{V}}$ist, so ist auch${\displaystyle {}\neg (\alpha )\in L^{V}}$.
3. Wenn${\displaystyle {}\alpha ,\beta \in L^{V}}$sind, so sind auch${\displaystyle {}(\alpha )\wedge (\beta ),\,(\alpha )\vee (\beta ),\,(\alpha )\rightarrow (\beta ),\,(\alpha )\leftrightarrow (\beta )\in L^{V}}$.

Es sei ${\displaystyle {}V}$ eine Menge von Variablen und ${\displaystyle {}L^{V}}$ die zugehörige aussagenlogische Sprache.Unter einerWahrheitsbelegungversteht man eineAbbildung

${\displaystyle \lambda \colon V\longrightarrow \{0,1\}}$

(oder mit ${\displaystyle {}\{f,w\}}$ als Wertebereich).

Es sei ${\displaystyle {}V}$ eine Menge von Variablen, ${\displaystyle {}L^{V}}$ die zugehörige aussagenlogische Spracheund

${\displaystyle \lambda \colon V\longrightarrow \{0,1\}}$

eineWahrheitsbelegung.Unter der zugehörigen Interpretation${\displaystyle {}I=I^{\lambda }}$versteht man die über den rekursiven Aufbau der Sprachefestgelegte Abbildung

${\displaystyle I\colon L^{V}\longrightarrow \{0,1\}}$

mit

1. ${\displaystyle {}I(v)=\lambda (v)}$für jede Aussagenvariable ${\displaystyle {}v\in V}$.
2. Bei${\displaystyle {}\alpha =\neg (\beta )}$ist

   ${\displaystyle {}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0\,,\\0,{\text{ falls }}I(\beta )=1\,.\end{cases}}\,}$

3. Bei${\displaystyle {}\alpha =(\beta )\wedge (\gamma )}$ist

   ${\displaystyle {}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )=1\,,\\0{\text{ sonst}}\,.\end{cases}}\,}$

4. Bei${\displaystyle {}\alpha =(\beta )\vee (\gamma )}$ist

   ${\displaystyle {}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=1{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=I(\gamma )=0\,.\end{cases}}\,}$

5. Bei${\displaystyle {}\alpha =(\beta )\rightarrow (\gamma )}$ist

   ${\displaystyle {}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=1{\text{ und }}I(\gamma )=0\,.\end{cases}}\,}$

6. Bei${\displaystyle {}\alpha =(\beta )\leftrightarrow (\gamma )}$ist

   ${\displaystyle {}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )\,,\\0,{\text{ falls }}I(\beta )\neq I(\gamma )\,.\end{cases}}\,}$

Für eine Aussagenvariablenmenge ${\displaystyle {}V}$ und beliebige Ausdrücke ${\displaystyle {}\alpha ,\beta ,\gamma }$ legt man folgende (syntaktische)Tautologien axiomatisch fest.

1. ${\displaystyle \vdash \alpha \rightarrow (\beta \rightarrow \alpha ).}$

2. ${\displaystyle \vdash (\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )\rightarrow (\alpha \rightarrow \gamma ).}$

3. ${\displaystyle \vdash (\alpha \rightarrow \beta )\wedge (\alpha \rightarrow \gamma )\rightarrow (\alpha \rightarrow \beta \wedge \gamma ).}$

4. ${\displaystyle \vdash (\alpha \wedge \beta \rightarrow \gamma )\rightarrow (\alpha \rightarrow (\beta \rightarrow \gamma ))}$

   und

   ${\displaystyle \vdash (\alpha \rightarrow (\beta \rightarrow \gamma ))\rightarrow (\alpha \wedge \beta \rightarrow \gamma ).}$

5. ${\displaystyle \vdash \neg \alpha \wedge \alpha \rightarrow \beta .}$

6. ${\displaystyle \vdash (\alpha \rightarrow \beta )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \beta .}$

Es sei${\displaystyle {}\Gamma \subseteq L^{V}}$eine Ausdrucksmenge in derSprache der Aussagenlogikzu einer Aussagenvariablenmenge ${\displaystyle {}V}$ und sei${\displaystyle {}\alpha \in L^{V}}$.Man sagt, dass ${\displaystyle {}\alpha }$ aus ${\displaystyle {}\Gamma }$ ableitbar ist, geschrieben

${\displaystyle \Gamma \vdash \alpha ,}$

wenn es endlich viele Ausdrücke${\displaystyle {}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma }$ derart gibt, dass

${\displaystyle \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha }$

gilt.

Eine Ausdrucksmenge${\displaystyle {}\Gamma \subseteq L^{V}}$in derSprache der Aussagenlogikzu einer Aussagenvariablenmenge ${\displaystyle {}V}$ heißtwidersprüchlich,wenn es einen Ausdruck${\displaystyle {}\alpha \in L^{V}}$mit${\displaystyle {}\Gamma \vdash \alpha }$ und ${\displaystyle {}\Gamma \vdash \neg \alpha }$gibt. Eine nicht widersprüchliche Ausdrucksmenge heißt widerspruchsfrei.

Eine Teilmenge${\displaystyle {}\Gamma \subseteq L^{V}}$zu einer Menge ${\displaystyle {}V}$ an Aussagenvariablenheißtmaximal widerspruchsfrei, wenn ${\displaystyle {}\Gamma }$ widerspruchsfreiist und jede echt größere Menge${\displaystyle {}\Gamma \subset \Gamma '}$widersprüchlich ist.

EineGrundtermmenge besteht aus den folgenden(untereinander disjunkten)Mengen.

1. eine Variablenmenge ${\displaystyle {}V}$,
2. eine Konstantenmenge ${\displaystyle {}K}$,
3. zu jedem${\displaystyle {}n\in \mathbb {N} _{+}}$eine Menge ${\displaystyle {}F_{n}}$ von Funktionssymbolen.

Zu einer Grundtermmenge${\displaystyle {}G=(V,K,F_{n})}$ist die zugehörige Termmenge (oder die Menge der ${\displaystyle {}G}$-Terme)diejenige Teilmenge${\displaystyle {}T=T(G)}$der Wörter ${\displaystyle {}A^{*}}$ über dem Termalphabet${\displaystyle {}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}}$,die durch die folgenden rekursiven Vorschriften festgelegt wird.

1. Jede Variable${\displaystyle {}v\in V}$ist ein Term.
2. Jede Konstante${\displaystyle {}c\in K}$ ist ein Term.
3. Für jedes${\displaystyle {}f\in F_{n}}$und ${\displaystyle {}n}$ Terme ${\displaystyle {}t_{1},t_{2},\ldots ,t_{n}}$ ist auch ${\displaystyle {}ft_{1}t_{2}\ldots t_{n}}$ ein Term.

EinAlphabet einer Sprache erster Stufe umfasst die folgenden Daten.

1. Eine Grundtermmenge,also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
2. Zu jeder natürlichen Zahl${\displaystyle {}n\in \mathbb {N} _{+}}$eine Menge ${\displaystyle {}R_{n}}$ von ${\displaystyle {}n}$-stelligen Relationssymbolen.
3. Die aussagenlogischen Junktoren

   ${\displaystyle \neg ,\,\wedge ,\,\vee ,\,\rightarrow ,\,\leftrightarrow .}$

4. Das Gleichheitszeichen ${\displaystyle {}=}$.
5. Die Quantoren${\displaystyle {}\forall }$ und ${\displaystyle {}\exists }$.
6. Klammern, also ${\displaystyle {}(}$ und ${\displaystyle {})}$.

Es sei einAlphabet einer Sprache erster Stufegegeben. Dann nennt man die folgenden rekursiv definierten Wörter über diesem Alphabet dieAusdrückedieser Sprache.

1. Wenn${\displaystyle {}t_{1}}$ und ${\displaystyle {}t_{2}}$Terme sind, so ist

   ${\displaystyle {}t_{1}=t_{2}\,}$

   ein Ausdruck.

2. Wenn ${\displaystyle {}R}$ ein ${\displaystyle {}n}$-stelliges Relationssymbol ist und ${\displaystyle {}t_{1},\ldots ,t_{n}}$ Terme sind, so ist

   ${\displaystyle Rt_{1}{\ldots }t_{n}}$

   ein Ausdruck.

3. Wenn${\displaystyle {}\alpha }$ und ${\displaystyle {}\beta }$Ausdrücke sind, so sind auch

   ${\displaystyle \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.

4. Wenn ${\displaystyle {}\alpha }$ ein Ausdruck und ${\displaystyle {}x}$ eine Variable ist, so sind auch

   ${\displaystyle \forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}}$

   Ausdrücke.

Es seien zwei Mengen${\displaystyle {}L}$ und ${\displaystyle {}M}$gegeben. Dann nennt man die Menge

${\displaystyle {}L\times M={\left\{(x,y)\mid x\in L,\,y\in M\right\}}\,}$

die Produktmenge der beiden Mengen.

Unter einer${\displaystyle {}n}$-stelligen Relation${\displaystyle {}R}$ auf einer Menge ${\displaystyle {}M}$ versteht man eine Teilmenge der ${\displaystyle {}n}$-fachen Produktmenge ${\displaystyle {}M\times \cdots \times M}$.

Seien${\displaystyle {}L}$ und ${\displaystyle {}M}$Mengen. Eine Abbildung ${\displaystyle {}F}$ von ${\displaystyle {}L}$ nach ${\displaystyle {}M}$ ist dadurch gegeben, dass jedem Element der Menge ${\displaystyle {}L}$ genau ein Element der Menge ${\displaystyle {}M}$ zugeordnet wird. Das zu${\displaystyle {}x\in L}$ eindeutig bestimmte Element wird mit ${\displaystyle {}F(x)}$ bezeichnet. Die Abbildung drückt man als Ganzes häufig durch

${\displaystyle F\colon L\longrightarrow M,\,x\longmapsto F(x),}$

aus.

Es sei ${\displaystyle {}M}$ eine Menge. Unter einer${\displaystyle {}n}$-stelligen Abbildungauf ${\displaystyle {}M}$ versteht man eine Abbildung

${\displaystyle f\colon M\times \cdots \times M\longrightarrow M,\,(x_{1},\ldots ,x_{n})\longmapsto f(x_{1},\ldots ,x_{n}),}$

vom${\displaystyle {}n}$-fachen Produktvon ${\displaystyle {}M}$ mit sich selbst nach ${\displaystyle {}M}$.

Es sei ${\displaystyle {}S}$ das Symbolalphabeteiner Sprache erster Stufe. Unter einer${\displaystyle {}S}$-Strukturversteht man eine nichtleere Menge ${\displaystyle {}M}$ mit den folgenden Festlegungen.

1. Für jede Konstante${\displaystyle {}c\in K}$ist ein Element${\displaystyle {}c^{M}\in M}$festgelegt.
2. Zu jedem ${\displaystyle {}n}$-stelligen Funktionssymbol ${\displaystyle {}f}$(aus ${\displaystyle {}S}$)ist eine ${\displaystyle {}n}$-stellige Funktion

   ${\displaystyle f^{M}\colon M^{n}\longrightarrow M}$

   festgelegt.

3. Zu jedem ${\displaystyle {}n}$-stelligen Relationssymbol ${\displaystyle {}R}$(aus ${\displaystyle {}S}$)ist eine ${\displaystyle {}n}$-stellige Relation

   ${\displaystyle {}R^{M}\subseteq M^{n}\,}$

   festgelegt.

Unter einer${\displaystyle {}S}$-(Variablen)belegung in ${\displaystyle {}M}$ versteht man eine Festlegung${\displaystyle {}x^{M}\in M}$für jede Variable${\displaystyle {}x\in V}$.

Unter einer${\displaystyle {}S}$-Interpretationversteht man eine ${\displaystyle {}S}$-Struktur zusammen mit einer ${\displaystyle {}S}$-Belegung.

Zu einemSymbolalphabet${\displaystyle {}S}$ erster Stufe und einer${\displaystyle {}S}$-Interpretationin einer Menge ${\displaystyle {}M}$ wird induktiv über den Aufbau der Terme für jeden${\displaystyle {}S}$-Term${\displaystyle {}t}$ eine Interpretation ${\displaystyle {}I(t)}$ in ${\displaystyle {}M}$ definiert.

1. Für jede Konstante ${\displaystyle {}c}$ und jede Variable ${\displaystyle {}x}$ ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also${\displaystyle {}I(c)=c^{M}}$und${\displaystyle {}I(x)=x^{M}}$.
2. Wenn ${\displaystyle {}t_{1},\ldots ,t_{n}}$ Terme mit den Interpretationen ${\displaystyle {}I(t_{1}),\ldots ,I(t_{n})}$ sind und wenn ${\displaystyle {}f}$ ein ${\displaystyle {}n}$-stelliges Funktionssymbol ist, so wird der Term ${\displaystyle {}ft_{1}\ldots t_{n}}$ als ${\displaystyle {}f^{M}(I(t_{1}),\ldots ,I(t_{n}))}$ interpretiert.

Es sei einSymbolalphabet${\displaystyle {}S}$ erster Stufe und eine${\displaystyle {}S}$-Interpretation${\displaystyle {}I}$ in einer Menge ${\displaystyle {}M}$ gegeben. Es sei ${\displaystyle {}x}$ eine Variable und ${\displaystyle {}m\in M}$ein Element der Grundmenge. Dann versteht man unter derUminterpretation${\displaystyle {}I{\frac {m}{x}}}$ diejenige Interpretation von ${\displaystyle {}S}$ in ${\displaystyle {}M}$, die strukturgleich zu ${\displaystyle {}I}$ ist und für deren Variablenbelegung

${\displaystyle {}{\left(I{\frac {m}{x}}\right)}(y)={\begin{cases}I(y),\,{\text{ falls }}y\neq x\,,\\m,\,{\text{ falls }}y=x\,,\end{cases}}\,}$

gilt.

Zu einem Symbolalphabet${\displaystyle {}S}$ erster Stufe und einer${\displaystyle {}S}$-Interpretation${\displaystyle {}I}$ in einer Menge ${\displaystyle {}M}$ werden die${\displaystyle {}S}$-Ausdrückefolgendermaßen (induktiv über den Aufbau der Ausdrücke)interpretiert und als gültig (oder ungültig)charakterisiert(die Gültigkeit einer Aussage ${\displaystyle {}\alpha }$ unter der Interpretation wird dabei als ${\displaystyle {}I\vDash \alpha }$ geschrieben).Es seien ${\displaystyle {}s,t,t_{1},\ldots ,t_{n}}$ Terme, ${\displaystyle {}R}$ ein ${\displaystyle {}n}$-stelliges Relationssymbol und ${\displaystyle {}\alpha ,\beta }$ Ausdrücke.

1. ${\displaystyle {}I\vDash s=t}$, wenn${\displaystyle {}I(s)=I(t)}$.
2. ${\displaystyle {}I\vDash Rt_{1}\ldots t_{n}}$, wenn${\displaystyle {}(I(t_{1}),\ldots ,I(t_{n}))\in R^{M}}$.
3. ${\displaystyle {}I\vDash \neg {\left(\alpha \right)}}$, wenn nicht ${\displaystyle {}I\vDash \alpha }$ gilt.
4. ${\displaystyle {}I\vDash {\left(\alpha \right)}\wedge {\left(\beta \right)}}$, wenn ${\displaystyle {}I\vDash \alpha }$ und ${\displaystyle {}I\vDash \beta }$ gilt.
5. ${\displaystyle {}I\vDash {\left(\alpha \right)}\rightarrow {\left(\beta \right)}}$, wenn die Gültigkeit ${\displaystyle {}I\vDash \alpha }$ die Gültigkeit ${\displaystyle {}I\vDash \beta }$ impliziert.
6. ${\displaystyle {}I\vDash \exists x\alpha }$, wenn es ein${\displaystyle {}m\in M}$ mit ${\displaystyle {}I{\frac {m}{x}}\vDash \alpha }$ gibt.
7. ${\displaystyle {}I\vDash \forall x\alpha }$, wenn für alle${\displaystyle {}m\in M}$die Beziehung ${\displaystyle {}I{\frac {m}{x}}\vDash \alpha }$ gilt.

Es sei ${\displaystyle {}S}$ einSymbolalphabetund ${\displaystyle {}\alpha }$ ein${\displaystyle {}S}$-Ausdruckin der Prädikatenlogik erster Stufe. Man nennt ${\displaystyle {}\alpha }$ allgemeingültig(oder einesemantische Tautologie),wenn er in jeder${\displaystyle {}S}$-Interpretation${\displaystyle {}I}$ gilt, also ${\displaystyle {}I\vDash \alpha }$ wahr ist.

Eine Menge ${\displaystyle {}G}$ mit einem ausgezeichneten Element${\displaystyle {}e\in G}$und mit einer Verknüpfung

${\displaystyle G\times G\longrightarrow G,\,(g,h)\longmapsto g\circ h,}$

heißtGruppe,wenn folgende Eigenschaften erfüllt sind.

1. Die Verknüpfung ist assoziativ, d.h. für alle${\displaystyle {}f,g,h\in G}$gilt

   ${\displaystyle {}(f\circ g)\circ h=f\circ (g\circ h)\,.}$

2. Das Element ${\displaystyle {}e}$ ist ein neutrales Element, d.h. für alle${\displaystyle {}g\in G}$gilt

   ${\displaystyle {}g\circ e=g=e\circ g\,.}$

3. Zu jedem${\displaystyle {}g\in G}$gibt es ein inverses Element, d.h. es gibt ein${\displaystyle {}h\in G}$mit

   ${\displaystyle {}h\circ g=g\circ h=e\,.}$

Eine Relation${\displaystyle {}\preccurlyeq }$ auf einer Menge ${\displaystyle {}I}$ heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

1. Es ist${\displaystyle {}i\preccurlyeq i}$für alle${\displaystyle {}i\in I}$.
2. Aus${\displaystyle {}i\preccurlyeq j}$und${\displaystyle {}j\preccurlyeq k}$folgt stets${\displaystyle {}i\preccurlyeq k}$.
3. Aus${\displaystyle {}i\preccurlyeq j}$und ${\displaystyle {}j\preccurlyeq i}$folgt${\displaystyle {}i=j}$.

Es sei ${\displaystyle {}S}$ einSymbolalphabeterster Stufe, ${\displaystyle {}\Gamma }$ eine Menge von${\displaystyle {}S}$-Ausdrückenund ${\displaystyle {}\alpha }$ ein ${\displaystyle {}S}$-Ausdruck. Man sagt, dass ${\displaystyle {}\alpha }$ aus ${\displaystyle {}\Gamma }$ folgt,geschrieben ${\displaystyle {}\Gamma \vDash \alpha }$, wenn für jede${\displaystyle {}S}$-Interpretation${\displaystyle {}I}$ mit ${\displaystyle {}I\vDash \Gamma }$ auch ${\displaystyle {}I\vDash \alpha }$ gilt.

Es sei ${\displaystyle {}S}$ einSymbolalphabetund es sei ${\displaystyle {}\alpha }$ ein${\displaystyle {}S}$-Ausdruckin der Prädikatenlogik erster Stufe. Man nennt ${\displaystyle {}\alpha }$ erfüllbar, wenn es eine${\displaystyle {}S}$-Interpretation${\displaystyle {}I}$ mit ${\displaystyle {}I\vDash \alpha }$ gibt.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k}}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k}}$ fixierte${\displaystyle {}S}$-Terme.Dann definiert man rekursiv über den Aufbau der Terme die Substitution ${\displaystyle {}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ für jeden ${\displaystyle {}S}$-Term ${\displaystyle {}s}$.

1. Für eine Variable ${\displaystyle {}x}$ ist

   ${\displaystyle {}x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:={\begin{cases}x,{\text{ falls }}x\neq x_{i}{\text{ für alle }}i\,,\\t_{i},{\text{ falls }}x=x_{i}\,.\end{cases}}\,}$

2. Für eine Konstante ${\displaystyle {}c}$ ist

   ${\displaystyle {}c{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=c\,.}$

3. Für ein ${\displaystyle {}n}$-stelliges Funktionssymbol ${\displaystyle {}f}$ und ${\displaystyle {}n}$ Terme ${\displaystyle {}s_{1},\ldots ,s_{n}}$ ist

   ${\displaystyle {}fs_{1}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.}$

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufe gegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k}}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k}}$ fixierte${\displaystyle {}S}$-Terme.Dann definiert man rekursiv über den Aufbau der ${\displaystyle {}S}$-Ausdrückedie Substitution${\displaystyle {}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ für jeden ${\displaystyle {}S}$-Ausdruck ${\displaystyle {}\alpha }$.

1. Für Terme ${\displaystyle {}s_{1},s_{2}}$ setzt man

   ${\displaystyle {}(s_{1}=s_{2}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=s_{2}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.}$

2. Für ein ${\displaystyle {}n}$-stelliges Relationssymbol ${\displaystyle {}R}$ und ${\displaystyle {}n}$ Terme ${\displaystyle {}s_{1},\ldots ,s_{n}}$ setzt man

   ${\displaystyle {}(Rs_{1}\ldots s_{n}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=Rs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.}$

3. Für einen Ausdruck ${\displaystyle {}\alpha }$ setzt man

   ${\displaystyle {}(\neg \alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\neg \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.}$

4. Für Ausdrücke ${\displaystyle {}\alpha }$ und ${\displaystyle {}\beta }$ setzt man

   ${\displaystyle {}(\alpha \wedge \beta ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\wedge \beta {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,}$

   und ebenso für die anderen zweistelligen Junktoren.

5. Für einen Ausdruck ${\displaystyle {}\alpha }$ seien ${\displaystyle {}x_{i_{1}},\ldots ,x_{i_{r}}}$ diejenigen Variablen(unter den ${\displaystyle x_{1},\ldots ,x_{k}}$),die in ${\displaystyle {}\forall x\alpha }$ frei vorkommen. Es sei${\displaystyle {}v=x}$,falls ${\displaystyle {}x}$ nicht in ${\displaystyle {}t_{i_{1}},\ldots ,t_{i_{r}}}$ vorkommt. Andernfalls sei ${\displaystyle {}v}$ die erste Variable(in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge),die weder in ${\displaystyle {}\alpha }$ noch in ${\displaystyle {}t_{i_{1}},\ldots ,t_{i_{r}}}$ vorkommt. Dann setzt man

   ${\displaystyle {}(\forall x\alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\forall v\alpha {\frac {t_{i_{1}},\ldots ,t_{i_{r}},v}{x_{i_{1}},\ldots ,x_{i_{r}},x}}\,}$

   und ebenso für den Existenzquantor.

Ein Ausdruck${\displaystyle {}\alpha \in L^{S}}$heißtableitbarim Prädikatenkalkül(oder einesyntaktische Tautologie),wenn er sich aus den Grundtautologien, also

• den aussagenlogischen syntaktischen Tautologien,

• den Gleichheitsaxiomen,

• der Existenzeinführung im Sukzedens,

durch sukzessive Anwendung der AbleitungsregelnModus ponensund der Existenzeinführung im Antezedenserhalten lässt. Die Ableitbarkeit wird durch

${\displaystyle \vdash \alpha }$

ausgedrückt.

Es sei ${\displaystyle {}S}$ einSymbolalphabet,${\displaystyle {}\Gamma }$ eine Menge an${\displaystyle {}S}$-Ausdrücken

${\displaystyle {}\alpha }$

${\displaystyle {}S}$

${\displaystyle {}\alpha }$

${\displaystyle {}\Gamma }$

${\displaystyle \Gamma \vdash \alpha ,}$

${\displaystyle {}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma }$derart gibt, dass

${\displaystyle \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha }$

gilt.

Es sei ${\displaystyle {}(\mathbb {N} ,0,^{\prime })}$ einDedekind-Peano-Modellder natürlichen Zahlen und${\displaystyle {}n\in \mathbb {N} }$.Dann definieren wir die Addition mit ${\displaystyle {}n}$[[Kategorie:Addition mit ${\displaystyle {}n}$ (MSW)|~]] als diejenige aufgrund vonSatz 12.2eindeutig bestimmte Abbildung

${\displaystyle \alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),}$

für die

${\displaystyle \alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N} }$

gilt.

Es sei ${\displaystyle {}(\mathbb {N} ,0,^{\prime })}$ einDedekind-Peano-Modellder natürlichen Zahlen und${\displaystyle {}n\in \mathbb {N} }$.Dann definieren wir die Multiplikation mit ${\displaystyle {}n}$[[Kategorie:Multiplikation mit ${\displaystyle {}n}$ (MSW)|~]] als diejenige aufgrund vonSatz 12.2eindeutig bestimmte Abbildung

${\displaystyle \mu _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \mu _{n}(k),}$

für die

${\displaystyle \mu _{n}(0)=0{\text{ und }}\mu _{n}(k')=\mu _{n}(k)+n{\text{ für alle }}k\in \mathbb {N} }$

gilt.

Eine Menge ${\displaystyle {}\Gamma }$ an${\displaystyle {}S}$-Ausdrücken(über einem Symbolalphabet${\displaystyle {}S}$)heißtmaximal widerspruchsfrei, wenn siewiderspruchsfreiist und wenn jede Hinzunahme eines jeden Ausdrucks${\displaystyle {}\alpha \notin \Gamma }$die Menge widersprüchlich macht.

Man sagt, dass eine Menge ${\displaystyle {}\Gamma }$ an${\displaystyle {}S}$-Ausdrücken(über einem Symbolalphabet${\displaystyle {}S}$)Beispiele enthält, wenn es für jeden Ausdruck der Form ${\displaystyle {}\exists x\alpha }$ einen ${\displaystyle {}S}$-Term${\displaystyle {}t}$ derart gibt, dass

${\displaystyle \exists x\alpha \rightarrow \alpha {\frac {t}{x}}}$

zu ${\displaystyle {}\Gamma }$ gehört.

Unter einem atomaren Ausdruckversteht man Ausdrücke der Form${\displaystyle {}s=t}$,wobei ${\displaystyle {}s}$ und ${\displaystyle {}t}$ Terme sind, und der Form ${\displaystyle {}Rt_{1}\ldots t_{n}}$, wobei ${\displaystyle {}R}$ ein ${\displaystyle {}n}$-stelliges Relationssymbol ist und ${\displaystyle {}t_{1},\ldots ,t_{n}}$ Terme sind.

Es sei einAlphabet einer Sprache erster Stufegegeben. Dann definiert man für Ausdrücke${\displaystyle {}\alpha \in L^{S}}$denRang${\displaystyle {}\rho }$ von ${\displaystyle {}\alpha }$ durch

1. ${\displaystyle {}\rho (\alpha )=0}$,falls ${\displaystyle {}\alpha }$ atomar ist.
2. ${\displaystyle {}\rho (\alpha )=\rho (\beta )+1}$,falls${\displaystyle {}\alpha =\neg (\beta )}$ist.
3. ${\displaystyle {}\rho (\alpha )=\rho (\beta )+\rho (\gamma )+1}$,falls${\displaystyle {}\alpha =(\beta )\circ (\gamma )}$mit${\displaystyle {}\circ =\wedge ,\,\vee ,\,\rightarrow ,\leftrightarrow }$ist.
4. ${\displaystyle {}\rho (\alpha )=\rho (\beta )+1}$,falls${\displaystyle {}\alpha =\exists x\beta }$oder${\displaystyle {}\alpha =\forall x\beta }$ ist.

Zwei${\displaystyle {}S}$-Strukturen${\displaystyle {}M}$ und ${\displaystyle {}N}$ über einemerststufigen Symbolalphabet${\displaystyle {}S}$ heißenelementar äquivalent, wenn jeder${\displaystyle {}S}$-Satz,der in ${\displaystyle {}M}$ gilt, auch in ${\displaystyle {}N}$ gilt.

Es sei ${\displaystyle {}S}$ ein erststufiges Symbolalphabetund${\displaystyle {}M}$ und ${\displaystyle {}N}$seien${\displaystyle {}S}$-Strukturen.Eine Abbildung

${\displaystyle \varphi \colon M\longrightarrow N}$

heißt${\displaystyle {}S}$-Homomorphismus,wenn folgende Eigenschaften gelten.

1. Für jede Konstante${\displaystyle {}c\in S}$ist

   ${\displaystyle {}\varphi {\left(c^{M}\right)}=c^{N}\,.}$

2. Für jedes ${\displaystyle {}n}$-stellige Funktionssymbol${\displaystyle {}f\in S}$ist

   ${\displaystyle {}\varphi {\left(f^{M}{\left(m_{1},\ldots ,m_{n}\right)}\right)}=f^{N}{\left(\varphi (m_{1}),\ldots ,\varphi (m_{n})\right)}\,}$

   für alle${\displaystyle {}m_{1},\ldots ,m_{n}\in M}$.

3. Für jedes ${\displaystyle {}n}$-stellige Relationsymbol${\displaystyle {}R\in S}$impliziert die Gültigkeit von

   ${\displaystyle R^{M}(m_{1},\ldots ,m_{n})}$

   die Gültigkeit von

   ${\displaystyle R^{N}{\left(\varphi (m_{1}),\ldots ,\varphi (m_{n})\right)}.}$

Es sei ${\displaystyle {}S}$ ein erststufiges Symbolalphabetund${\displaystyle {}M}$ und ${\displaystyle {}N}$seien${\displaystyle {}S}$-Strukturen.Einebijektive Abbildung

${\displaystyle \varphi \colon M\longrightarrow N}$

heißt${\displaystyle {}S}$-Isomorphismus,wenn sowohl ${\displaystyle {}\varphi }$ als auch dieUmkehrabbildung${\displaystyle {}\varphi ^{-1}}$ ein${\displaystyle {}S}$-Homomorphismusist.

Es sei ${\displaystyle {}S}$ einerststufiges Symbolalphabetund ${\displaystyle {}M}$ eine${\displaystyle {}S}$-Struktur.Wir nennen zwei Elemente${\displaystyle {}m,n\in M}$ elementar äquivalent, wenn für jeden Ausdruck${\displaystyle {}\alpha \in L_{1}^{S}}$in der einen freien Variablen ${\displaystyle {}x}$ und jede Variablenbelegung ${\displaystyle {}\lambda }$ auf ${\displaystyle {}M}$ die Beziehung

${\displaystyle I{\frac {m}{x}}\vDash \alpha {\text{ genau dann, wenn }}I{\frac {n}{x}}\vDash \alpha }$

gilt.

Es sei ${\displaystyle {}S}$ einerststufiges Symbolalphabetumd ${\displaystyle {}M}$ eine${\displaystyle {}S}$-Struktur.Eine Teilmenge${\displaystyle {}T\subseteq M}$ heißtfunktional abgeschlossen (oder eine${\displaystyle {}S}$-Unterstruktur),wenn für jede Konstante${\displaystyle {}c\in S}$ das Element ${\displaystyle {}c^{M}}$ zu ${\displaystyle {}T}$ gehört und für jedes ${\displaystyle {}k}$-stellige Funktionssymbol ${\displaystyle {}f}$ und beliebige Elemente${\displaystyle {}m_{1},\ldots ,m_{k}\in T}$auch ${\displaystyle {}f^{M}(m_{1},\ldots ,m_{k})}$ zu ${\displaystyle {}T}$ gehört.

Es sei ${\displaystyle {}M}$ eine fixierte${\displaystyle {}S}$-Struktur(dasStandardmodell)über einem Symbolalphabet${\displaystyle {}S}$. Dann nennt man eine weitere ${\displaystyle {}S}$-Struktur ${\displaystyle {}M'}$, die zu ${\displaystyle {}M}$elementar äquivalent,aber nicht zu ${\displaystyle {}M}$ ${\displaystyle {}S}$-isomorphist, einNichtstandardmodellvon ${\displaystyle {}M}$.

Einangeordneter Körper${\displaystyle {}K}$ heißtreell-abgeschlossen, wenn folgende Eigenschaften gelten.

1. Jedes nichtnegative Element aus ${\displaystyle {}K}$ besitzt eine Quadratwurzelin ${\displaystyle {}K}$.
2. Jedes Polynom${\displaystyle {}P\in K[X]}$mit ungeradem Gradbesitzt in ${\displaystyle {}K}$ eine Nullstelle.

Unter einer Registermaschine versteht man eine endliche Folge von Registern ${\displaystyle {}R_{1},R_{2},\ldots ,R_{m}}$(oder Speichern),deren Inhalt jeweils eine natürliche Zahl ist, die durch eine endliche (eventuell leere)Folge von Strichen repräsentiert wird.

Ein Programm für eine Registermaschine ist eine endliche durchnummerierte Folge von Befehlen ${\displaystyle {}B_{1},B_{2},\ldots ,B_{h}}$, wobei es für die einzelnen Befehle ${\displaystyle {}B_{j}}$ die folgenden Möglichkeiten gibt.

1. ${\displaystyle {}i+}$ (erhöhe den Inhalt des Registers ${\displaystyle {}R_{i}}$ um ${\displaystyle {}1}$, d.h. um einen Strich).
2. ${\displaystyle {}i-}$(reduziere den Inhalt des Registers ${\displaystyle {}R_{i}}$ um ${\displaystyle {}1}$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
3. ${\displaystyle {}C(ij)}$(wenn das ${\displaystyle {}i}$-te Register leer ist, so gehe zum Befehl ${\displaystyle {}B_{j}}$, andernfalls zum nächsten Befehl).
4. Drucke(drucke den Inhalt des ersten Registers).
5. Halte an.

Dabei muss${\displaystyle {}i\leq m}$ für alle in einer Programmzeile adressierten Register und${\displaystyle {}j\leq h}$ für alle adressierten Befehlszeilen gelten. Die letzte Befehlszeile ${\displaystyle {}B_{h}}$ ist ein Haltebefehl und sonst gibt es keinen Haltebefehl.

Eine${\displaystyle {}k}$-stellige Funktion

${\displaystyle F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N} }$

heißt${\displaystyle {}R}$-berechenbar(oderRegister-berechenbar),wenn es ein Programm ${\displaystyle {}P}$ für eine Registermaschine gibt, die bei jeder Eingabe ${\displaystyle {}(r_{1},\ldots ,r_{k})}$(in den ersten ${\displaystyle {}k}$ Registern)anhält und ${\displaystyle {}F(r_{1},\ldots ,r_{k})}$ als (einzige)Ausgabe besitzt.

Es sei${\displaystyle {}T\subseteq \mathbb {N} }$eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge${\displaystyle {}R}$-entscheidbar(oder Register-entscheidbar)ist, wenn es ein Programm ${\displaystyle {}P}$ für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

${\displaystyle n\in T{\text{ genau dann, wenn }}P(n){\text{ die Ausgabe }}0{\text{ besitzt}}}$

gilt.

Es sei${\displaystyle {}T\subseteq \mathbb {N} }$eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge${\displaystyle {}R}$-aufzählbar (oder Register-aufzählbar)ist, wenn es ein Programm ${\displaystyle {}P}$ für eine Registermaschine gibt, die bei Eingabe von ${\displaystyle {}0}$ nach und nach genau die Zahlen aus ${\displaystyle {}T}$ ausdruckt(dabei dürfen Zahlen aus ${\displaystyle {}T}$ auch mehrfach ausgedruckt werden).