• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






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

+3 votos
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?
preguntado por EliasMochan (7,870 puntos) Sep 10, 2015 en Preguntas
editado por EliasMochan Sep 10, 2015

2 Respuestas

+2 votos
 
Mejor respuesta
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.
respondido por David Fernández (15,540 puntos) Sep 14, 2015
seleccionada por EliasMochan Sep 18, 2015
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).
0 votos
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.
respondido por Ramiro Milu GaBa (2,640 puntos) Sep 11, 2015
editado por Ramiro Milu GaBa Sep 11, 2015
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)$.
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...