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

Übungsaufgaben

Aufgabe Aufgabe 8.1 ändern

Zeige, dass die folgenden prädikatenlogischen Ausdrücke allgemeingültig sind.

1. $\forall x\forall y\forall z((x=y\wedge y=z)\rightarrow x=z).$

2. $(\forall x\alpha )\rightarrow \alpha$

   (wobei ${}\alpha$ ein Ausdruck ist).

3. $\alpha _{1}\wedge \alpha _{2}\wedge \alpha _{3}\rightarrow \beta ,$

   wobei ${}\alpha _{1},\alpha _{2},\alpha _{3}$ die Gruppenaxiome sind und

   $\beta :=\forall z(\forall x(zx=x\wedge xz=x)\rightarrow z=e)$

   ist.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}f\in S$ ein ${}n$-stelliges Funktionssymbol. Zeige, dass der Ausdruck

$\exists y{\left({\left(fx_{1}{\ldots }x_{n}=y\right)}\wedge \forall z{\left({\left(fx_{1}{\ldots }x_{n}=z\right)}\rightarrow y=z\right)}\right)}$

allgemeingültig ist.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}f\in S$ ein ${}2$-stelliges Funktionssymbol. Zeige, dass der Ausdruck

$(\forall x\forall y\forall z(ffxyz=fxfyz))\rightarrow (\forall x\forall y\forall z\forall w(fffxyzw=fxfyfzw))$

allgemeingültig ist.

Aufgabe Aufgabe 8.4 ändern

Es seien ${}p_{1},\ldots ,p_{n}$ Aussagenvariablen und ${}\beta _{1},\ldots ,\beta _{n}$ prädikatenlogische Ausdrücke. Zeige, dass man, wenn man in einer allgemeingültigen aussagenlogischen Aussage ${}\alpha$, in dem keine weiteren Aussagenvariablen vorkommen, jedes Vorkommen von ${}p_{i}$ durch ${}\beta _{i}$ ersetzt, einen allgemeingültigen prädikatenlogischen Ausdruck erhält.

Aufgabe Referenznummer erstellen

Formuliere ein Axiomensystem für das Konzept Äquivalenzrelation in einer prädikatenlogischen Sprache erster Stufe.

Aufgabe Referenznummer erstellen

Axiomatisiere den Körperbegriff in einer geeigneten Sprache erster Stufe.

Eine Menge ${}K$ heißt ein Körper, wenn es zwei Verknüpfungen (genannt Addition und Multiplikation)

$+:K\times K\longrightarrow K{\text{ und }}\cdot :K\times K\longrightarrow K$

und zwei verschiedene Elemente ${}0,1\in K$ gibt, die die folgenden Eigenschaften erfüllen.

1. Axiome der Addition
   1. Assoziativgesetz: Für alle ${}a,b,c\in K$ gilt: ${}(a+b)+c=a+(b+c)$.
   2. Kommutativgesetz: Für alle ${}a,b\in K$ gilt ${}a+b=b+a$.
   3. ${}0$ ist das neutrale Element der Addition, d.h. für alle ${}a\in K$ ist ${}a+0=a$.
   4. Existenz des Negativen: Zu jedem ${}a\in K$ gibt es ein Element ${}b\in K$ mit ${}a+b=0$.
2. Axiome der Multiplikation
   1. Assoziativgesetz: Für alle ${}a,b,c\in K$ gilt: ${}(a\cdot b)\cdot c=a\cdot (b\cdot c)$.
   2. Kommutativgesetz: Für alle ${}a,b\in K$ gilt ${}a\cdot b=b\cdot a$.
   3. ${}1$ ist das neutrale Element der Multiplikation, d.h. für alle ${}a\in K$ ist ${}a\cdot 1=a$.
   4. Existenz des Inversen: Zu jedem ${}a\in K$ mit ${}a\neq 0$ gibt es ein Element ${}c\in K$ mit ${}a\cdot c=1$.
3. Distributivgesetz: Für alle ${}a,b,c\in K$ gilt ${}a\cdot (b+c)=(a\cdot b)+(a\cdot c)$.

Aufgabe Referenznummer erstellen

Axiomatisiere den Begriff eines angeordneten Körpers in einer geeigneten Sprache erster Stufe.

Ein Körper ${}K$ heißt angeordnet, wenn es eine totale Ordnung ${}\geq$ auf ${}K$ gibt, die die beiden Eigenschaften

1. Aus ${}a\geq b$ folgt ${}a+c\geq b+c$ (für beliebige ${}a,b,c\in K$),
2. Aus ${}a\geq 0$ und ${}b\geq 0$ folgt ${}ab\geq 0$ (für beliebige ${}a,b\in K$),

erfüllt.

Aufgabe Referenznummer erstellen

Es sei ${}S=\{0,1,+,\cdot ,\geq \}$ die Symbolmenge für einen angeordneten Körper. Zeige

$\mathbb {R} \vDash \forall x\forall y{\left(x\geq y\leftrightarrow \exists z{\left(x-y=z^{2}\right)}\right)}$

und

$\mathbb {Q} \vDash \neg {\left(\forall x\forall y{\left(x\geq y\leftrightarrow \exists z(x-y=z^{2})\right)}\right)}.$

Über den reellen Zahlen kann man also das Symbol ${}\geq$ mit anderen Symbolen ausdrücken.

Aufgabe * Referenznummer erstellen

In einem angeordneten Körper ist durch

${}\vert {x}\vert \geq \vert {y}\vert \,$

eine zweistellige Relation gegeben. Drücke diese Relation mit den üblichen Symbolen ${}0,-,\geq$, Variablen und aussagenlogischen Junktoren aus.

Aufgabe Referenznummer erstellen

Es sei ${}S=\{0,1,+,\cdot ,\geq \}\cup V$ die Symbolmenge für einen angeordneten Körper und ${}f$ ein einstelliges Funktionssymbol. Formuliere über ${}S'=S\cup \{f\}$ folgende Eigenschaften.

1. Die Stetigkeit von ${}f$.
2. Die gleichmäßige Stetigkeit von ${}f$.
3. Die Differenzierbarkeit von ${}f$.

Gesucht ist also ein Ausdruck ${}\alpha$ aus ${}L^{S'}$ mit der Eigenschaft, dass ${}\alpha$ in einer Interpretation von ${}S'$ (gegeben durch einen angeordneten Körper ${}K$ und eine Funktion ${}f\colon K\rightarrow K$) genau dann gilt, wenn ${}f$ stetig ist.

Aufgabe Referenznummer erstellen

Zeige, dass die Polynomfunktionen in einer Variablen über einem angeordneten Körper stetig sind. Formuliere diese Aussage über dem Symbolalphabet ${}S=\{0,1,+,\cdot ,\geq \}$ für Polynome eines festes Grades.

Aufgabe Referenznummer erstellen

Sei ${}S=\{0,1,+,\cdot ,\geq \}\cup V$ die Symbolmenge für einen angeordneten Körper und ${}f$ ein einstelliges Funktionssymbol. Formuliere über ${}S'=S\cup \{f\}$ die Aussage des Zwischenwertsatzes.

Aufgabe Referenznummer erstellen

Es sei ${}S=\{0,1,+,\cdot ,\geq \}\cup V$ die Symbolmenge für einen angeordneten Körper. Formuliere über ${}S$ die Aussage des Zwischenwertsatzes für Polynome vom Grad ${}d$.

In welchem Zusammenhang stehen die beiden vorstehenden Formulierungen?

Aufgabe Referenznummer erstellen

Es seien ${}\alpha _{1},\alpha _{2},\alpha _{3}$ die Gruppenaxiome und

${}\alpha :=\forall x(\forall y(\forall z(\mu yx=e\wedge \mu xy=e\wedge \mu zx=e\wedge \mu xz=e\rightarrow y=z)))\,,$

also die Aussage, dass das inverse Element eindeutig bestimmt ist. Zeige, dass ${}\alpha$ aus keiner echten Teilmenge ${}\Gamma \subset \{\alpha _{1},\alpha _{2},\alpha _{3}\}$ folgt.

Aufgabe Referenznummer erstellen

Zeige, dass der prädikatenlogische Ausdruck

$\exists x(\forall y(x=y))$

erfüllbar ist.

Aufgabe Aufgabe 8.16 ändern

Es sei ${}\Gamma$ eine Ausdrucksmenge und ${}\alpha$ ein Ausdruck in einer Sprache erster Stufe. Zeige, dass ${}\Gamma \vDash \alpha$ genau dann gilt, wenn ${}\Gamma \cup \{\neg \alpha \}$ nicht erfüllbar ist.

Aufgabe * Referenznummer erstellen

Formuliere die Injektivität für eine Abbildung

$f\colon D\longrightarrow Z$

prädikatenlogisch mit Hilfe der Verwendung von Sorten.

Aufgabe Referenznummer erstellen

Formalisiere mit dem Symbolalphabet ${}S=\{f,g\}\cup V$, wobei ${}f,g$ einstellige Funktionssymbole sind, die Aussage, dass die Hintereinanderschaltung von injektiven Abbildungen zwischen Mengen wieder injektiv ist.

Häufig sind in mathematische Strukturen gewisse Teilmengen wichtig, die Bezug auf die umgebende Struktur nehmen. Eine solche Teilmenge wird prädikatenlogisch durch eine einstellige Relation mit zusätzlichen Eigenschaften wiedergegeben.

Aufgabe * Referenznummer erstellen

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet ${}S$, dass ein Untervektorraum in einem Vektorraum über einem Körper vorliegt.

Aufgabe Referenznummer erstellen

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet ${}S$ den Sachverhalt, dass der Durchschnitt von zwei Untervektorräumen in einem Vektorraum über einem Körper wieder ein Untervektorraum ist.

Aufgabe Referenznummer erstellen

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet ${}S$, dass ein Ideal in einem kommutativen Ring vorliegt.

Aufgabe * Referenznummer erstellen

Es sei ${}A$ eine Menge mit ihrer Potenzmenge ${}{\mathfrak {P}}\,(A)$. Entwerfe ein Symbolalphabet mithilfe von Sortenprädikaten, mit dem man bei adäquater Interpretation folgendes erreichen kann.

1. Man kann zwischen Elementen und Teilmengen von ${}A$ unterscheiden.
2. Man kann die Zugehörigkeit eines Elementes zu einer Teilmenge ausdrücken.
3. Man kann die leere Teilmenge benennen.
4. Man kann die Disjunktheit von zwei Teilmengen ausdrücken.
5. Man kann die Teilmengenbeziehung zwischen zwei Teilmengen ausdrücken.
6. Man kann die Vereinigung und den Durchschnitt von zwei Teilmengen ausdrücken.

Entwerfe ferner ein Axiomensystem für das entwickelte Symbolalphabet, mit dem man

1. die charakteristische Eigenschaft der leeren Teilmenge,
2. die charakteristische Eigenschaft der Disjunktheit,
3. die charakteristische Eigenschaft der Teilmengenbeziehung,
4. das Extensionalitätsprinzip für Teilmengen,
5. die charakteristische Eigenschaft des Durchschnitts,
6. die charakteristische Eigenschaft der Vereinigung,

formulieren kann.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

Welche der folgenden prädikatenlogischen Ausdrücke sind allgemeingültig (${}x,y$ seien Variablen)?

1. ${}\forall x(\exists y(x=y))$,
2. ${}\forall x(\forall y(x=y))$,
3. ${}\exists x(\forall y(x=y))$,
4. ${}\exists x(\exists y(x=y))$.

Aufgabe (5 (2+2+1) Punkte)Aufgabe 8.24 ändern

Es seien ${}\alpha ,\beta \in L^{S}$.

a) Zeige, dass

${\left(\exists x{\left(\alpha \rightarrow \beta \right)}\right)}\rightarrow {\left(\exists x\alpha \rightarrow \exists x\beta \right)}$

nicht allgemeingültig ist.

b) Zeige, dass

${\left(\exists x\alpha \rightarrow \exists x\beta \right)}\rightarrow {\left(\exists x{\left(\alpha \rightarrow \beta \right)}\right)}$

allgemeingültig ist.

c) Zeige, dass

${\left(\exists x\alpha \rightarrow \exists x\beta \right)}\rightarrow {\left(\exists x{\left(\alpha \rightarrow \beta \right)}\right)}$

nicht allgemeingültig wäre, wenn man auch leere Grundmengen zulassen würde.

Aufgabe (3 Punkte)Referenznummer erstellen

Es sei ${}f$ ein einstelliges Funktionssymbol. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

1. ${}\forall x\exists y(fx=y)$,
2. ${}\forall x\exists x(fx=x)$,
3. ${}\exists x(fx=x)$.

Aufgabe (5 Punkte)Referenznummer erstellen

Es seien ${}u,x,y,z$ Variablen und ${}f,g$ einstellige Funktionssymbole. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

a)

1. ${}\forall x\forall y((fx=fy\rightarrow x=y)\wedge (gx=gy\rightarrow x=y))$,
2. ${}\forall x\forall y(fx=fy\rightarrow x=y)\wedge \forall x\forall y(gx=gy\rightarrow x=y)$,
3. ${}\forall x\forall y\forall u\forall z((fx=fy\rightarrow x=y)\wedge (gu=gz\rightarrow u=z))$.

b)

1. ${}\forall x\exists y(fy=x)\wedge \forall x\exists y(gy=x)$,
2. ${}\forall x\exists y{\left(fy=x\wedge gy=x\right)}$,
3. ${}\forall x\exists y\forall u\exists z(fy=x\wedge gz=u)$,
4. ${}\forall x\forall u\exists y\exists z(fy=x\wedge gz=u)$.

Aufgabe (2 Punkte)Referenznummer erstellen

Zeige, dass die Kommutativität der Addition aus den übrigen Körperaxiomen folgt.

Tipp: Zeige zuerst, dass ${}0x=0$ ist.

Aufgabe (2 Punkte)Referenznummer erstellen

Sei ${}S=\{0,1,+,\cdot ,\geq \}\cup V$ die Symbolmenge für einen angeordneten Körper und ${}f,g$ zwei einstellige Funktionssymbole. Formuliere über ${}S'=S\cup \{f,g\}$ die Aussage, dass die Hintereinanderschaltung von zwei stetigen Funktionen wieder stetig ist.

Aufgabe (2 Punkte)Referenznummer erstellen

Formalisiere in der prädikatenlogischen Sprache, dass die Hintereinanderschaltung von surjektiven Abbildungen zwischen Mengen wieder surjektiv ist.

Aufgabe (3 Punkte)Referenznummer erstellen

Formuliere ein prädikatenlogisches Axiomensystem für einen metrischen Raum über einem angeordneten Körper mit Hilfe von Sortenprädikaten.

Aufgabe (3 Punkte)Referenznummer erstellen

Es sei ${}k\in \mathbb {N}$ fixiert. Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet ${}S$ den Sachverhalt, dass ${}k$ Elemente eines kommutativen Ringes ein gegebenes Ideal erzeugen.

Fußnoten