¿Por qué no prohibir los cuantificadores anidados sobre la misma variable?

Question

La gente parece pensar (1, 2, 3) que un wff puede tener cuantificadores anidados sobre la misma variable, por ejemplo, $\forall x(Px \wedge \exists x Qx)$.

Sin embargo, considere el siguiente argumento:

1. $\forall x \exists y Pxy$ (Premisa)
2. $\exists y P\hat{x}y$ (1, $\forall$E)
3. $\forall y \exists y Pyy$ (2, $\forall$I)

Evidentemente, esto no es válido, pero lo que está mal con él? De acuerdo a wikipedia, la aplicación de la $\forall$I está mal porque $y$ se produce en 2.

Aquí es otro argumento no válido:

1. $\forall x Pxc$ (Premisa)
2. $\exists x \forall x Pxx$ (1, $\exists$I)

Esta es considerada inválida por un motivo similar: la aplicación de la $\exists$I está mal porque $x$ se produce en 1.

Pero no necesitaríamos estas restricciones si sólo nos prohibió cuantificadores anidados sobre la misma variable. Esto parece como una regla más simple y no nos vamos a perder el poder expresivo. ¿Alguien configurar la lī ogica de esta manera?

Answer 1

Podría llevarse a cabo, como se describe en las otras respuestas.

Pero no iba a hacer la captura de evitar la sustitución más fácil de definir, así que no hay ningún beneficio real.

Por otro lado, nos gustaría perder a veces la propiedad útil que una frase puede ser sustituido en cualquier contexto sin necesidad de mirar dentro de él.

También sería más difícil de definir de local vuelve a escribir de una fórmula que introducir una nueva variable y su cuantificador en algún lugar en el árbol de análisis. En lugar de sólo mirar hacia abajo desde el nuevo cuantificador para asegurarse de que no captura nada nos gustaría también necesitan mirar hacia arriba para asegurarse de que no la sombra de nada. La necesidad de "mirar en ambas direcciones" podría fuertemente complicar la estructura de una definición inductiva.

Answer 2

El problema es que ese tipo de regla que requiere el conocimiento de los contenidos de menor wffs. Piense acerca de las otras normas - ninguno de ellos dice nada acerca de "si tal y tal aparece un símbolo en el interior...". La regla de que usted propone sería algo como esto: "Si $\varphi$ es un wff, $v$ es una variable, y $\varphi$ no incluye las cadenas '$\forall v$' o '$\exists v$', $\forall v\varphi$ $\exists v\varphi$ son wffs." Esto es mucho más complicado que cualquiera de las reglas estándar - y, porque "mira dentro" $\varphi$, hace que las técnicas estándar como la inducción de la complejidad de la fórmula considerablemente más difícil. Piense en ello como una prueba por inducción (ordinario aritmética) en las que por alguna razón tenían que utilizar diferentes reglas en el momento $n$ un $2$ en su expansión decimal. Técnicamente no sería un obstáculo real - como la alternativa reglas tenían la misma cantidad de energía, que podrían demostrar lo que usted necesita para probar - pero sería super incómodo.

También realidad no iba a ayudar a las situaciones que estamos mirando. Los argumentos que presenta todavía estaría mal, y la única razón por la que todavía sería "porque usted no puede hacer eso"; sería simplemente "no se puede escribir la frase" en lugar de "usted no puede utilizar esta regla como esa". Así que, para resumir: la adición de la regla para la construcción de wffs llegaría en el costo de la simplicidad en un montón de pruebas en el meta-lenguaje, y no mejorar la situación lo suficiente como para hacer la diferencia.

Answer 3

En el primer ejemplo, $y$ no ocurre libre en el paso 2 y en el segundo ejemplo, $x$ no ocurre libre en el paso 1, por lo que el problema no es con la variable de repeticiones en los antecedentes para la inferencia de los pasos. Lo que está mal en ambos ejemplos es que no has hecho sustituciones correctamente al derivar la succedents de la inferencia a paso. Cuando usted sustituto $y$ $\hat{x}$ $\exists y P\hat{x}y$ usted necesita para cambiar el nombre de la variable vinculada $y$ para evitar ser "capturado" por el de sustitución. El resultado debe ser algo parecido a $\exists y'~Pyy'$.

Answer 4

En Barendregt del Cálculo Lambda libro, él establece una variable de la convención.

Reconociendo que los términos de $\lambda x.x$ $\lambda y.y$ $\alpha$convertible, y en cierto sentido, "el mismo", podemos decir que en cualquier prueba que implican finitely/contables de muchos términos, se $\alpha$-se convierten, de manera que las variables enlazadas son todos distintos, y distinto del de las variables libres.

Esto evita variables sin estar obligado en las sustituciones.

No estoy tan familiarizado con la lógica de la literatura, pero no me sorprendería si un convenciones similares existe.

El efecto sería que una fórmula como $\forall y \exists y P(y,y)$ es de hecho bien formado, pero para mayor claridad, podríamos, en lugar de escribir el "equivalente" de la fórmula $\forall x \exists y P(y,y)$.

Answer 5

Anidación de los cuantificadores no es exactamente el problema con la eliminación-introducción confusión.

Intento que el argumento de la realidad utilizando la supuesta niño problema: $\forall x\,(Px \wedge \exists x\,Qx)$

1. $\forall y\,(Py \wedge \exists x\,Qx)$ como premisa.

2. $Pa \wedge \exists x\,Qx$ través $\forall$ eliminación arbitraria de las $a$.

3. $\forall x\,(Px \wedge \exists x\,Qx)$ través $\forall$ introducción de arbitrario $a$.

Esto no es ningún problema. Cuando la introducción de un universal quatifier, usted puede de manera segura alfa-reemplazar la arbitrariedad de la testigo, $a$, con cualquier variable que no se encuentra libre dentro de cualquier ámbito compartido. Aquí, $x$ no se producen libres, como es obligado por el existencial.

Su argumento original ¿ ha $x$ ocurren dentro de un ámbito compartido. Fue esto lo que provocó el problema, no la anidación de los cuantificadores.