Universelle Verallgemeinerung - Universal generalization

In der Prädikatenlogik ist die Generalisierung (auch universelle Generalisierung oder universelle Einführung , GEN ) eine gültige Inferenzregel . Es besagt, dass wenn abgeleitet wurde, dann abgeleitet werden kann. ${\displaystyle \vdash \!P(x)}$${\displaystyle \vdash \!\forall x\,P(x)}$

Verallgemeinerung mit Hypothesen

Die vollständige Generalisierungsregel lässt Hypothesen links vom Drehkreuz zu , jedoch mit Einschränkungen. Angenommen ist ein Satz von Formeln, eine Formel, und wurde abgeleitet. Die Generalisierungsregel besagt, dass abgeleitet werden kann, wenn in nicht erwähnt wird und in nicht vorkommt . ${\displaystyle \Gamma}$${\displaystyle\varphi}$${\displaystyle \Gamma\vdash\varphi(y)}$${\displaystyle \Gamma\vdash\forall x\,\varphi(x)}$${\displaystyle y}$${\displaystyle \Gamma}$${\displaystyle x}$${\displaystyle\varphi}$

Diese Einschränkungen sind für die Solidität erforderlich. Ohne die erste Einschränkung könnte man aus der Hypothese schließen . Ohne die zweite Einschränkung könnte man folgenden Abzug machen: ${\displaystyle \forall xP(x)}$${\displaystyle P(y)}$

1. ${\displaystyle \exists z\,\exists w\,(z\not=w)}$ (Hypothese)
2. ${\displaystyle \exists w\,(y\not =w)}$ (Existenzielle Instanziierung)
3. ${\displaystyle y\not=x}$ (Existenzielle Instanziierung)
4. ${\displaystyle \forall x\,(x\not=x)}$ (Fehlerhafte universelle Verallgemeinerung)

Dies soll zeigen, was eine unsolide Schlussfolgerung ist. Beachten Sie, dass zulässig ist, wenn in nicht erwähnt wird (die zweite Einschränkung muss nicht gelten, da die semantische Struktur von durch die Substitution von Variablen nicht geändert wird). ${\displaystyle \exists z\,\exists w\,(z\not =w)\vdash \forall x\,(x\not =x),}$${\displaystyle \Gamma\vdash\forall y\,\varphi(y)}$${\displaystyle y}$${\displaystyle \Gamma}$${\displaystyle\varphi(y)}$

Beispiel für einen Beweis

Beweise: ist von und ableitbar . ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$${\displaystyle \forall x\,P(x)}$

Nachweisen:

Nummer	Formel	Rechtfertigung
1	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$	Hypothese
2	${\displaystyle \forall x\,P(x)}$	Hypothese
3	${\displaystyle (\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y))}$	Universelle Instanziierung
4	${\displaystyle P(y)\rightarrow Q(y)}$	Aus (1) und (3) von Modus ponens
5	${\displaystyle (\forall x\,P(x))\rightarrow P(y)}$	Universelle Instanziierung
6	${\displaystyle P(y)\ }$	Aus (2) und (5) von Modus ponens
7	${\displaystyle Q(y)\ }$	Aus (6) und (4) von Modus ponens
8	${\displaystyle \forall x\,Q(x)}$	Aus (7) durch Verallgemeinerung
9	${\displaystyle \forall x\,(P(x)\rightarrow Q(x)),\forall x\,P(x)\vdash \forall x\,Q(x)}$	Zusammenfassung von (1) bis (8)
10	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\vdash \forall x\,P(x)\rightarrow \forall x\,Q(x)}$	Aus (9) nach Deduktionssatz
11	${\displaystyle \vdash \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$	Aus (10) nach Deduktionssatz

In diesem Beweis wurde in Schritt 8 die universelle Verallgemeinerung verwendet. Der Deduktionssatz war in den Schritten 10 und 11 anwendbar, da die verschobenen Formeln keine freien Variablen haben.

Siehe auch

• Logik erster Ordnung
• Voreilige Verallgemeinerung
• Universelle Instanziierung

Verweise