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

Bei den beiden folgenden Aufgaben soll mit den Peano-Axiomen der zweiten Stufe argumentiert werden.

Aufgabe *

Zeige ausgehend von den Dedekind-Peano-Axiomen, dass jedes Element ${}n\in {\mathbb {N} }$, ${}n\neq 0$, einen Vorgänger besitzt.

Aufgabe

Man gebe Beispiele ${}(M,0,')$ für Mengen mit einem ausgezeichneten Element ${}0\in M$ und einer Abbildung ${}'\colon M\rightarrow M$ an, die je zwei der Dedekind-Peano-Axiome erfüllen, aber nicht das dritte.

Aufgabe

Zeige, dass in der arithmetischen Sprache erster Stufe mit den Konstanten ${}0,1$, dem Nachfolgersymbol ${}N$ und den zweistelligen Funktionssymbolen ${}+$ und ${}\cdot$ nur abzählbar viele Teilmengen von ${}\mathbb {N}$ „adressierbar“ sind und dass daher das zweitstufige Induktionsaxiom der Dedekind-Peano-Axiome nicht in dieser Sprache formulierbar ist.

Aufgabe

Zeige, dass man für jede Teilmenge ${}T\subseteq \mathbb {N}$ die arithmetische Sprache erster Stufe um ein einstelliges Relationssymbol ${}R_{T}$ und die erststufigen Peano-Axiome um geeignete Axiome ergänzen kann, derart, dass diese neue Axiomatik in der Standardinterpretation ${}\mathbb {N}$ genau dann gilt, wenn ${}R_{T}$ als ${}T$ interpretiert wird. Man folgere daraus, dass mit überabzählbar vielen Relationssymbolen alle Teilmengen der natürlichen Zahlen „adressierbar“ sind.

(Dies bedeutet aber nicht, dass für jede Struktur einer solchen Axiomatik jede Teilmenge adressierbar ist, noch, dass das zweitstufige Induktionsaxiom, das eine Aussage über alle Teilmengen macht, erststufig formulierbar ist).

Aufgabe *

Beweise die aussagenlogische Tautologie

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

aus den aussagenlogischen Axiomen.

Aufgabe

Es seien ${}\alpha _{1},\ldots ,\alpha _{n}$ Ausdrücke und es seien ${}i_{1},\ldots ,i_{k}$ Elemente aus ${}\{1,\ldots ,n\}$. Zeige, dass

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

gilt.

Aufgabe

Zeige

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

Aufgabe

Begründe die folgende Ableitungsregel: Aus ${}\vdash \alpha$ und ${}\vdash \alpha \wedge \beta \rightarrow \gamma$ folgt ${}\vdash \beta \rightarrow \gamma$.

Aufgabe

Es seien ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme, ${}f$ ein ${}n$-stelliges Funktionssymbol und ${}R$ ein ${}n$-stelliges Relationssymbol. Zeige, dass die folgenden Aussagen im Prädikatenkalkül ableitbar sind.

1. $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}.$

2. $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\wedge Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{n}.$

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieses Arbeitsblattes Zur Vorlesung (PDF)