Lógica de predicados, Prueba de validez. ¿Cómo eliminar la negación delante del cuantificador existencial?

Question

$\forall x~(P(x) \to (Q(x) \lor R(x))), \lnot \exists x~(P(x) \land R(x)) \vdash \forall x~(P(x) \to Q(x))$

Estoy atascado en cómo deshacerme de la negación en "$\lnot \exists x~(P(x) \land R(x))$" en este caso particular. Tengo una idea relativa de cómo abordar esta oración, donde primero uso la segunda premisa para eliminar el "$\exists x$" y luego obtener respectivamente el "$P(x_0)$" y "$R(x_0)$", luego usando la eliminación de "$\forall x$" para obtener "$P(x_0) \to (Q(x_0) \lor R(x_0))", lo que luego me permite usar el $P(x_0)$ de "$P(x_0) \land R(x_0)$" para eliminar el conectivo condicional que me permite tener dos subpruebas para eliminar la disyunción. Luego puedo hacer una introducción condicional dando "$P(x_0) \to Q(x_0)$" necesario y después solo introducción de $\forall x$ que me da $\forall x~(P(x) \to Q(x))$ lo que estoy buscando.

Mi problema es cómo deshacerme de la negación en la segunda premisa de esta oración o ¿voy en la dirección equivocada en este caso? Cualquier consejo sería útil. ¡Gracias!

Mi intento hasta ahora:

Answer 1

Estoy atascado en cómo deshacerme de la negación en "$\lnot \exists x~(P(x) \land R(x))$" en este caso particular. Tengo una idea relativa de cómo abordar esta oración, donde primero usando la segunda premisa eliminando el "$\exists x$" y luego obteniendo respectivamente el "$P(x_0)$" y "$R(x_0)$", luego después usar la eliminación de "$\forall x$" para obtener "$P(x_0) \to (Q(x_0) \lor R(x_0))", lo que me permite usar el $P(x_0)$ de la expresión anterior "$P(x_0) \land R(x_0)" para eliminar el conectivo condicional que me permite tener 2 sub-pruebas para eliminar la disyunción. Luego puedo hacer una introducción condicional dando "$P(x_0) \to Q(x_0)$" necesario y después simplemente introducir $\forall x$ que me da $\forall x~(P(x) \to Q(x))$ lo que estoy buscando.

Tienes la idea correcta. Sin embargo, deberías comenzar asumiendo $P(x_0)$ para un $x_0$ arbitrario, luego eliminar el cuantificador universal en la primera premisa para ese testigo, eliminar el condicional, y así eliminar la disyunción resultante. (Dado que tienes $P(x_0)$ y $Q(x_0)\lor R(x_0)$ en ese punto.)

En el caso izquierdo, $Q(x_0)$ se deriva trivialmente, mientras que en el caso derecho es donde ocurre la magia. A partir de $R(x_0)$ y el $P(x_0)$ asumido, deriva la existencia de $P(x_0)\land R(x_0)$, es decir $\exists x~(P(x)\land R(x)$, lo que contradiría la segunda premisa. Explota esa contradicción.

Luego introduce un cuantificador universal, deduciendo $\forall x~(P(x)\to Q(x))$ como se deseaba.

$\def\fitch#1#2{\quad\begin{array}{|l} #1\\\hline #2\end{array}}\fitch{1.\forall x~(P(x)\to(Q(x)\lor R(x))\hspace{10ex}\textsf{Premisa}\\2.\neg\exists x~(P(x)\land R(x))\hspace{18ex}\textsf{Premisa}}{\fitch{3.[x_0]\hspace{10ex}\textsf{Testigo Arbitrario}}{\fitch{4.P(x_0)\hspace{10ex}\textsf{Suposición}}{5.P(x_0)\to(Q(x_0)\lor R(x_0))\hspace{10ex}\textsf{Eliminación Universal}\\6.Q(x_0)\lor R(x_0)\hspace{10ex}\textsf{Eliminación Condicional}\\\fitch{7.Q(x_0)\hspace{10ex}\textsf{Suposición (Caso Izquierdo)}}{}\\8.Q(x_0)\to Q(x_0)\hspace{10ex}\textsf{Introducción Condicional}\\\fitch{9.R(x_0)\hspace{10ex}\textsf{Suposición (Caso Derecho)}}{10.P(x_0)\land R(x_0)\hspace{10ex}\textsf{Introducción de Conjunción}\\11.\exists x~(P(x)\land R(x))\ldots\hspace{10ex}\textsf{Introducción Existencial}\\12.\bot\hspace{10ex}\textsf{Eliminación de Negación}\\13.Q(x_0)\hspace{10ex}\textsf{Explotar (Ex Falsum Quodlibet)}}\\14.R(x_0)\to Q(x_0)\hspace{10ex}\textsf{Introducción Condicional}\\15.Q(x_0)\hspace{10ex}\textsf{Eliminación de Disyunción}}\\16.P(x_0)\to Q(x_0)\hspace{10ex}\textsf{Introducción Condicional}}\\17.\forall x~(P(x)\to Q(x))\hspace{10ex}\textsf{Introducción Universal}}$

Answer 2

Idea básica: Suponer P(a). Deducir Q(a) dentro del ámbito de P(a).

Para una pista sobre cómo deshacerse de la negación, note que la introducción existencial no tiene restricciones, ¿verdad?

Más detalle:

Suponga (P(a)$\land$R(a)), donde 'a' es una constante. Entonces puede obtener una contradicción (pista: use la introducción existencial). Por lo tanto, puede inferir $\lnot$(P(a)$\land$R(a)). Pero, luego 'a' aparecerá y no aparecerá en ninguna otra suposición realizada. Por lo tanto, tendrá la capacidad de utilizar la introducción universal, para tener ∀x$\lnot$(P(x)$\land$R(x)). Luego, utilizando una ley de De Morgan, tiene ∀x($\lnot$P(x)$\lor$$\lnot$R(x)).

Luego suponga P(a). Con la eliminación universal puede inferir ($\lnot$P(a)$\lor$$\lnot$R(a)). Por lo tanto, puede lograr llegar a $\lnot$R(a). Además, derive (Q(a)$\lor$R(a)) usando la primera premisa y P(a). Entonces, puede derivar Q(a).

Luego descargue P(a) dando como resultado (P(a)$\rightarrow$Q(a)). Y note que 'a' no aparece en ninguna suposición aún vigente para el último paso.

Answer 3

En lugar de intentar eliminar la negación frente a lo existencial, utiliza esa afirmación como parte de una demostración por contradicción.

Para ser un poco más específico: necesitas demostrar que todo P es un Q. Bien, toma cualquier objeto arbitrario que sea un P. Ahora supongamos (aquí comienza la prueba por contradicción) que no es un Q. Bueno, por la premisa 1, sabemos que el objeto es un Q o un R ... pero acabamos de suponer que no es un Q, por lo que debe ser un R. Pero entonces el objeto es tanto un P como un R, así que hay algo que es un P y un R (probablemente harás una Introducción existencial en este punto) y eso contradice la premisa 2. Entonces, la suposición debe ser retirada, y por lo tanto, el objeto es un Q. Finalmente, dado que el objeto era arbitrario, podemos decir que cualquier Q es un R.

Ahora, no conozco las reglas específicas de tu sistema de demostración, pero es probable que pueda implementar esta idea de demostración. ¡Buena suerte!