Demostraciones sobre Conjuntos

Nociones basicas de conjuntos

Un conjunto es una coleccion de objetos, llamados elementos. Se puede describir de dos formas:

Por extension: listando sus elementos, como $\{1, 2, 3\}$
Por comprension: usando una propiedad, como $\{x : P(x)\}$ , que se lee "el conjunto de todos los $x$ tales que $P(x)$ "

Definición 1 — Pertenencia

Un elemento $x$ pertenece a un conjunto $A$ , escrito $x \in A$ , si $x$ es uno de los elementos de $A$ .

Definición 2 — Conjunto vacio

El conjunto vacio $\emptyset$ es el conjunto que no tiene elementos. Para todo $x$ :

$x \in \emptyset \equiv \bot$

Definición 3 — Subconjunto

$A$ es subconjunto de $B$ , escrito $A \subseteq B$ , si todo elemento de $A$ es elemento de $B$ :

$A \subseteq B \equiv \forall x : x \in A \Rightarrow x \in B$

Definición 4 — Igualdad de conjuntos

Dos conjuntos son iguales si tienen exactamente los mismos elementos:

$A = B \equiv A \subseteq B \land B \subseteq A$

Equivalentemente:

$A = B \equiv \forall x : x \in A \Leftrightarrow x \in B$

Operaciones basicas

Definición 5 — Union

$x \in A \cup B \equiv x \in A \lor x \in B$

Definición 6 — Interseccion

$x \in A \cap B \equiv x \in A \land x \in B$

Definición 7 — Complemento

$x \in \overline{A} \equiv \neg(x \in A)$

Definición 8 — Diferencia

$x \in A \setminus B \equiv x \in A \land \neg(x \in B)$

Como demostrar que un conjunto es subconjunto de otro

Para demostrar $A \subseteq B$ , debemos probar que $\forall x : x \in A \Rightarrow x \in B$ . Esto se reduce a tomar un $x$ arbitrario, suponer $x \in A$ , y demostrar $x \in B$ . Es decir, es una prueba directa de una implicacion universalmente cuantificada.

Teorema 1 — La interseccion es subconjunto

$A \cap B \subseteq A$

▶Demostración

Sea $x$ arbitrario. Supongamos $x \in A \cap B$ .

Por definicion de interseccion:

$x \in A \cap B \equiv x \in A \land x \in B$

Como $x \in A \land x \in B$ vale, en particular $x \in A$ .

Como $x$ fue arbitrario, concluimos $A \cap B \subseteq A$ .

QED

Ejemplo 2 — Monotonia de la interseccion

Enunciado: Si $A \subseteq B$ , entonces $A \cap C \subseteq B \cap C$ .

Demostracion: Sea $x$ arbitrario. Supongamos $x \in A \cap C$ . Por definicion, $x \in A$ y $x \in C$ . Como $A \subseteq B$ y $x \in A$ , tenemos $x \in B$ . Luego $x \in B$ y $x \in C$ , es decir, $x \in B \cap C$ .

QED

Como demostrar que dos conjuntos son iguales

Para demostrar $A = B$ hay dos metodos equivalentes:

Doble inclusion: demostrar $A \subseteq B$ y $B \subseteq A$ por separado.
Bicondicional: tomar $x$ arbitrario y demostrar $x \in A \Leftrightarrow x \in B$ .

En la practica, ambos metodos funcionan expandiendo las definiciones de las operaciones de conjuntos hasta reducir el enunciado a una equivalencia logica.

Teorema 3 — Ley de De Morgan para conjuntos

$\overline{A \cup B} = \overline{A} \cap \overline{B}$

▶Demostración

Sea $x$ arbitrario. Mostramos $x \in \overline{A \cup B} \Leftrightarrow x \in \overline{A} \cap \overline{B}$ :

$x \in \overline{A \cup B}$

$\equiv \neg(x \in A \cup B)$

$\equiv \neg(x \in A \lor x \in B)$

$\equiv \neg(x \in A) \land \neg(x \in B)$

$\equiv x \in \overline{A} \land x \in \overline{B}$

$\equiv x \in \overline{A} \cap \overline{B}$

El paso clave usa la ley de De Morgan de la logica proposicional: $\neg(p \lor q) \equiv \neg p \land \neg q$ .

QED

Ejemplo 4 — Distributividad de la union sobre la interseccion

Enunciado: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Demostracion: Sea $x$ arbitrario. Tenemos:

$x \in A \cup (B \cap C)$

$\equiv x \in A \lor (x \in B \land x \in C)$

$\equiv (x \in A \lor x \in B) \land (x \in A \lor x \in C)$

$\equiv x \in (A \cup B) \cap (A \cup C)$

El paso central usa la distributividad de $\lor$ sobre $\land$ : $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ .

QED

Conexion entre conjuntos y logica

Las demostraciones anteriores revelan un patron: cada operacion de conjuntos se corresponde con un conectivo logico.

Operacion de conjuntos	Conectivo logico
$A \cup B$	$p \lor q$
$A \cap B$	$p \land q$
$\overline{A}$	$\neg p$
$A \subseteq B$	$p \Rightarrow q$
$A = B$	$p \Leftrightarrow q$
$\emptyset$	$\bot$

Esta correspondencia explica por que toda identidad de conjuntos tiene una identidad logica asociada, y viceversa. Por ejemplo:

La ley de De Morgan para conjuntos ( $\overline{A \cup B} = \overline{A} \cap \overline{B}$ ) se corresponde con la ley de De Morgan logica ( $\neg(p \lor q) \equiv \neg p \land \neg q$ ).
La distributividad de $\cup$ sobre $\cap$ se corresponde con la distributividad de $\lor$ sobre $\land$ .
La propiedad $A \cap B \subseteq A$ se corresponde con la simplificacion $p \land q \Rightarrow p$ .

En la practica, demostrar una igualdad de conjuntos consiste en traducir las operaciones de conjuntos a logica, aplicar las equivalencias logicas conocidas, y luego traducir de vuelta a conjuntos. El metodo es siempre el mismo:

Tomar un elemento $x$ arbitrario
Expandir las definiciones de las operaciones de conjuntos
Manipular la expresion logica resultante
Concluir la pertenencia al otro conjunto

Esta relacion profunda entre conjuntos y logica es una de las razones por las que la teoria de conjuntos sirve como fundamento de la matematica: los conjuntos dan una semantica concreta a las operaciones logicas abstractas.