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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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 , , einen Vorgänger besitzt.


Aufgabe

Man gebe Beispiele für Mengen mit einem ausgezeichneten Element und einer Abbildung 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 , dem Nachfolgersymbol und den zweistelligen Funktionssymbolen und nur abzählbar viele Teilmengen von „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 die arithmetische Sprache erster Stufe um ein einstelliges Relationssymbol und die erststufigen Peano-Axiome um geeignete Axiome ergänzen kann, derart, dass diese neue Axiomatik in der Standardinterpretation genau dann gilt, wenn als 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

aus den aussagenlogischen Axiomen.


Aufgabe

Es seien Ausdrücke und es seien Elemente aus . Zeige, dass

gilt.


Aufgabe

Zeige


Aufgabe

Begründe die folgende Ableitungsregel: Aus und folgt .


Aufgabe

Es seien Terme, ein -stelliges Funktionssymbol und ein -stelliges Relationssymbol. Zeige, dass die folgenden Aussagen im Prädikatenkalkül ableitbar sind.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)