Generalización universal

La regla de generalización completa permite la hipótesis a la izquierda del trinquete, pero con restricciones. Supongamos que Γ es un conjunto de fórmulas, φ una fórmula, y ${\displaystyle \Gamma \vdash \varphi (y)}$. La regla de generalización dice que ${\displaystyle \Gamma \vdash \forall x\varphi (x)}$ puede derivarse si y no se menciona en Γ y x no ocurre en φ.

Estas restricciones son necesarias para la solidez. Sin la primera restricción, se podría concluir ${\displaystyle \forall xP(x)}$ de la hipótesis ${\displaystyle P(y)}$. Sin la segunda restricción, se podría hacer la siguiente deducción:

1. ${\displaystyle \exists z\exists w(z\not =w)}$ (Hipótesis)
2. ${\displaystyle \exists w(y\not =w)}$ (Instanciación existencial)
3. ${\displaystyle y\not =x}$ (Instanciación existencial)
4. ${\displaystyle \forall x(x\not =x)}$ (Generalización universal defectuosa)

Esto pretende demostrar que ${\displaystyle \exists z\exists w(z\not =w)\vdash \forall x(x\not =x),}$ que es una deducción errónea.

Demostrar: ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$.

Demostración:

Número	Fórmula	Justificación
1	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$	Hipótesis
2	${\displaystyle \forall x\,P(x)}$	Hipótesis
3	${\displaystyle (\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y)))}$	Instanciación universal
4	${\displaystyle P(y)\rightarrow Q(y)}$	Desde (1) y (3) por Modus ponens
5	${\displaystyle (\forall x\,P(x))\rightarrow P(y)}$	Instanciación universal
6	${\displaystyle P(y)\ }$	Desde (2) y (5) por Modus ponens
7	${\displaystyle Q(y)\ }$	Desde (6) y (4) por Modus ponens
8	${\displaystyle \forall x\,Q(x)}$	Desde (7) por Generalización
9	${\displaystyle \forall x\,(P(x)\rightarrow Q(x)),\forall x\,P(x)\forall x\,Q(x)}$	Resumen de (1) a (8)
10	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\forall x\,P(x)\rightarrow \forall x\,Q(x)}$	Desde (9) por Teorema de la deducción
11	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$	Desde (10) por Teorema de la deducción

En esta prueba, se utilizó la generalización universal en el paso 8. El teorema de la deducción es aplicable en los pasos 10 y 11 porque las fórmulas que son trasladadas no tiene variables libres.

• Lógica de primer orden
• Generalización apresurada
• Instanciación universal

• Esta obra contiene una traducción total derivada de «Universal generalization» de Wikipedia en inglés, concretamente de esta versión, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.