¿Cuándo NO usaría una doble implicación al probar la igualdad entre conjuntos?

Question

Actualmente estoy estudiando cómo probar conjunto de igualdades.

Para esto, hay un ejemplo en mi libro que va de esta manera:

Demostrar los siguientes: $A-(B\cup C) = (A-B)\cap (A-C)$

Tenemos que demostrar las siguientes dos proposiciones: $$A-(B\cup C)\subseteq (A-B)\cap (A-C)$$ and also $$(A-B)\cap (A-C) \subseteq A-(B\cup C)$$

Para ello, vamos a hacer ambas cosas con una sola equivalencia: $$a\in A - (B\cup C) \leftrightarrow a \in A \land a \notin (B\cup C)$$ $$\leftrightarrow a \in A \land a \notin B \land a \notin C$$ $$\leftrightarrow (a \in A \de la tierra a \noen B) \la tierra (a \in A \de la tierra un \noen C)$$ $$\leftrightarrow a \in (A-B) \land a \in (A-C)$$ $$\leftrightarrow a \in (A-B) \cap (A-C)$$

El siguiente ejemplo en el libro hace la misma cosa (demostrando ambas declaraciones con una sola equivalencia) para demostrar $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Bien, muy bien. Si alguna vez tengo que probar este tipo de igualdad, voy a hacer la misma cosa (ni siquiera sé por qué). ¿Hay algún caso que debo hacer, tanto de ellos por separado?

Answer 1

Es sorprendentemente difícil de probar que $\left|\Bbb{Q}\right| = \left|\Bbb{N}\right| (=\aleph_0)$ mediante la exhibición de una explícita bijection entre los dos. Por el contrario, es mucho más fácil usar el hecho de que $\Bbb{N}\subseteq\Bbb{Q}$ (trivialmente) y, a continuación, encontrar una correspondencia $\Bbb{Q}\leftrightarrow S\subset\Bbb{N}$ para algunos de $S$ de los números naturales. Por ejemplo, la manera clásica es la forma más simple " de una fracción $\frac{p}{q}\in\Bbb{Q}$ y el mapa que el habitual número $\frac{(p+q)(p+q+1)}{2}+q$; véase la http://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function . Este enfoque no proporciona un directo bijection porque, por ejemplo, el número de $8 = \langle 1,2\rangle = \frac{(1+2)(1+2+1)}{2}+2$ y el número de $25=\langle 2,4\rangle = \frac{(2+4)(2+4+1)}{2}+4$ corresponden ambos a la fracción $\frac{1}{2}$, por lo que una forma del teorema de citar (el llamado Cantor-Bernstein Teorema) es necesaria para demostrar que los dos conjuntos son, en realidad, en bijection.

Answer 2

$\newcommand{\cl}{\operatorname{cl}}$No son simples ejemplos de la que estoy a punto de dar, pero las que puedo pensar en este momento, todos requieren de algunos matemáticos de fondo que no puede tener.

Decir que un conjunto $A\subseteq\Bbb Z^+$ es cerrado bajo la adición de si $a+b\in A$ siempre $a,b\in A$. Para $A\subseteq\Bbb N$ definir el cierre de $A$ a

$$\cl A=\bigcap\{C\subseteq\Bbb Z^+:A\subseteq C\text{ and }C\text{ is closed under addition}\}\;,$$

la intersección de todos superseries de $A$ que está cerrado bajo la suma.

Ahora vamos a $A=\{n\in\Bbb Z^+:n\text{ is even}\}$, y muestran que la $A=\cl A$.

Deje $\mathscr{C}=\{C\subseteq\Bbb Z^+:A\subseteq C\text{ and }C\text{ is closed under addition}\}$. Claramente $A\in\mathscr{C}$, lo $\cl A=\bigcap\mathscr{C}\subseteq A$. Por otro lado, $A\subseteq C$ para todos los $C\in\mathscr{C}$, lo $A\subseteq\bigcap\mathscr{C}=\cl A$. Juntando las piezas, tenemos $A=\cl A$.

Creo que usted encontrará que es difícil llegar con una prueba que usa una cadena de doble implicaciones.

O $\cl\{2\}=A$.

Deje $\mathscr{C}=\{C\subseteq\Bbb Z^+:2\in C\text{ and }C\text{ is closed under addition}\}$, por lo que el $\cl\{2\}=\bigcap\mathscr{C}$. Claramente $A\in\mathscr{C}$, lo $\cl\{2\}\subseteq A$. Para mostrar que $A\subseteq\cl\{2\}$, supongo que no. A continuación,$A\setminus\cl\{2\}\ne\varnothing$, así que vamos a $m=\min(A\setminus\cl\{2\})$. Claramente $m\ne 2$, ya que el $2\in\{2\}\subseteq\cl\{2\}$, lo $m\ge 4$, e $m-2\in A$. Por otra parte, $m$ es el miembro más pequeño de $A$ que es no en $\cl\{2\}$, lo $m-2\in\cl\{2\}$, y por lo tanto $m-2\in C$ por cada $C\in\mathscr{C}$. Pero también tenemos $2\in C$ por cada $C\in\mathscr{C}$, y cada una de las $C\in\mathscr{C}$ es cerrado bajo la suma, por lo $2+(m-2)=m\in C$ por cada $C\in\mathscr{C}$. Pero, a continuación,$m\in\bigcap\mathscr{C}=\cl\{2\}$, contradiciendo la elección de $m$. Esta contradicción muestra que $A\setminus\cl\{2\}$ realidad debe de estar vacío, es decir, que $A\subseteq\cl\{2\}$. Juntando las piezas, tenemos $A=\cl\{2\}$, como se desee.

Aquí es aún más difícil de llegar con una prueba que usa una cadena de doble implicaciones.