Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Definitionsliste

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: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

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