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

Übungsaufgaben

Aufgabe

Es sei $ℕ$ die Menge der natürlichen Zahlen und $n \in ℕ$ . Zeige, dass die Menge

ℕ_{\geq n} = {x \in ℕ ∣ x \geq n}

ebenfalls die Dedekind-Peano-Axiome (mit welchem ausgezeichneten Element und mit welcher Nachfolgerabbildung?) erfüllt.

Aufgabe

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

Aufgabe

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

Aufgabe *

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

Aufgabe

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

Aufgabe

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

Es sei $M$ die disjunkte Vereinigung aus $ℕ$ und aus $ℤ$ .^[1] 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 ℕ$ 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 $ℕ$ und auf $ℤ$ übereinstimmt und für die die Abziehregel gilt.

c) Gilt das erststufige Induktionsaxiom (formuliert für die Nachfolgerfunktion)?^[2]

Aufgabe

Zeige, dass die Vorgängereigenschaft

\forall x (x \neq 0 \to \exists y (x = y + 1))

aus der Menge der erststufigen Peano-Axiome ableitbar ist.

Aufgabe

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

Aufgabe

Betrachte die Produktmenge $ℕ \times ℕ$ mit der Nachfolgerfunktion

(a, b)^{'} := (a, b^{'})

und der sogenannten lexikographische Ordnung, für die

(a_{1}, b_{1}) \leq (a_{2}, b_{2})

genau dann gilt, wenn $a_{1} < a_{2}$ oder $a_{1} = a_{2}$ und $b_{1} \leq b_{2}$ ist. Zeige folgende Aussagen.

Es handelt sich um eine totale Ordnung.
Es ist
$x^{'} \geq x$

für alle $x \in ℕ \times ℕ$ .
$(0, 0)$ ist das kleinste Element.
Es liegt eine Wohlordnung (nach unten) vor.
Diese Menge mit der Nachfolgerfunktion erfüllt nicht das Dedekind-Peano-Induktionsaxiom

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es seien $N_{1}$ und $N_{2}$ Dedekind-Peano-Modelle der natürlichen Zahlen. Es sei

φ : N_{1} ⟶ N_{2}

der eindeutig bestimmte Isomorphismus mit $φ (0_{1}) = 0_{2}$ und $φ (n^{'}) = (φ (n))^{'}$ für alle $n \in N_{1}$ . Zeige, dass $φ$ die Multiplikation respektiert, dass also

φ (m \cdot n) = φ (m) \cdot φ (n)

für alle $m, n \in N_{1}$ gilt.

Aufgabe (4 Punkte)

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

φ : ℕ ⟶ M

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

Aufgabe (4 Punkte)

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

Aufgabe (3 Punkte)

Zeige, dass $ℝ_{\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

↑ Dabei muss man darauf achten, die Elemente aus $ℕ$ nicht mit denen aus $ℤ_{\geq 0}$ zu verwechseln. Beispielsweise kann man die Elemente einerseits mit $5$ und andererseits mit $5_{ℤ}$ bezeichnen.
↑ Diese Aufgabe ist wohl schwierig.

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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)

[1] Dabei muss man darauf achten, die Elemente aus $ℕ$ nicht mit denen aus $ℤ_{\geq 0}$ zu verwechseln. Beispielsweise kann man die Elemente einerseits mit $5$ und andererseits mit $5_{ℤ}$ bezeichnen.

[2] Diese Aufgabe ist wohl schwierig.

[1]

[2]