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

Aufgabe

Beweise aus der Existenzeinführung im Antezedens die Alleinführung im Sukzedens. Sie besagt, dass man aus

$\vdash \beta \rightarrow \alpha {\frac {y}{x}}$

unter der Bedingung, dass ${}y$ weder in ${}\forall x\alpha$ noch in ${}\beta$ frei vorkommt, auf

$\vdash \beta \rightarrow \forall x\alpha$

schließen kann.

Aufgabe

Zeige

$\vdash \exists x(x=y).$

Aufgabe

a) Zeige

$\vdash \exists x(\alpha \wedge \beta )\rightarrow \exists x\alpha \wedge \exists x\beta .$

b) Zeige, dass

$\exists x\alpha \wedge \exists x\beta \rightarrow \exists x(\alpha \wedge \beta )$

keine Tautologie ist.

Die beiden folgenden Aufgaben sind vermutlich mühselig.

Aufgabe

Man gebe einen formalen Beweis für die Aussage, dass die Hintereinanderschaltung von zwei surjektiven Abbildungen auf einer Menge wieder surjektiv ist.

Aufgabe

Man gebe einen formalen Beweis für die Aussage, dass die Hintereinanderschaltung von zwei injektiven Abbildungen auf einer Menge wieder injektiv ist.

Aufgabe

Es sei ${}\Gamma$ eine Ausdrucksmenge aus einer Sprache erster Stufe und ${}\alpha$ ein weiterer Ausdruck. Es sei ${}\alpha$ nicht aus ${}\Gamma$ ableitbar. Zeige, dass man aus ${}\Gamma \cup \{\neg \alpha \}$ keinen Widerspruch (also keinen Ausdruck der Form ${}\beta \wedge \neg \beta$) ableiten kann.

Aufgabe

Es sei ${}\Gamma$ eine Menge von ${}S$- Ausdrücken, die über beliebig großen endlichen Grundmengen erfüllbar ist. Zeige, dass ${}\Gamma$ auch über einer unendlichen Menge erfüllbar ist.

Wegen der vorstehenden Aussage gibt es keinen Ausdruck, der genau in allen endlichen Grundmengen gilt. Dennoch kann man die (Un-)endlichkeit prädikatenlogisch charakterisieren.

Aufgabe

Zeige, dass es eine Ausdrucksmenge ${}\Gamma$ mit der Eigenschaft gibt, dass für jede Interpretation ${}I$ genau dann ${}I\vDash \Gamma$ gilt, wenn die Grundmenge der Interpretation unendlich ist.

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieses Arbeitsblattes Zur Vorlesung (PDF)