Restricciones a la generalización universal

Question

Artículo de Wikipedia sobre la generalización universal no parece dar una explicación satisfactoria de las restricciones sobre cuándo se puede utilizar:

Supongamos que $\Gamma$ es un conjunto de fórmulas, $\varphi$ una fórmula, y $\Gamma \vdash \varphi(y)$ se ha derivado. La regla de generalización establece que $\Gamma \vdash \forall x \varphi(x)$ puede derivarse si $y$ no se menciona en $\Gamma$ y $x$ no se produce en $\varphi$ .

A continuación, el artículo ofrece un ejemplo de utilización incorrecta de la UG para derivar $\exists z\exists w(z\neq w) \vdash \forall x(x\neq x)$ con las restricciones dadas ciertamente violadas. Sin embargo, ¿la siguiente modificación de la "prueba" no estaría de acuerdo con las restricciones?

$\exists z\exists w(z\neq w)$

$\exists w(y\neq w)$

$y\neq x$

$\forall\alpha(\alpha\neq x)$

$x\neq x$

Aquí, la generalización del paso 4 se ha modificado para utilizar $\alpha$ como variable de enlace del cuantificador, lo que debería estar permitido, ya que $\alpha$ no se produce en $y\neq x$ y $y$ no se produce en el supuesto $\exists z\exists w(z\neq w)$ Sin embargo, esto lleva a una instanciación universal que es claramente falsa. ¿Es la $\Gamma$ de las restricciones se refiere a todos los pasos anteriores de la prueba, no sólo a los supuestos? Si es así, ¿esto no invalidaría la prueba dada más adelante en el artículo que incluye los pasos $P(y)\to Q(y)$ y $P(y)$ antes de generalizar $Q(y)$ ? ¿La presencia de la instanciación existencial impone de alguna manera más restricciones a la generalización universal, contando el existencial instanciado como una mención de la variable introducida?

Answer 1

Este tipo de cosas sólo pueden responderse mirando una set de las reglas de inferencia, en lugar de examinar una regla de inferencia a la vez. Este es un defecto inherente a la forma en que Wikipedia cubre las reglas de inferencia, porque las reglas que son sólidas individualmente pueden no serlo cuando se combinan, como muestra la deducción en la pregunta.

He aquí cómo se resuelve el problema de la pregunta en el libro de texto de lógica de Mendelson, que sí utiliza un sistema deductivo al estilo de Hilbert. Recordemos que la deducción de $\phi(c)$ de $(\exists x)\phi(x)$ como en los dos primeros pasos de la deducción en la pregunta, se llama instanciación existencial. En el sistema de Mendelson, esto no se formaliza como una regla de inferencia, sino que se trata como una extensión definitoria de la teoría original, en la que un nuevo símbolo constante $c$ se añade junto con un nuevo axioma $\phi(c)$ . Ahora bien, la versión de Mendelson de la generalización universal es justo eso de $\phi$ podemos deducir $(\forall x)\phi$ para cualquier variable $x$ . Por lo tanto, no hay manera de pasar del paso 3 al 4 de la deducción anterior, porque la regla de generalización universal de Mendelson no tiene la capacidad de sustituir el símbolo constante $y$ con una variable $\alpha$ en la fórmula que tiene un cuantificador adjunto. De este modo, Mendelson puede evitar cualquier restricción sobre la variable en la regla de generalización universal.

En un sistema deductivo diferente en el que la regla de generalización universal sí tiene la capacidad de sustituir símbolos constantes por variables, tienes razón en que habrá que añadir restricciones adicionales si los símbolos constantes se pueden añadir por instanciación existencial. Por ejemplo, si tomamos como convención que cualquier símbolo constante introducido por instanciación existencial ha sido mencionado en $\Gamma$ que también evitaría este tipo de problemas.

Por supuesto, la prueba real no es si parece que se han evitado los problemas; la prueba es si se pueden demostrar los teoremas de solidez y completitud para un sistema deductivo concreto. Lo más fácil es elegir un libro que tenga un sistema que se ajuste a su gusto, y luego atenerse escrupulosamente al sistema de ese libro. Así se evitan todos estos problemas sutiles sobre reglas de inferencia que no coinciden.

Answer 2

Creo que esta es una excelente pregunta que puede responderse de dos maneras.

El primera forma Como en la gran respuesta anterior, se trata de asegurarse de que podemos entender las restricciones para la instanciación y la generalización universales, de modo que la lógica de primer orden (FOL) pueda emplearse de forma útil y adecuada.

El segunda vía es darnos cuenta de que nuestras intuiciones sobre "para todos" y "algunos" como cuantificadores no coinciden con los dictados de la FOL para $\forall$ y $\exists$ .

Una discusión completa aquí llevaría demasiado tiempo y espacio. Pero basta con decir que los objetivos sistémicos de consistencia ( $\vdash A$ si y sólo si $\models A$ ) y integridad ( $\models A$ si y sólo si $\vdash A$ ) es todo lo que necesitamos para un FOL, a menos que tengamos otros objetivos que no sean los esenciales para un FOL. Por ejemplo, solidez donde el requisito es $A \vdash B$ si y sólo si $A \models B$ . La solidez es un requisito idiosincrásico pero habitual que es el "bugaboo", en mi opinión, y tenemos que distinguirlo de la consistencia. El requisito de la generalización universal y de la coherencia es que preservemos la verdad lógica . El requisito de solidez es que preservemos verdad . Las dos cosas son muy diferentes y creo que todavía no entendemos lo que está pasando en este sentido.

Hay agujeros en los fundamentos de FOL que tenemos que discutir. Esta pregunta es una belleza en ese sentido.