Es $\exists x(P(x) \to Q(x)) \equiv (\exists xP(x) \to \exists xQ(x))$ ?

Question

Mi intuición es que esta afirmación es falsa y aquí está mi prueba.

$\exists x(P(x) \to Q(x))$

$\exists x(\lnot P(x) \lor Q(x))$ utilizando la equivalencia lógica.

$\exists x\lnot P(x) \lor \exists x Q(x)$ utilizando las propiedades distributivas de $\exists$ en $\lor$ .

Asumiendo que Q(x) es siempre falsa, simplemente necesitamos 1 x tal que $\lnot P(x)$ es verdadera y eso hace que toda la afirmación sea verdadera. La otra expresión se puede transformar en esto:

$\exists xP(x) \to \exists xQ(x)$

$\lnot\exists xP(x) \lor \exists xQ(x)$ utilizando la equivalencia lógica.

$\forall x\lnot P(x) \lor \exists xQ(x)$

Si suponemos que Q(x) es siempre falsa, lo único que hace que esto sea cierto es que para todos los $\lnot P(x)$ sea cierto. Por ejemplo, el dominio podría ser todos los números enteros positivos y $P(x) = x \le 10$ . Para ser completos, supongamos $Q(x) = x \le -10$ .

Por lo tanto, el lado izquierdo de $\exists x(P(x) \to Q(x))$ es verdadero y el lado derecho de $(\exists xP(x) \to \exists xQ(x))$ es falso.

Estoy bastante seguro de que tengo razón, pero me gustaría que otro par de ojos vieran si he hecho alguna estupidez.

Answer 1

Sabes dos cosas, como señaló Jonny:

• $\exists x(P(x)\to Q(x))\equiv \neg\forall xP(x)\lor\exists x Q(x)\equiv\exists x\neg P(x)\lor\exists xQ(x)$
• $\exists xP(x)\to \exists xQ(x)\equiv\forall x\neg P(x)\lor\exists x Q(x)$

Por lo tanto, en nuestro intento de crear un contraejemplo, lo que realmente nos preocupa es si $\exists x\neg P(x)\equiv\forall x\neg P(x)$ . Esto debería ser bastante fácil de invalidar.

Contraejemplo: Sea el universo los números naturales. Sea $Q(x)$ y $P(x)$ sean los siguientes:

• $Q(x) : x$ es a la vez primo y no primo.
• $P(x) : x$ no es un número primo par.

Bien, $Q(x)$ es claramente siempre falso. Ahora, $\exists x\neg P(x)$ es cierto porque existe un número primo par, a saber $2$ . Sin embargo, $\forall x\neg P(x)$ es claramente falso, ya que $2$ es el único número primo par. Así, podemos ver que $\exists x\neg P(x) \not\equiv\forall\neg P(x)$ demostrando así que $$\exists x(P(x)\to Q(x))\not\equiv \exists xP(x)\to \exists xQ(x).$$

Answer 2

Yo dejaría de lado el asumir que Qx es siempre falso y me quedaría con los movimientos de equivalencia lógica.

La primera afirmación equivale a $\neg\forall x P(x) \lor \exists x Q(x)$ mientras que la segunda afirmación equivale a $\forall x \neg P(x) \lor \exists x Q(x)$

A partir de aquí todo lo que necesitas es un contraejemplo... recuerda que las afirmaciones son lógicamente equivalentes si su verdad se evalúa de la misma manera en todos los modelos. Así que necesitamos una estructura en la que una afirmación sea verdadera y la otra falsa. Quizás estamos en el universo de los números naturales y P significa que x es primo y Q significa que x es el número más grande.

Answer 3

Tu contraejemplo está bien.

Quizá le interese otro enfoque algo más formal, escrito al estilo de Dijkstra-Scholten y Gries-Schneider (véase también EWD1300 ), para encontrar todos contraejemplos.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $ Calculemos cuándo los dos lados son equivalentes:

$$\calc \langle \exists x :: P(x) \then Q(x) \rangle \;\equiv\; (\langle \exists x :: P(x) \rangle \then \langle \exists x :: Q(x) \rangle) \op\equiv\hints{write $ \;\phi \entonces \psi\; $ as $ \;\ no \phi \lor \psi\; $, twice}\hint{-- to make manipulations easier} \langle \exists x :: \lnot P(x) \lor Q(x) \rangle \;\equiv\; \lnot \langle \exists x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \op\equiv\hints{$ \;\exists\; $ distributes over $ \;\lor\\; $}\hint{-- because $ \;\exists\; $ is a kind of 'repeated disjunction'} \langle \exists x :: \lnot P(x) \rangle \lor \langle \exists :: Q(x) \rangle \;\equiv\; \lnot \langle \exists x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \op\equiv\hint{$ \;\lor\\; $ distributes over $ \;\equiv\; $ -- to simplify} (\langle \exists x :: \lnot P(x) \rangle \equiv \lnot \langle \exists x :: P(x) \rangle) \;\lor\; \langle \exists x :: Q(x) \rangle \op\equiv\hints{DeMorgan on right hand side of $ \;\equiv\; $}\hint{-- making both sides more alike} (\langle \exists x :: \lnot P(x) \rangle \equiv \langle \forall x :: \lnot P(x) \rangle) \;\lor\; \langle \exists x :: Q(x) \rangle \op\equiv\hint{split $ \;\equiv\; $ into $ \;\then\; $ and $ \Sigue desde aquí; $; $ \;\forall\then\exists\; $} (\langle \exists x :: \lnot P(x) \rangle \then \langle \forall x :: \lnot P(x) \rangle) \;\lor\; \langle \exists x :: Q(x) \rangle \op\equiv\hint{write $ \;\phi \entonces \psi\; $ as $ \;\ no \phi \lor \psi\; $} \tag{*} \lnot \langle \exists x :: \lnot P(x) \rangle \;\lor\; \langle \forall x :: \lnot P(x) \rangle \;\lor\; \langle \exists x :: Q(x) \rangle \endcalc$$

Así que tienes un contraejemplo siempre que la negación de $\ref *$ es cierto: $$ \tag{$ \no $*} \langle \exists x :: \lnot P(x) \rangle \;\land\; \langle \exists x :: P(x) \rangle \;\land\; \langle \forall x :: \lnot Q(x) \rangle $$ En otras palabras, un contraejemplo es cualquier $\;P(x)\;$ lo que es cierto para algunos $\;x\;$ y falso para algún otro, junto con cualquier $\;Q(x)\;$ que siempre es falso.