Prädikatenlogik/Quantoren/Tautologien/Ableitungen/Fakt/Beweis

Beweis

(1). Durch Existenzeinführung im Sukzedenz haben wir

$\vdash \alpha \rightarrow \exists x\alpha$

und

$\vdash \exists x\alpha \rightarrow \exists y\exists x\alpha$

und daraus

$\vdash \alpha \rightarrow \exists y\exists x\alpha .$

Dabei ist ${}y$ hinten gebunden und somit kann man mit der Existenzeinführung im Antezedens auf

$\vdash \exists y\alpha \rightarrow \exists y\exists x\alpha$

schließen. Da auch ${}x$ hinten gebunden ist, ergibt sich

$\vdash \exists x\exists y\alpha \rightarrow \exists y\exists x\alpha .$

(2). Aufgrund der Alleinführung im Antezedens ist

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

und

$\vdash \forall x(\alpha \rightarrow \beta )\rightarrow (\alpha \rightarrow \beta ).$

Dies konjugiert (unter Verwendung von Fakt  (2)) ergibt

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

Ferner haben wir die aussagenlogische Tautologie

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

Damit ergibt sich aufgrund der Transitivität der Implikation die Ableitung

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

Da ${}x$ vorne und in ${}\forall x\beta$ gebunden vorkommt, gilt nach der Alleinführung im Sukzedens auch

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

Zu (3) siehe Aufgabe und Aufgabe.

(4). Aufgrund der Alleinführung im Antezedens ist

$\vdash \forall x(\alpha \rightarrow \beta )\rightarrow (\alpha \rightarrow \beta ),$

was wir als

$\vdash \alpha \wedge \forall x(\alpha \rightarrow \beta )\rightarrow \beta$

schreiben. Wegen ${}\vdash \beta \rightarrow \exists x\beta$ ist auch

$\vdash \alpha \wedge \forall x(\alpha \rightarrow \beta )\rightarrow \exists x\beta ,$

was wir als

$\vdash \alpha \rightarrow (\forall x(\alpha \rightarrow \beta )\rightarrow \exists x\beta )$

schreiben. Im Sukzedens ist ${}x$ gebunden, daher folgt aus der Existenzeinführung im Antezedens

$\vdash \exists x\alpha \rightarrow (\forall x(\alpha \rightarrow \beta )\rightarrow \exists x\beta ),$

was aussagenlogisch äquivalent zur Behauptung ist.

Zu (5) siehe Aufgabe.

Zur bewiesenen Aussage