¿Es esta una prueba válida de que A = B dado A B = A B?

Question

Aquí está mi prueba. Mi instructor afirma que es inválida porque no utilicé una tabla de pertenencia a un conjunto, y que el uso de una tabla de verdad lógica predicativa es inválido.

Eso no tiene sentido para mí. ¡Si puedo hacer S := { x | P(x) }, entonces obviamente debería poder usar lógica predicativa en los miembros de los conjuntos!

Dados 2 conjuntos A y B tales que A  B = A  B, ¿qué se puede concluir sobre A y B?

A  B = A  B                                                           reformulación

x(x  A  B  x  A  B)                                               definición de igualdad de conjuntos

x(x  A  x  B  x  A  x  B)                                       pertenencia al conjunto distribuida sobre unión e intersección

p(x) := x  A

q(x) := x  B

p    q    p  q    p  q    p  q  p  q    p  q

T    T      T        T            T            T

T    F      F        T            F            F

F    T      F        T            F            F

F    F      F        F            T            T

x(x  A  x  B)                                                        equivalencia lógica (p  q  p  q  p  q)

x(x  A  x  B  x  B  x  A)                                        equivalencia lógica (p  q  q  p  p  q)

x(x  A  x  B)  x(x  B  x  A)                                    cuantificador universal distribuido sobre conjunción

A  B  B  A                                                            definición de subconjunto

A = B                                                                     definición de igualdad de conjuntos

Vemos que los conjuntos A y B son iguales. A y B pueden ser ambos el conjunto vacío.

Entonces, ¿mi prueba es válida?

Editando: después de una reflexión más profunda, creo que el punto de controversia puede ser el uso de una tabla de verdad para demostrar la equivalencia lógica sobre un dominio infinito. Esta prueba puede no ser válida para conjuntos infinitos. En su lugar, podría demostrar la equivalencia lógica p q p q p q de otra manera.

Answer 1

Tu razonamiento es perfectamente válido. En el punto en el que utilizas una tabla de verdad para mostrar una equivalencia proposicional, ya estás mirando un $x$ (a la vez), por lo que las posibilidades que necesitas considerar son solo las cuatro filas de tu tabla.

Formalmente, una vez que has establecido la equivalencia proposicional $$ (p\land q)\leftrightarrow(p\lor q) \quad\equiv\quad p\leftrightarrow q $$ ahora estás autorizado a sustituir cualquier cosa por $p$ y $q$, y será una equivalencia válida, incluso fórmulas de la lógica de predicados.

---

(Es un poco largo el camino, sin embargo. Es más rápido ver $$ A \subseteq A \cup B = A \cap B \subseteq B $$ y viceversa, entonces $A\subseteq B$ y $B\subseteq A$, y por lo tanto los conjuntos son iguales).

Answer 2

Su prueba está bien. Lo que ha demostrado $(x\in A\land x\in B)\iff(x\in A\lor x\in B)$ es equivalente a $(x\in A)\iff(x\in B)$ se extiende a todos los $x$ sin problemas; si $\phi(x)$ es equivalente a $\psi(x)$, $\forall x(\phi(x))$ es equivalente a $\forall x(\psi(x))$.

Answer 3

Déjame mostrarte una demostración estilo Fitch que corresponde a tu razonamiento (correcto), para asegurarme de que entiendas por qué es válida:

---

Dados cualquier conjunto $A,B$ tal que $AB = AB$:

  Dado cualquier objeto $x$:

    $xAB xAB$.

    Por lo tanto $xA xB xA xB$.

    Sea $P : xA$.

    Sea $Q : xB$.

    Entonces $PQ PQ$.

    Por lo tanto $P Q$.   [según la tabla de verdad que proporcionaste]

    Por lo tanto $xA xB$.

  Por lo tanto $A = B$.

---

Nota que realizas el misma razonamiento para cualquier objeto dado $x$, así que aunque los $P,Q$ en la demostración anterior pueden diferir en valor de verdad para diferentes $x$, sigue siendo válido en cada caso que $P Q$, y por lo tanto obtienes la conclusión que buscas. Si tu instructor no puede entender esto, pídele que te dé cualquier conjuntos $A,B$ tal que $AB = AB$ y cualquier objeto $x$ y sigue explícitamente la demostración para mostrar (mediante un solo uso de la tabla de verdad) que $xA xB$. Si está claro que no puede evitar tu conclusión sin importar qué $A,B,x$ te dé, entonces has ganado. (Esto se llama semántica de juegos, por cierto, y te recomiendo que pienses en los cuantificadores de esta manera para comprender completamente el significado del orden de cuantificación).