¿equivale a $\forall x\,\exists y\, Q(x, y)$ $\exists y\,\forall x\,Q(x, y)$?
Leí en el libro que el orden de los cuantificadores de hace una gran diferencia, así que me preguntaba si estas dos expresiones son equivalentes o no.
Gracias.
Respuestas
¿Demasiados anuncios?
Ciertamente que no. En que útil "loglish" dialecto (una casa de medio camino entre el lenguaje formal y natural en inglés), la primera dice
Para cualquier $x$, hay un $y$ tal que $Qxy$.
El segundo dice:
Para algunos $y$ $x$ son tales que $Qxy$.
Estos son muy diferentes. Comparar
Para cualquier número natural $x$, hay algún número $y$, de tal manera que $x < y$. Verdadero (para cualquier número, no hay uno más grande).
Para algún número natural $y$, cualquier número $x$ tomamos es tal que $x < y$. Falso (no hay ningún número mayor que todos los números!).
Una más de la observación general. Todo el punto de la cuantificador de la variable de notación es para exigir claridad en cuanto a la relación alcance de los operadores lógicos.
Para tomar un caso simple, considere el inglés "Todo el mundo no ha llegado todavía". Este es estructuralmente ambigua. Usted puede fácilmente imaginar contextos donde la naturaleza es la lectura "no Es el caso que todo el mundo ha llegado", y otros contextos donde los naturales de la lectura es "No todo el mundo ha llegado". Comparar, sin embargo,
$\neg\forall xAx$
$\forall x\neg Ax$
Aquí, en el lenguaje de la lógica de primer orden, el orden de los operadores lógicos se asegura de que cada frase tiene un único análisis, y no hay posibilidad de ambigüedad estructural.
DanV
Puntos
281
Porque yo realmente odio el mundo real analogías (después de un examen me fue forzado a leer casi 300 respuestas a murmurar "cada olla tiene una tapa" analogías), permítanme darles una forma matemática de la comprensión de este sin la evaluación de las fórmulas reales.
Deje $M$ ser arbitraria de la estructura de nuestro lenguaje, vamos a $A(x)=\{y\in M\mid M\models Q(x,y)\}$. Por lo tanto, dado un punto de $m\in M$ hemos partido de que el conjunto de $A(m)$ de todos aquellos que están satisfaciendo $Q$ con $m$.
La primera frase $\forall x\exists yQ(x,y)$ nos dice que por cada $m\in M$, $A(m)$ no está vacía.
La segunda frase $\exists y\forall xQ(x,y)$ nos dice que hay algo de $y$ tal que $y\in A(m)$ todos los $m$. Es decir, la intersección de todos los $A(m)$ no está vacío.
Podemos recurrir inmediatamente a la conclusión de que la segunda frase implica que la primera. Si la intersección de todos los $A(m)$'s no vacío, entonces ciertamente no $A(m)$ puede estar vacía.
Por otro lado también es muy claro que la segunda frase implica que la intersección de todos los $A(m)$'s no es vacío, todos ellos contienen al menos un punto común. La primera frase no establece tal requisito, por lo que no es difícil construir una estructura en la que la primera frase es cierta, pero la segunda es falsa.
Drew Jolesch
Puntos
11
Cambiar el orden de los cuantificadores es a menudo no es válido. En particular, podemos cambiar el significado de una declaración cuando se cambia el orden de los diferentes cuantificadores cuyo ámbito es el de toda la declaración - como en este caso - y por lo general es no válido para cambiar una de las principales cuantificador con un anidados uno.
En este caso, tenemos:
$$\forall x \exists yQ(x, y) \not\equiv \exists y \forall x Q(x, y)$$
Por ejemplo:
Deje $Q(x, y)$ significa que "x ama a y". Dominio de $x, y$ : personas
La mano izquierda iba a leer, de manera efectiva:
$\forall x \exists y Q(x, y)$: "Todo el mundo ama a alguien" (cada persona ama a alguien);El lado derecho iba a leer, de manera efectiva:
$\exists y \forall x Q(x, y)$: "Hay alguien a quien todo el mundo ama." O, alternativamente, "hay alguien que es amado por todo el mundo."
Esas no son en absoluto equivalentes declaraciones.
Gene Choin
Puntos
1
La respuesta es no.
Aquí es lo que me gusta pensar en ello me: permite un % diferente $\forall x \exists y Qxy$cada $y$ $x$ y $\exists y \forall x Qxy$ requiere el mismo trabajo de $y$de % los $x$.
A veces la gente confunde debido a esta construcción: "existe un $y$ % todo $x$tal que $Q(x, y)$ sostiene." La colocación de la "tal que" es de vital importancia.
Johannes
Puntos
141
Además de a respuesta detallada de @Asaf y de @amWhy, estoy tomando nota por ejemplo, tal vez, abre un trocito del camino. Considerar $M=\mathbb Z$ y $$Q(x,y): x+y=0$$ Obviously, for all $x\in\mathbb Z$, there is a $y\in\mathbb Z $ such that $Q(x,y) $ be a true statement. Now, think about this sentence: There is an $y\in\mathbb Z$ such that for all integers $x$, $x=-y$. Clearly, it is wrong. Because if for example $y=a$ then we can't write $-a=x$ when $x$ is freely moving alongside the set $\mathbb Z$. Por lo tanto, su reclamo no es cierto en general.
