Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Definitionsabfrage

Definition:Primzahl

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

Definition:Mersennesche Primzahl

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

Definition:Primzahlzwilling

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

Definition:Wort über einem Alphabet

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

Definition:Sprache der Aussagenlogik

Es sei ${}V$ eine Menge (deren Elemente wir als Aussagenvariable bezeichnen). Dann wird die zugehörige Sprache der Aussagenlogik ${}L^{V}$ (zu ${}V$) rekursiv durch folgende Regeln definiert.

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

Definition:Wahrheitsbelegung

Es sei ${}V$ eine Menge von Variablen und ${}L^{V}$ die zugehörige aussagenlogische Sprache. Unter einer Wahrheitsbelegung versteht man eine Abbildung

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

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

Definition:Interpretation (Aussagenlogik)

Es sei ${}V$ eine Menge von Variablen, ${}L^{V}$ die zugehörige aussagenlogische Sprache und

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

eine Wahrheitsbelegung. Unter der zugehörigen Interpretation ${}I=I^{\lambda }$ versteht man die über den rekursiven Aufbau der Sprache festgelegte Abbildung

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

mit

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

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

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

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

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

   ${}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 ${}\alpha =(\beta )\rightarrow (\gamma )$ ist

   ${}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 ${}\alpha =(\beta )\leftrightarrow (\gamma )$ ist

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

Definition:Aussagenlogische Grundtautologien

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

1. $\vdash \alpha \rightarrow (\beta \rightarrow \alpha ).$

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

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

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

   und

   $\vdash (\alpha \rightarrow (\beta \rightarrow \gamma ))\rightarrow (\alpha \wedge \beta \rightarrow \gamma ).$

5. $\vdash \neg \alpha \wedge \alpha \rightarrow \beta .$

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

Definition:Ableitbar (Aussagenlogik)

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

$\Gamma \vdash \alpha ,$

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

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

gilt.

Definition:Widersprüchliche Ausdrucksmenge (Aussagenlogik)

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

Definition:Maximal widerspruchsfrei (Aussagenlogik)

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

Definition:Ordnungsrelation

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

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

Definition:Größtes Element

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt größtes Element von ${}I$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in I$ gilt.

Definition:Maximales Element

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt maximal (in ${}I$) oder ein maximales Element (von ${}I$), wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.

Definition:Obere Schranke

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt obere Schranke für ${}J$, wenn ${}y\preccurlyeq s$ für jedes ${}y\in J$ gilt.

Definition:Ideal

Eine Teilmenge ${}{\mathfrak {a}}$ eines kommutativen Ringes ${}R$ heißt Ideal, wenn die folgenden Bedingungen erfüllt sind:

1. ${}0\in {\mathfrak {a}}$.
2. Für alle ${}a,b\in {\mathfrak {a}}$ ist auch ${}a+b\in {\mathfrak {a}}$.
3. Für alle ${}a\in {\mathfrak {a}}$ und ${}r\in R$ ist auch ${}ra\in {\mathfrak {a}}$.

Definition:Maximales Ideal

Ein Ideal ${}{\mathfrak {m}}$ in einem kommutativen Ring ${}R$ heißt maximales Ideal, wenn ${}{\mathfrak {m}}\neq R$ ist und wenn es zwischen ${}{\mathfrak {m}}$ und ${}R$ keine weiteren Ideale gibt.

Definition:Induktiv geordnet

Eine geordnete Menge ${}(I,\preccurlyeq )$ heißt induktiv geordnet, wenn jede total geordnete Teilmenge ${}J\subseteq I$ eine obere Schranke in ${}I$ besitzt.

Definition:Topologischer Filter

Es sei ${}X$ ein topologischer Raum. Ein System ${}F$ aus offenen Teilmengen von ${}X$ heißt Filter, wenn folgende Eigenschaften gelten ($U,V$ seien offen).

1. ${}X\in F$.
2. Mit ${}U\in F$ und ${}U\subseteq V$ ist auch ${}V\in F$.
3. Mit ${}U\in F$ und ${}V\in F$ ist auch ${}U\cap V\in F$.

Definition:Ultrafilter

Ein topologischer Filter ${}F$ heißt Ultrafilter, wenn ${}\emptyset \notin F$ und wenn ${}F$ maximal mit dieser Eigenschaft ist.

Definition:Wohlordnung

Eine totale Ordnung ${}\preccurlyeq$ auf einer Menge ${}M$ heißt Wohlordnung, wenn jede nichtleere Teilmenge ${}T\subseteq M$ ein kleinstes Element besitzt.

Definition:Grundtermmenge

Eine Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.

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

Definition:Termmenge

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

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

Definition:Alphabet einer Sprache erster Stufe

Ein Alphabet 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 ${}n\in \mathbb {N} _{+}$ eine Menge ${}R_{n}$ von ${}n$-stelligen Relationssymbolen.
3. Die aussagenlogischen Junktoren

   $\neg ,\,\wedge ,\,\vee ,\,\rightarrow ,\,\leftrightarrow .$

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

Definition:Ausdruck in einer Sprache erster Stufe

Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann nennt man die folgenden rekursiv definierten Wörter über diesem Alphabet die Ausdrücke dieser Sprache.

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

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

   ein Ausdruck.

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

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

   ein Ausdruck.

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

   $\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 ${}\alpha$ ein Ausdruck und ${}x$ eine Variable ist, so sind auch

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

   Ausdrücke.

Definition:Produktmenge

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

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

die Produktmenge der beiden Mengen.

Definition:Relation auf einer Menge

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

Definition:Abbildung

Es seien ${}L$ und ${}M$ Mengen. Eine 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 ${}x\in L$ eindeutig bestimmte Element wird mit ${}F(x)$ bezeichnet. Die Abbildung drückt man als Ganzes häufig durch

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

aus.

Definition:n-stellige Abbildung

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

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

vom ${}n$- fachen Produkt von ${}M$ mit sich selbst nach ${}M$.

Definition:Interpretation

Es sei ${}S$ das Symbolalphabet einer Sprache erster Stufe. Unter einer ${}S$-Struktur versteht man eine nichtleere Menge ${}M$ mit den folgenden Festlegungen.

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

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

   festgelegt.

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

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

   festgelegt.

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

Unter einer ${}S$-Interpretation versteht man eine ${}S$-Struktur zusammen mit einer ${}S$-Belegung.

Definition:Terminterpretation

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

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

Definition:Uminterpretation

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

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

gilt.

Definition:Gültigkeit unter einer Interpretation

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

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

Definition:Allgemeingültiger Ausdruck

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

Definition:Gruppe

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

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

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

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

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

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

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

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

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

Definition:Ordnungsrelation

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

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

Definition:Folgerung

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

Definition:Erfüllbarer Ausdruck

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

Definition:Variablensubstitution für Terme

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

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

   ${}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 ${}c$ ist

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

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

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

Definition:Variablensubstitution für Ausdrücke

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

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

   ${}(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 ${}n$-stelliges Relationssymbol ${}R$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ setzt man

   ${}(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 ${}\alpha$ setzt man

   ${}(\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 ${}\alpha$ und ${}\beta$ setzt man

   ${}(\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 ${}\alpha$ seien ${}x_{i_{1}},\ldots ,x_{i_{r}}$ diejenigen Variablen (unter den $x_{1},\ldots ,x_{k}$), die in ${}\forall x\alpha$ frei vorkommen. Es sei ${}v=x$, falls ${}x$ nicht in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Andernfalls sei ${}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 ${}\alpha$ noch in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Dann setzt man

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

Definition:Ableitbar (Prädikatenlogik)

Ein Ausdruck ${}\alpha \in L^{S}$ heißt ableitbar im Prädikatenkalkül (oder eine syntaktische Tautologie), wenn er sich aus den Grundtautologien, also

• den aussagenlogischen syntaktischen Tautologien,
• den Gleichheitsaxiomen,
• der Existenzeinführung im Sukzedens,

durch sukzessive Anwendung der Ableitungsregeln Modus ponens und der Existenzeinführung im Antezedens erhalten lässt. Die Ableitbarkeit wird durch

$\vdash \alpha$

ausgedrückt.

Definition:Ableitbar aus Ausdrucksmenge (Prädikatenlogik)

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

und ${}\alpha$ ein weiterer ${}S$-Ausdruck. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ ableitbar ist, geschrieben

$\Gamma \vdash \alpha ,$

wenn es endlich viele Ausdrücke

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

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

gilt.

Definition:Addition mit n

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

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

für die

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

gilt.

Definition:Multiplikation mit n

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

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

für die

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

gilt.

Definition:Maximal widerspruchsfrei

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

Definition:Ausdrucksmenge enthält Beispiele

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

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

zu ${}\Gamma$ gehört.

Definition:Atomarer Ausdruck

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

Definition:Rang (Ausdruck)

Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann definiert man für Ausdrücke ${}\alpha \in L^{S}$ den Rang ${}\rho$ von ${}\alpha$ durch

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

Definition:Elementar äquivalent

Zwei ${}S$- Strukturen ${}M$ und ${}N$ über einem erststufigen Symbolalphabet ${}S$ heißen elementar äquivalent, wenn jeder ${}S$- Satz, der in ${}M$ gilt, auch in ${}N$ gilt.

Definition:Homomorphismus

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

$\varphi \colon M\longrightarrow N$

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

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

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

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

   ${}\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 ${}m_{1},\ldots ,m_{n}\in M$.

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

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

   die Gültigkeit von

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

Definition:Isomorphismus

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ und ${}N$ seien ${}S$- Strukturen. Eine bijektive Abbildung

$\varphi \colon M\longrightarrow N$

heißt ${}S$-Isomorphismus, wenn sowohl ${}\varphi$ als auch die Umkehrabbildung ${}\varphi ^{-1}$ ein ${}S$- Homomorphismus ist.

Definition:Elementare Äquivalenz für Elemente

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

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

gilt.

Definition:Funktional-abgeschlossene Teilmenge

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

Definition:Nichtstandardmodell

Es sei ${}M$ eine fixierte ${}S$- Struktur (das Standardmodell) über einem Symbolalphabet ${}S$. Dann nennt man eine weitere ${}S$-Struktur ${}M'$, die zu ${}M$ elementar äquivalent, aber nicht zu ${}M$ ${}S$- isomorph ist, ein Nichtstandardmodell von ${}M$.

Definition:Reell-abgeschlossener Körper

Ein angeordneter Körper ${}K$ heißt reell-abgeschlossen, wenn folgende Eigenschaften gelten.

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

Definition:Registermaschine

Unter einer Registermaschine versteht man eine endliche Folge von Registern ${}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 ${}B_{1},B_{2},\ldots ,B_{h}$, wobei es für die einzelnen Befehle ${}B_{j}$ die folgenden Möglichkeiten gibt.

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

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

Definition:Register-berechenbar

Eine ${}k$- stellige Funktion

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

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

Definition:Register-entscheidbar

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

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

gilt.

Definition:Register-aufzählbar

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

Definition:Arithmetisch repräsentierbare Abbildung

Eine Abbildung

$F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

heißt arithmetisch repräsentierbar , wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die Äquivalenz ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r+s})$ gilt.

Definition:Arithmetisch repräsentierbare Relation

Eine Relation ${}R\subseteq \mathbb {N} ^{r}$ heißt arithmetisch repräsentierbar , wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$-Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Äquivalenz ${}(n_{1},\ldots ,n_{r})\in R$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r})$ gilt.

Definition:Arithmetische Ausdrücke für Befehle

Den Programmzeilen ${}B_{1},\ldots ,B_{h}$ eines Registerprogramms mit ${}m$ Registern werden die folgenden arithmetischen Ausdrücke ${}A_{1},\ldots ,A_{h}$ in den freien Variablen ${}z,r_{1},\ldots ,r_{m},z',r'_{1},\ldots ,r'_{m}$ zugeordnet.

1. Bei ${}B_{\ell }=i+$ setzt man

   $A_{\ell }:=(z=\ell )\rightarrow (z'=z+1)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{i-1}'=r_{i-1})\wedge (r_{i}'=r_{i}+1)\wedge (r_{i+1}'=r_{i+1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

2. Bei ${}B_{\ell }=i-$ setzt man

   $A_{\ell }:=(z=\ell )\rightarrow (z'=z+1)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{i-1}'=r_{i-1})\wedge ((r_{i}=0)\rightarrow (r'_{i}=r_{i}))\wedge (\neg (r_{i}=0)\rightarrow (r_{i}'+1=r_{i}))\wedge (r_{i+1}'=r_{i+1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

3. Bei ${}B_{\ell }=C(ij)$ setzt man

   $A_{\ell }:=(z=\ell )\rightarrow ((r_{i}=0)\rightarrow (z'=j))\wedge (\neg (r_{i}=0)\rightarrow (z'=z+1))\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

4. Bei ${}B_{\ell }=B_{h}=H$ setzt man

   $A_{h}:=(z=h)\rightarrow (z'=z)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

Definition:${}\beta$-Funktion

Unter der ${}\beta$-Funktion versteht man die Abbildung

$\mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(p,n,i)\longmapsto \beta (p,n,i),$

die folgendermaßen festgelegt ist. ${}\beta (p,n,i)$ ist die kleinste Zahl ${}a\in \mathbb {N}$, die die Bedingung erfüllt, dass es natürliche Zahlen ${}b_{0},b_{1},b_{2}$ gibt, die die folgenden Eigenschaften erfüllen:

1. ${}n=b_{0}+b_{1}{\left((i+1)+ap+b_{2}p^{2}\right)}$.
2. ${}a<p$.
3. ${}b_{0}<b_{1}$.
4. ${}b_{1}$ ist eine Quadratzahl.
5. Alle Teiler ${}d\neq 1$ von ${}b_{1}$ sind ein Vielfaches von ${}p$.

Wenn kein solches ${}a$ existiert, so ist ${}\beta (p,n,i)=0$.

Definition:Theorie (Sprache erster Stufe)

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Eine Teilmenge ${}T\subseteq L_{0}^{S}$ heißt Theorie, wenn ${}T$ abgeschlossen unter der Ableitungsbeziehung ist, d.h. wenn aus ${}T\vdash \alpha$ für ${}\alpha \in L_{0}^{S}$ bereits ${}\alpha \in T$ folgt.

Definition:Widersprüchliche Theorie

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Eine Theorie ${}T\subseteq L_{0}^{S}$ heißt widersprüchlich, wenn es einen Satz ${}\alpha \in L_{0}^{S}$ mit ${}\alpha \in T$ und ${}\neg \alpha \in T$ gibt.

Definition:Vollständige Theorie

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Eine Theorie ${}T$ heißt vollständig, wenn für jeden Satz ${}\alpha \in L_{0}^{S}$ gilt ${}\alpha \in T$ oder ${}\neg \alpha \in T$.

Definition:Endlich axiomatisierbar

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Eine Theorie ${}T\subseteq L_{0}^{S}$ heißt endlich axiomatisierbar, wenn es endlich viele Sätze ${}\alpha _{1},\ldots ,\alpha _{n}\in L_{0}^{S}$ mit ${}T=\{\alpha _{1},\ldots ,\alpha _{n}\}^{\vdash }$ gibt.

Definition:Aufzählbar axiomatisierbar

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Eine Theorie ${}T\subseteq L_{0}^{S}$ heißt aufzählbar axiomatisierbar, wenn es eine ${}R$- aufzählbare Satzmenge ${}\Gamma \subseteq L_{0}^{S}$ mit ${}T=\Gamma ^{\vdash }$ gibt.

Definition:Repräsentierbare Relation (in Ausdrucksmenge)

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Relation ${}T\subseteq \mathbb {N} ^{r}$ heißt repräsentierbar in ${}\Gamma$, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$-Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die beiden Eigenschaften

1. Wenn ${}(n_{1},\ldots ,n_{r})\in T$, so ist ${}\Gamma \vdash \psi (n_{1},\ldots ,n_{r})$,
2. Wenn ${}(n_{1},\ldots ,n_{r})\notin T$, so ist ${}\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r})$,

gelten.

Definition:Repräsentierbare Funktion (in Ausdrucksmenge)

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Funktion

$F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

heißt repräsentierbar in ${}\Gamma$, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die folgenden Eigenschaften

1. Wenn ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$, so ist ${}\Gamma \vdash \psi (n_{1},\ldots ,n_{r+s})$,
2. Wenn ${}F(n_{1},\ldots ,n_{r})\neq (n_{r+1},\ldots ,n_{r+s})$, so ist ${}\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r+s})$,
3. ${}\Gamma \vdash \exists !x_{r+1}\ldots \exists !x_{r+s}\psi (n_{1},\ldots ,n_{r},x_{r+1},\ldots ,x_{r+s})$,

gelten.

Definition:Erlaubt Repräsentierungen

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Man sagt, dass ${}\Gamma$ Repräsentierungen erlaubt, wenn ${}\Gamma$ jede ${}R$- berechenbare Relation und jede ${}R$- berechenbare Funktion repräsentiert.

Definition:(Einstelliges) Ableitungsprädikat

Es sei ${}\Gamma$ eine korrekte aufzählbare arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Es sei ${}\delta _{\Gamma }(x,y)$ der ${}L^{\rm {Ar}}$-Ausdruck, der in ${}\Gamma$ die zweistellige Ableitungsrelation ${}A\subseteq \mathbb {N} ^{2}$ repräsentiert. Dann setzt man

${}\alpha (y)=\exists x(\delta _{\Gamma }(x,y))\,$

und nennt dies das (einstellige) Ableitungsprädikat.