Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Arbeitsblatt 13/kontrolle

Übungsaufgaben

Aufgabe Aufgabe 13.1 ändern

Zeige, dass in einem Peano-Halbring die Addition assoziativ ist.

Aufgabe Aufgabe 13.2 ändern

Zeige, dass in einem Peano-Halbring die Multiplikation kommutativ und assoziativ ist und dass ${}1$ das neutrale Element ist.

Aufgabe * Aufgabe 13.3 ändern

Man gebe ein Beispiel für einen kommutativen Halbring, der kein Peano-Halbring ist.

Aufgabe Referenznummer erstellen

Zeige, dass in einem Peano-Halbring die Ordnungsrelation mit der Addition und der Multiplikation verträglich ist.

Aufgabe Referenznummer erstellen

Zeige, dass in einem Peano-Halbring der Ausdruck

$\forall x\forall y{\left(x\leq y\wedge y\leq x+1\rightarrow {\left(y=x\vee y=x+1\right)}\right)}$

gilt.

Aufgabe Referenznummer erstellen

Zeige, dass in einem Peano-Halbring das Lemma von Bezout in der Form gilt, dass es zu zwei teilerfremden (das ist zu definieren) Elementen ${}x,y$ Elemente ${}a,b$ mit

${}ax=1+by\,$

gibt.

Aufgabe Referenznummer erstellen

Zeige, dass in einer Struktur, die die Peano-Axiome für den Nachfolger erfüllt, die Aussage

$\forall x{\left(x=0\vee x=N0\vee \exists y{\left(NNy=x\right)}\right)}$

gilt.

Aufgabe * Referenznummer erstellen

Zeige, dass die Vorgängereigenschaft

$\forall x{\left(x\neq 0\rightarrow \exists y(x=Ny)\right)}$

aus der Menge der Peano-Axiome für den Nachfolger folgt.

Aufgabe Aufgabe 13.9 ändern

Zeige, dass die Vorgängereigenschaft

$\forall x{\left(x\neq 0\rightarrow \exists y(x=y+1)\right)}$

aus der Menge der erststufigen Peano-Axiome ableitbar ist.

Aufgabe Referenznummer erstellen

Zeige, dass die Division mit Rest aus der Menge der erststufigen Peano-Axiome ableitbar ist.

Aufgabe Referenznummer erstellen

Es sei

${}M=\mathbb {Q} _{\geq 0}\,$

die Menge der nichtnegativen rationalen Zahlen mit der ${}0$ und der Abbildung

${}N(x)=x+1\,.$

Welche der Peano-Axiome für den Nachfolger gelten für ${}M$, welche nicht?

Aufgabe Referenznummer erstellen

Es sei ${}M$ die disjunkte Vereinigung aus zwei Kopien von ${}\mathbb {N}$ zusammen mit dem ausgezeichneten Element ${}0=0_{1}$ (aus der ersten Kopie) und der Abbildung ${}N$, die auf beiden Kopien die übliche Nachfolgerabbildung ist. Welche der Peano-Axiome für den Nachfolger gelten für ${}M$, welche nicht?

Aufgabe Referenznummer erstellen

Es sei ${}M$ die disjunkte Vereinigung aus ${}\mathbb {N}$ und aus ${}\mathbb {Z}$. Wir definieren auf ${}M$ eine Nachfolgerfunktion, die auf den beiden Bestandteilen durch den üblichen Nachfolger gegeben ist (also durch ${}+1$), und wir betrachten die ${}0\in \mathbb {N}$ als die Null von ${}M$.

a) Zeige, dass ${}M$ die ersten beiden Axiome aus den erststufigen Peano-Axiomen für die Nachfolgerfunktion erfüllt.

b) Zeige, dass es keine Addition auf ${}M$ gibt, die mit den Additionen auf ${}\mathbb {N}$ und auf ${}\mathbb {Z}$ übereinstimmt und für die die Abziehregel gilt.

c) Gilt das erststufige Induktionsaxiom (formuliert für die Nachfolgerfunktion)?

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 weder, 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).

Aufgaben zum Abgeben

Aufgabe (4 Punkte)Aufgabe 13.16 ändern

Es sei ${}\mathbb {N}$ ein Peano-Dedekind-Modell der natürlichen Zahlen und ${}M$ ein Peano-Halbring. Zeige, dass es eine eindeutig bestimmte Abbildung

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

mit ${}\varphi (0)=0$ und ${}\varphi (n')=\varphi (n)+1$ gibt. Zeige ferner, dass ${}\varphi$ injektiv ist und die Addition und die Multiplikation respektiert.

Aufgabe (4 Punkte)Aufgabe 13.17 ändern

Zeige, dass in einem Peano-Halbring das Distributivgesetz gilt.

Aufgabe (3 Punkte)Aufgabe 13.18 ändern

Zeige, dass in einem Peano-Halbring die Kürzungseigenschaft gilt, d.h. dass aus ${}xz=yz$ mit ${}z\neq 0$ die Gleichheit ${}x=y$ folgt.

Aufgabe (4 Punkte)Referenznummer erstellen

Zeige, dass ${}\mathbb {R} _{\geq 0}$ mit ${}0,1$ und der natürlichen Addition und Multiplikation die ersten sechs Peano-Axiome erfüllt, aber nicht das Induktionsaxiom.

Fußnoten