4.6: Contraejemplos (reprise)

Hemos estado discutiendo pruebas en este capítulo, pero debes tener en cuenta que los contraejemplos también son una parte importante de la lógica:

Para demostrar que una deducción es válida, proporcionar un comprobante.
Para demostrar que una deducción no es válida, proporcionar un contraejemplo.

Ejemplo\(4.6.1\).

Demostrar que la siguiente deducción no es válida:\[\exists x,(x \in A), \quad \therefore \forall x,(x \in A).\]

Scratchwork. Para hacerse una idea de lo que está pasando, puede ser útil traducir la deducción al inglés. Por ejemplo, podríamos usar la clave de simbolización

\(\mathcal{U}\): cosas en la mesa de la cocina

\(A\): aplica sobre la mesa de la cocina

En este marco, la deducción se convierte en:

Hay una manzana en la mesa de la cocina... Todo en la mesa de la cocina es una manzana.

Esta deducción obviamente no es válida: es fácil imaginar una situación en la que una cosa en la mesa de la cocina es una manzana, pero otra cosa en la mesa de la cocina no es una manzana.

Para encontrar la solución oficial, haremos algo análogo, pero usando la notación de Lógica de primer orden, en lugar de hablar de manzanas y mesas. Para construir un contraejemplo, queremos que la hipótesis de la deducción sea verdadera y que la conclusión sea falsa.

• Para que la hipótesis sea\(\exists x,(x \in A)\) cierta, necesitamos algo de lo que ser un elemento\(A\). Por ejemplo, podríamos dejar\(1 \in A\).
• Para hacer\(\forall x,(x \in A)\) falsa la conclusión, queremos que su negación sea cierta:\(\exists x,(x \notin A)\) queremos ser verdad. Por ejemplo, podríamos arreglar eso\(2 \notin A \text {. }\).

Para satisfacer las dos condiciones anteriores, dejamos\(A =\{1\}\). Ya que 1 y 2 son los únicos elementos mencionados en la discusión, podemos dejar\(\mathcal{U}=\{1,2\}\). Esto da como resultado el contraejemplo que esperábamos encontrar.

Solución

Brindamos un contraejemplo. Vamos\[\mathcal{U}=\{1,2\} \text { and } A=\{1\}\]
Entonces:\[1 \in A \text { is true, so } \exists x,(x \in A) \text { is true, so the hypothesis is true, }\]
pero\[2 \notin A, \text { so } \forall x,(x \in A) \text { is false, so the conclusion is false. }\]
Como tenemos una situación en la que la hipótesis es cierta, pero la conclusión es falsa, la deducción no es válida.

Ejemplo\(4.6.2\).

Demostrar que la siguiente deducción no es válida:

Hipótesis:

1. \(\forall x,((x \in A) \vee(x \in B))\)
2. \(A \neq \varnothing\)
3. \(B \neq \varnothing\)

Conclusión:\(\exists x,((x \in A) \&(x \in B)) .\)

Scratchwork. Para construir un contraejemplo, queremos que todas las hipótesis de la deducción sean verdaderas y que la negación de la conclusión sea cierta. La negación de la conclusión es la\[\forall x,((x \notin A) \vee(x \notin B)) ,\]
que lógicamente equivale a\(4.6.3\)\[\forall x,((x \in A) \Rightarrow(x \notin B))\]
Ahora:

• Para que la Hipótesis 2 sea cierta, podemos dejar\(1 \in A\).
• Para que la Hipótesis 3 sea cierta, debemos poner algo en el set\(B\). No obstante, es importante señalar que (\(4.6.3\)) nos dice\(1 \notin B\), por lo que debemos poner algo más en\(B\). Por ejemplo, podemos dejar\(2 \in B\).
• Ahora, después\(A\) y se\(B\) han construido, podemos hacer que la Hipótesis 1 sea cierta dejando\(\mathcal{U} = A \cup B\).

Para satisfacer las tres condiciones, podemos dejar\(A=\{1\}, B=\{2\}, \text { and } \mathcal{U}=A \cup B=\{1,2\}\).

Solución

Brindamos un contraejemplo. \[\mathcal{U}=\{1,2\}, \quad A=\{1\}, \quad \text { and } \quad B=\{2\}\]
Entonces deja:

1. Tenemos
   • \(1 \in A\)es verdad, así\((1 \in A) \vee(1 \in B)\) es verdad, y
   • \(2 \in B\)es verdad, así\((2 \in A) \vee(2 \in B)\) es verdad.
     Ya que 1 y 2 son los únicos elementos de\(\mathcal{U}\), esto implica, para cada\(x\), eso\((x \in A) \vee(x \in B)\) es cierto. Entonces la Hipótesis 1 es cierta.
2. \(1 \in A\), entonces\(A \neq \varnothing\). De ahí que la Hipótesis 2 sea cierta.
3. \(2 \in B\), entonces\(B \neq \varnothing\). De ahí que la Hipótesis 3 sea cierta.

Sin embargo:

• \(1 \notin B\), así\((1 \in A) \& (1 \in B)\) es falso, y
• \(2 \notin A\), así\((2 \in A) \&(2 \in B)\) es falso.

Ya que 1 y 2 son los únicos elementos de\(\mathcal{U}\), esto implica que no hay\(x\) para lo cual la aseveración\((x \in A) \&(x \in B)\) es cierta. De ahí que la aseveración\(\exists x,((x \in A) \&(x \in B))\) sea falsa; es decir, la conclusión de la deducción es falsa. Ya que tenemos una situación en la que la hipótesis es cierta, pero la conclusión es falsa, la deducción no es válida.

Ejemplo\(4.6.4\).

Explique cómo sabe que la siguiente deducción no es válida:\[X \cap Y \subset D, \quad \therefore X \subset Y \cup D .\]

Solución

Brindamos un contraejemplo. Vamos\(X=\{1\}, Y=\{2\}, \text { and } D=\{3\}\). Entonces\(X \cap Y=\{1\} \cap\{2\}=\varnothing\), entonces\(X \cap Y \subset D\), porque el conjunto vacío es un subconjunto de cada conjunto. Esto quiere decir que la hipótesis es cierta.

Sin embargo,\(Y \cup D=\{2\} \cup\{3\}=\{2,3\} .\). Por lo tanto\[1 \in\{1\}=X \text { and } 1 \notin\{2,3\}=Y \cup D, \text { so } X \not \subset Y \cup D .\]
Esto quiere decir que la conclusión es falsa.

Ya que tenemos una situación en la que la hipótesis es cierta, pero la conclusión es falsa, la deducción no es válida.

Ejercicio\(4.6.5\).

Explique cómo sabe que cada una de las siguientes deducciones no es válida.

1. \(\exists x,(x \in A), \quad \exists x,(x \in B), \quad \therefore \exists x,((x \in A) \&(x \in B))\)
2. \(\forall a \in A, \exists b \in B,(a \neq b), \quad A \neq \varnothing, \quad \therefore \forall b \in B, \exists a \in A,(a \neq b)\)
3. \(A \neq B, \therefore A \cup B \neq A\)
4. \(\forall x \in A,(x \notin B), \quad \forall x \in B,(x \notin A), \therefore A \neq B \text {. }\)

Ejercicio\(4.6.6\).

Explique cómo sabe que cada una de estas deducciones no es válida.

1. \(A \cup B \subset E \cup F, \quad \therefore A \cap B \subset E \cap F\)
2. \(A \subset B, X \subset Y, \quad \therefore A \backslash X \subset B \backslash Y\)
3. \(A \cap B \neq \varnothing, B \subset C, \quad \therefore A \subset C\)
4. \(\exists x,((x \in P) \&(x \notin Q)), \quad \therefore \forall x,((x \in P) \Rightarrow(x \notin Q))\)
5. \(\forall x \in X,(x R x), \quad \therefore \forall x_{1} \in X, \forall x_{2} \in X,\left(\left(x_{1} R x_{2}\right) \Rightarrow\left(x_{2} R x_{1}\right)\right)\)

Ejercicio\(4.6.7\).

Determina si cada una de las siguientes deducciones es válida, y justifica tu respuesta dando una prueba o un contraejemplo.

1. \(\exists u \in U,(u \notin V), \quad \therefore \forall u \in U,(u \notin V)\)
2. \(\forall x,((x \in S) \Rightarrow(1 \in T)), \quad S \neq \varnothing, \quad \therefore 1 \in T\)
3. \(\forall a \in A,(a \in B), \quad \forall b \in B,(b \in C), \quad \therefore \forall a \in A,(a \in C) .\)
4. \(D \cup E \neq \varnothing, \quad D \subset F, \quad \therefore D \cap F \neq \varnothing\)
5. \(\forall a_{1} \in A, \forall a_{2} \in A,\left(\left(a_{1} R a_{2}\right) \vee\left(a_{2} R a_{1}\right)\right), \quad 2 \in A, \quad \therefore 2 R 2 .\)