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

Beweis

(1). 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 nach Fakt 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 (2) siehe Aufgabe und Aufgabe.

(3). 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 (4) siehe Aufgabe.

Zur bewiesenen Aussage