Si tengo $n$ conjuntos y cada diferencia es no vacía ¿es cierto que la unión tiene al menos $n$ elementos?

Question

Sea $n\geq 2$. Sean $A_1,\ldots, A_n$ conjuntos tales que si $i\neq j$ entonces $A_i\setminus A_j\neq\emptyset$. ¿Se puede asegurar que $\bigcup_{i=1}^n A_i$ tiene al menos $n$ elementos?

Answer 1

La respuesta es no. Voy a mostrarlo con $n=5$. Sean $a,b,c,d$ cuatro cosas distintas, y considérense los conjuntos
$A_1=\{a,b\}$
$A_2=\{a,c\}$
$A_3=\{b,c\}$
$A_4=\{b,d\}$
$A_5=\{a,d\}$
Puede checarse que estos conjuntos satisfacen las hipótesis (para esto hay que checar 20 posibles parejas $A_i\setminus A_j$ a patín, lo cual yo ya hice y dejo de ejercicio al lector), sin embargo se tiene que $\bigcup_{i=1}^5A_i=\{a,b,c,d\}$ el cual tiene menos de 5 elementos.

La pregunta es si $n=5$ contiene el mínimo contraejemplo. Sé que no hay contraejemplos si $n=2$ o $n=3$, a continuación mi demostración del caso $n=3$ (si $n=2$ esto es bastante fácil de probar): elíjase un $a\in A_1\setminus A_2$ y un $b\in A_2\setminus A_1$. Por razones obvias ($a\in A_1$ pero $b\notin A_1$) tenemos que $a\neq b$ [y si aquí le paramos, ya tenemos la demostración para $n=2$], ahora agárrese $c\in A_3\setminus A_1$. Sabemos que $c\neq a$, por lo que si corremos con la suerte de que $c\neq b$ entonces ya encontramos $a,b,c$ distintos pertenecientes a $A_1\cup A_2\cup A_3$. Si no corremos con tal suerte, entonces $c=b\in A_2\cap A_3$, pero si ahora agarramos $d\in A_2\setminus A_3$ entonces debe tenerse que $d\neq c$ (ya que $d\notin A_3$ pero $c\in A_3$) y también $d\neq a$ (ya que $d\in A_2$ pero $a\notin A_2$), por lo que $a,b,d$ serán tres elementos distintos que pertenecen todos ellos a $A_1\cup A_2\cup A_3$. En cualquiera de estos dos casos tenemos que dicha unión tiene al menos tres elementos.

Esto aún deja abierto el caso $n=4$. Si alguien más le quiere entrar a resolverlo, bienvenido.

Comments

Otra pregunta interesante sería ¿Cuántos elementos se puede asegurar que hay en la union? ¿Un número lineal o es sublineal?

---

Si tomas un conjunto con $2k$ elementos y tomas los subconjuntos de cardinalidad $k$, tienes una colección de $\left(\begin{array}\ 2k\\ k\end{array}\right)$ conjuntos que cumplen la propiedad y su unión tiene sólo $2k$ elementos. Como ese número crece mucho más rápido que linealmente, yo pienso que al hacer el cambio $n=\left(\begin{array}\ 2k\\ k\end{array}\right)$, y despejar $k$ obtenemos que es bastante sublineal. (Falta formalidad en mi argumento, pero espero que se entienda).

Answer 2

Demostración:

Sea $E_i=A_i\setminus \bigcup _{k=1,k\neq i}^n A_k=\bigcup _{k=1,k\neq i}^n A_i\setminus A_k$; $E_i$,  es distinto del vacio y $E_i\subset A_i$, se puede observa que $E_i\cap A_j=\emptyset$ para todo $i\neq j$ y como $E_j\subset A_j$ se tiene que $E_i\cap E_j=\emptyset$, para $i\neq j$.
Ahora como $\bigcup _{i=1}^n E_i \subset \bigcup _{i=1}^n A_i$ se tiene que $n\leq n(\bigcup _{i=1}^n E_i )\leq  n(\bigcup _{i=1}^n A_i)$

Por lo tanto la unión si tiene al menos $n$ elementos.

Comments

Para cada $i,$ tu conjunto $E_i$ es vacío pues nota que $A_i\subseteq\cup_{k=1}^nA_k$

---

No es vacío, revisaré la redacción, pero si menciono  que $A_i$ no está en la Unión, indicando que la Unión es sobre todas las k  distinto de i.

---

Aún así yo creo que podría haber problemas: por ejemplo, si $A_1=\{a,b\}$, $A_2=\{b,c\}$ y $A_3=\{a,c\}$ entonces es cierto que $A_i\setminus A_j\neq\varnothing$ siempre que $i\neq j$, mas sin embargo $E_1=A_1\setminus(A_2\cup A_3)=\varnothing$.

---

Si tienes razon, entonces esta mal hecho.

---

Usaste mal las leyes de De Morgan: $A_i\setminus\bigcup_{k\neq i}A_k=\bigcap_{k\neq i}(A_i\setminus A_k)$.