No puedo ver la intuición detrás de la validez de esta fórmula:$\exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$

Question

Sé que

$$\vdash_{\mathcal G}\exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$$

(He leído y hecho sintáctico prueba de ello.)
Y por lo tanto también

$$\models \exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$$

Por la solidez de FOL.

Pero no puedo entender cómo esta fórmula puede ser válida. Se ve mal para mí. La forma en que lo leí es: si existe alguna $x$ e $y$ tal que $P(x,y)$, luego forall $z$ y algunos $w$, $P(z,w)$. Pero ¿cómo puede ser válido?

El orden de los cuantificadores es significativo en FOL, por lo que podría ser más sencillo considerar la posibilidad de una fórmula lógicamente equivalente en una forma más simple. Esta fórmula puede ser reescrito para una fórmula en Forma Normal Prenex, como por ejemplo este:

$$\exists x \forall y \forall z \exists w: P(x,y) → P(z,w)$$

Pero esta fórmula no se parece a ella es válida, ya sea. Aquí es un intento de un contra-ejemplo en la forma de una interpretación de la fórmula (estructura de la misma): Vamos a $P = \{0\} \times \mathbb{N}$. A continuación, $P(0,x)$ para todos los $x \in \mathbb{N}$, pero no es $w \in \mathbb N$ s.t. $P(z,w)$ para todos los $z \in \mathbb N$. De hecho, sólo hay un $z \in \mathbb N$ s.t. $P(z,w)$ mantiene para algunos $w$, es decir,$z = 0$.

Answer 1

Esto es sólo el Bebedor de la Paradoja en el disfraz.

Nota los siguientes:

$$\exists x(\exists yP(x,y) → \forall z \exists xP(z,x))\iff \exists x(\exists yP(x,y) → \forall y \exists xP(y,x)).$$

Denota el predicado $\exists x_2P(x_1,x_2)$ por $D(x_1)$ se convierte en el objeto de declaración en

$$\exists x(D(x)\to \forall yD(y)).$$

Si me permite reescribir esto como $\exists x(\neg D(x)\lor \forall yD(y))$, entonces creo que es intuitivo pensar de esto es como decir "ya sea que alguien no bebe, o todo el mundo lo hace".

Tenga en cuenta que esto no es lo que esta fórmula se transmite inmediatamente. La declaración de "ya sea que alguien no bebe, o lo hace todo el mundo" debe ser formalizado como $\exists x\neg D(x)\lor \forall yD(y)$, pero son equivalentes, y dado que esta es una cuestión de intuición, creo que esta lo suficientemente cerca.

Si es que cualquier ayuda, vea mi comentario aquí.

Answer 2

Suponiendo que el universo no está vacío, considere dos casos:

1. $\forall x\ \exists y\ P(x,y)$.

   Aquí su fórmula es verdadera, porque la conclusión de la implicación es trivialmente cierta.

2. $\exists x\ \forall y\ \neg P(x,y)$.

   Aquí su fórmula es verdadera, porque para ese$x$ tenemos$\neg P(x,x)$ y la premisa de la implicación es falsa.

De hecho, su fórmula es muy similar a la reordenación de cuantificadores, a saber:

PS

Espero que esto ayude $$\exists x\ \forall y\ P(x,y)\ \to\ \forall y\ \exists x\ P(x,y).$

Answer 3

Pero la lectura :

si existe alguna $x$ e $y$ tal que $P(x,y)$, entonces para todos los $z$ y algunos $w$, $P(z,w)$

es no correcto; el primero $\exists$ está "fuera" de los paréntesis.

Pruebe con un "informal", argumento que, a partir de la reescritura de la fórmula :

$∃x(\lnot ∃yP(x,y) \lor ∀z∃wP(z,w))$

puede ver inmediatamente que no se puede "mover " dentro" de la primera $\exists$ sin cambiar el significado de la fórmula.

Si recordamos que podemos "distribuir" $\exists$ sobre $\lor$, debido a $\exists$ "es" como un "inifinite" disyunción", tenemos que nuestra fórmula es "equivalente" a :

$∃x(\lnot ∃yP(x,y)) \lor ∃x∀z∃wP(z,w)$

que es :

$\lnot ∀x∃yP(x,y) \lor ∃x∀z∃wP(z,w)$.

En la segunda tensión dialéctica, el cuantificador $\exists x$ no hace ningún tipo de trabajo, debido a que $x$ en no libre en él; por lo tanto, olvidarse de él.

Por último, tenemos :

$\lnot ∀x∃yP(x,y) \lor ∀z∃wP(z,w)$

que es "claramente" válido.

Answer 4

La intuición es clara, tome$x$ para que sea un elemento sin$y$ correspondiente, de manera tal que$P(x,y)$, si eso es posible. Entonces la hipótesis será falsa, y la afirmación verdadera. Por otro lado, si por cada$x$ hay un$y$,$P(x,y)$, entonces la conclusión es correcta y puede tomar cualquier elemento para$x$.