Demostrar o refutar la validez: $(\forall x \exists y (P(x) \supset Q(y))) \supset(\exists y \forall x (P (x) \supset Q(y)))$

Question

He trabajado en esta fórmula $(\forall x \exists y (P(x) \supset Q(y))) \supset (\exists y \forall x (P (x) \supset Q(y)))$ para probarlo o refutarlo.

Primero, tuve la tentación de refutarlo, pero cambié de opinión.

Escribí "para todo x que existe algún y satisface la condición correspondiente", y "existe algún y que para todo x satisface la condición correspondiente". Creo que estas afirmaciones se refieren a la misma idea.

¿Alguna sugerencia?

Answer 1

En el contexto habitual de las estructuras no vacías, la afirmación es válida, lo que significa que es verdadera en todos los modelos. Una forma de ver esto es que si hay algún $y$ en la estructura para la que $Q(y)$ se mantiene, entonces la afirmación es verdadera, ya que siempre podemos elegir que $y$ y esto hará que $Q(y)$ verdadera y por lo tanto la implicación final verdadera, independientemente de cualquier $x$ y, por tanto, toda la implicación es cierta. De lo contrario, estamos en el caso de que $Q(y)$ es siempre falso, en cuyo caso $P(x)\to Q(y)$ es lógicamente equivalente a $\neg P(x)$ por lo que la cuantificación sobre $y$ pasa a ser irrelevante (siempre que la estructura no sea vacía). Así que de nuevo la afirmación es verdadera. Así que la afirmación es verdadera en cualquier estructura no vacía.

Editar. Mientras tanto, en el contexto de la lógica de primer orden que permite la estructura vacía (que es un poco inusual, y que sólo es posible si su lenguaje no tiene símbolos constantes), entonces la declaración no es válida, ya que es falsa en la estructura vacía. Esto se debe a que todos los enunciados universales se mantienen vacíos en la estructura vacía y todos los enunciados existenciales fallan en la estructura vacía, por lo que el antecedente es verdadero y la conclusión es falsa, por lo que la implicación falla en la estructura vacía.

Conclusión: su afirmación es válida si el lenguaje tiene símbolos constantes; válida si su lógica no permite la estructura vacía; pero en caso contrario no es válida.

Answer 2

$(\forall x \exists y (P(x) \supset Q(y))) \supset (\exists y \forall x (P(x) \supset Q(y)))$ La fórmula no es válida. Considera la siguiente idea: $P^M$ es la relación que {x : x se mueve primero} $Q^M$ es la relación que {x : x gana el juego} Para la parte izquierda de la implicación $(\forall x \exists y (P(x) \supset Q(y)))$ indica que para todos los $x$ hacer el primer movimiento, existe algún $y$ que gana el juego. Sin embargo, considerando la parte derecha de la implicación $(\exists y \forall x (P(x) \supset Q(y)))$ existe algún $y$ que supera todos los primeros movimientos de $x$ . Esto es obviamente diferente y más difícil que la parte izquierda de la implicación, que puede ser falsa mientras que la primera parte es verdadera por lo que hace que la teoría sea falsa. La idea es de esta página .