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

Übungsaufgaben

Aufgabe * Referenznummer erstellen

Zeige, dass in einem kommutativen Halbring die Beziehung ${}0\cdot 0=0$ gilt.

Aufgabe Referenznummer erstellen

Es sei ${}R$ ein kommutativer Halbring. Zeige, dass

${}0\cdot {\left(1+1+\cdots +1\right)}=0\,$

ist (mit einer beliebig langen Summe von Einsen).

Aufgabe * Referenznummer erstellen

Man definiere auf der dreielementigen Menge ${}\{0,1,u\}$ die Struktur eines kommutativen Halbringes, bei dem ${}0\cdot u\neq 0$ gilt.

Aufgabe Referenznummer erstellen

Da man die natürlichen Zahlen zum Zählen von endlichen Mengen nimmt, es aber auch unendliche Mengen gibt, denkt sich Gabi Hochster, dass man die natürlichen Zahlen ${}\mathbb {N}$ um ein weiteres Symbol ${}\infty$ (sprich unendlich) erweitern sollte. Diese neue Menge bezeichnet sie mit ${}\mathbb {N} ^{\infty }$. Sie möchte die Ordnungsstruktur, die Addition und die Multiplikation der natürlichen Zahlen auf ihre neue Menge ausdehnen, und zwar derart, dass möglichst viele vertraute Rechengesetze erhalten bleiben.

1. Wie legt Gabi die Ordnung fest?
2. Wie legt sie die Nachfolgerabbildung fest? Gelten die Peano-Axiome?
3. Wie legt sie die Addition fest? Sie möchte ja nur mit dem einzigen neuen Symbol ${}\infty$ arbeiten.
4. Gilt mit dieser Addition die Abziehregel?
5. Zuerst denkt sie an die Festlegung

   ${}0\cdot \infty =1\,,$

   doch dann stellt sie fest, dass sich das mit dem Distributivgesetz beißt. Warum?

6. Gabi möchte nun, dass für die neue Menge die Eigenschaften aus Satz 8.14 und aus Satz 9.6 (Grundkurs Mathematik (Osnabrück 2018-2019)) nach wie vor gelten. Wie legt sie die Verknüpfungen fest?
7. Handelt es sich bei ${}\mathbb {N} ^{\infty }$ mit den Festlegungen aus Teil (6) um einen kommutativen Halbring?
8. Gilt die Kürzungsregel?

Aufgabe * Referenznummer erstellen

Es sei ${}R={\mathfrak {P}}\,(M)$ die Potenzmenge zu einer Menge ${}M$. Zeige, dass ${}R$ mit der Vereinigung ${}\cup$ als Addition und der leeren Menge als ${}0$ und mit dem Durchschnitt ${}\cap$ als Multiplikation und der Gesamtmenge ${}M$ als ${}1$ ein kommutativer Halbring ist.

Aufgabe Referenznummer erstellen

Gilt für die Vereinigung von Mengen die „Abziehregel“, d.h. kann man aus ${}A\cup C=B\cup C$ auf ${}A=B$ schließen?

Aufgabe Referenznummer erstellen

Es sei ${}M$ ein kommutativer Halbring. Zeige, dass es eine eindeutig bestimmte (kanonische) Abbildung

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

gibt, die sowohl die Addition als auch die Multiplikation respektiert.

Aufgabe Referenznummer erstellen

Es sei ${}R$ ein kommutativer Halbring und ${}f,a_{i},b_{j}\in R$. Zeige die folgenden Gleichungen:

$\sum _{i=0}^{n}a_{i}f^{i}+\sum _{j=0}^{m}b_{j}f^{j}=\sum _{k=0}^{\max(n,m)}(a_{k}+b_{k})f^{k}$

und

${\left(\sum _{i=0}^{n}a_{i}f^{i}\right)}\cdot {\left(\sum _{j=0}^{m}b_{j}f^{j}\right)}=\sum _{k=0}^{n+m}c_{k}f^{k}{\text{ mit }}c_{k}=\sum _{r=0}^{k}a_{r}b_{k-r}.$

Aufgabe * Referenznummer erstellen

Beweise das allgemeine Distributivgesetz für einen kommutativen Halbring.

Aufgabe * Referenznummer erstellen

Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring ${}R$ durch Induktion über ${}k$, wobei der Fall ${}k=2$ verwendet werden darf (dabei sind ${}n_{1},\ldots ,n_{k}$ natürliche Zahlen und ${}a_{j,i}\in R$).

${}{\begin{aligned}{\left(\sum _{i_{1}=1}^{n_{1}}a_{1,i_{1}}\right)}\cdot {\left(\sum _{i_{2}=1}^{n_{2}}a_{2,i_{2}}\right)}\cdots {\left(\sum _{i_{k}=1}^{n_{k}}a_{k,i_{k}}\right)}&=\sum _{(i_{1},i_{2},\ldots ,i_{k})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\\\end{aligned}}$

Aufgabe Referenznummer erstellen

Zeige, dass in einem kommutativen Halbring durch

$x\geq y{\text{ genau dann, wenn }}\exists z(x=y+z)$

eine reflexive und transitive Relation gegeben ist. Zeige durch geeignete Beispiele, dass diese weder antisymmetrisch noch total sein muss.

In den folgenden Aufgaben besprechen wir Teilbarkeitskonzepte für einen kommutativen Halbring.

Eine Nichteinheit ${}p$ in einem kommutativen Halbring heißt irreduzibel (oder unzerlegbar), wenn eine Faktorisierung ${}p=ab$ nur dann möglich ist, wenn einer der Faktoren eine Einheit ist.

Diese Eigenschaft charakterisiert im Halbring ${}\mathbb {N}$ gerade die Primzahlen.

Eine Nichteinheit ${}p\neq 0$ in einem kommutativen Halbring ${}R$ heißt prim (oder ein Primelement), wenn folgendes gilt: Teilt ${}p$ ein Produkt ${}ab$ mit ${}a,b\in R$, so teilt es einen der Faktoren.

Aufgabe Referenznummer erstellen

Formalisiere in der (erststufigen) Sprache der kommutativen Halbringe die Konzepte Einheit, Teilt, irreduzibel, Primelement.

Aufgabe Referenznummer erstellen

Es sei ${}R$ ein kommutativer Halbring, der die Kürzungsregel erfüllt. Zeige, dass ein Primelement stets irreduzibel ist.

Aufgabe Referenznummer erstellen

Zeige, dass für ${}\mathbb {N}$ die Konzepte Primelement und irreduzibel zusammenfallen.

Aufgabe Referenznummer erstellen

Man gebe Beispiele für kommutative Halbringe, in denen die Konzepte Primelement und irreduzibel auseinanderfallen.

Aufgabe Aufgabe 13.16 ändern

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

Aufgabe Aufgabe 13.17 ändern

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

Aufgabe * Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Es sei ${}M$ ein Peano-Halbring und

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

die kanonische Abbildung. Zeige, dass ${}\varphi$ injektiv 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 * Aufgabe 13.22 ändern

Zeige, dass in einem Peano-Halbring ${}M$ zu ${}d\geq 1$ die Division mit Rest eindeutig ist.

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 die Division mit Rest aus der Menge der erststufigen Peano-Axiome ableitbar ist.

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

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=\{0\}\cup \mathbb {Q} _{\geq 1}\,.$

1. Zeige, dass ${}M$ ein kommutativer Halbring ist.
2. Zeige, dass in ${}M$ die Relationen

   $a{\text{ teilt }}b{\text{ oder }}a=0$

   und

   $a\leq b{\text{ oder }}b=0$

   zueinander äquivalent sind.

3. Zeige, dass ${}{\frac {6}{5}}$ nicht irreduzibel in ${}M$ ist.
4. Zeige, dass es in ${}M$ keine irreduziblen Elemente gibt.
5. Es sei ${}\alpha$ die Aussage

   $x=0\vee \exists y(x=y+1).$

   Zeige, dass in ${}M$ die Aussage

   $\alpha {\frac {0}{x}}\wedge {\left(\alpha \rightarrow \alpha {\frac {x+1}{x}}\right)}$

   wahr ist.

6. Zeige, dass ${}M$ kein Peano-Halbring ist.

Die folgende Aufgabe gibt eine Version des Lemmas von Bezout für Peano-Halbringe.

Aufgabe Referenznummer erstellen

Es sei ${}M$ ein Peano-Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d{\text{ mit }}u+ax+by=cx+dy\right\}}\,.$

Zeige, dass es ein eindeutig bestimmtes ${}v\in M$ derart gibt, dass ${}I$ aus sämtlichen Vielfachen von ${}v$ besteht. Zeige, dass ${}v$ der größte gemeinsame Teiler von ${}x$ und ${}y$ ist.

Aufgabe Referenznummer erstellen

Zeige, dass in einem Peano-Halbring ${}M$ die Begriffe irreduzibel und prim zusammenfallen.

Aufgabe Referenznummer erstellen

Es sei ${}n\in \mathbb {N} _{+}$ und betrachte ${}M=\mathbb {Z} /(n)$ mit den natürlichen Operationen. Welche der Peano-Axiome gelten, welche nicht?

Aufgabe * Referenznummer erstellen

Es sei ${}M$ ein kommutativer Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d{\text{ mit }}u+ax+by=cx+dy\right\}}\,.$

1. Zeige, dass ${}I$ die folgenden drei Eigenschaften erfüllt.
   1. ${}0\in I$.
   2. Wenn ${}u,v\in I$ sind, so ist auch ${}u+v\in I$.
   3. Wenn ${}u\in I$ und ${}r\in M$ ist, so ist auch ${}ru\in I$.
2. ${}M$ erfülle nun die Abziehregel. Zeige, dass aus ${}u,v\in I$ mit ${}u=v+z$ auch ${}z\in I$ folgt.

Aufgabe Aufgabe 13.33 ändern

Zeige, dass in ${}M\subseteq \mathbb {Z} [V]$ aus Beispiel 13.9 jedes Element ${}\neq 0$ einen eindeutig bestimmten Vorgänger besitzt.

Aufgabe Aufgabe 13.34 ändern

Zeige, dass in ${}M\subseteq \mathbb {Z} [V]$ aus Beispiel 13.9 durch ${}x\geq y$, falls es ein ${}z\in M$ mit ${}x=y+z$ gibt, eine totale Ordnung gegeben ist.

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.37 ä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.38 ändern

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

Aufgabe (3 Punkte)Aufgabe 13.39 ä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.

Die Aufgabe zum Aufgeben

Aufgabe (5 Punkte)Referenznummer erstellen

Man gebe einen Ausdruck ${}\alpha \in L^{\rm {Ar}}$ aus der arithmetischen Sprache erster Stufe (also mit ${}0,1,+,\cdot$) mit einer freien Variablen ${}x$ an, der über den ganzen Zahlen ${}\mathbb {Z}$ folgende Eigenschaft besitzt: Es gilt

$\mathbb {Z} {\frac {m}{x}}\vDash \alpha$

genau dann, wenn ${}m\in \mathbb {N}$ ist (der Ausdruck gilt also genau für die natürlichen Zahlen).

Fußnoten