martes, 14 de junio de 2011

Un lema sobre conjuntos diferentes

Ahora mismo estoy ejerciendo de referee (revisor o como queráis llamarlo) para un artículo y, lógicamente, estoy teniendo que leer bastantes papers para la ocasión.

Uno de ellos es un precioso artículo de Aron, Gurary y Seoane-Sepúlveda titulado Lineability and spaceability of sets of functions on y que se puede encontrar en Proc. Amer. Math Soc. 133 (2005), nº 3, 795-803. Ya lo conocía, y, probablemente, hablaré más de él en el futuro. Pero ahora me he fijado en un curioso lema técnico de teoría de conjuntos que, a primera vista, meresultó un tanto curioso, así que os lo dejo, con la demostración que obtuve y que también me resultó curiosa.

Lema: Si tenemos conjuntos todos ellos diferentes, arbitrarios y no vacíos, entonces seguro que existe uno de ellos tal que .


Para que todos nos entendamos, si y son dos conjuntos, entonces la diferencia entre ellos es. Por lo tanto, se cumple que si entonces tiene que cumplirse que . Además, se puede decir que si y sólo si .

En resumen, el lema nos dice que en las condiciones que plantea, seguro que uno de los conjuntos en concreto no puede estar totalmente contenido en ninguno de los otros. Aquí os dejo mi demostración.



Demostración: Vamos a hacerlo por reducción al absurdo. Supongamos que la tesis no es cierta, es decir, que dado cualquiera de los conjuntos , siempre podemos encontrar otro diferente (con ) tal que , o lo que es lo mismo, . Vamos allá.
Tomemos el primer conjunto , entonces debe existir otro diferente en el que esté contenido. Para no liar las cosas, vamos a renombrar a ese conjunto y lo vamos a llamar . Es decir, tenemos que .
Ahora tomamos . Debe existir otro conjunto diferente en el que esté contenido. Si este conjunto fuese , entonces tendríamos que , pero como también tenemos que , resulta que , lo que es imposible, ya que los conjuntos eran todos diferentes. Así que el conjunto en el que está contenido no puede ser . Pues nada, volvamos a renombrar a este último y será el que contenga a . Con lo que tenemos .
Ahora partimos de y tiene que haber un conjunto que lo contenga. Igual que antes, este conjunto no puede ser ni (entonces sería ) ni (entonces ). Así que llamamos al que contiene a y tendremos que  .
Así sucesivamente, renombrando todos los conjuntos, llegaremos en pasos a que . Pero ahora, si tomamos como conjunto, resulta que no puede estar contenido en ningún otro, lo que nos lleva a contradicción.
Así que la tesis del lema debe ser cierta.

En fin, sólo quería compartir con vosotros esta pequeña demostración que, en cierto modo, me ha recordado al principio del palomar, no sé muy bien por qué.

Tito Eliatron Dixit

7 comentarios:

  1. Yo daría otra demostración:
    La inclusión entre conjuntos establece una relación de orden parcial y cualquier elemento maximal (que ha de existir puesto que la colección es finita) para dicha relación cumple el enunciado q.e.d.

    ResponderEliminar
  2. También... pero esta se me ocurrió a mi solito y me hacía ilusión compartirla. Sí, es una bobada, pero qué le vamos a hacer.

    ResponderEliminar
  3. Bobada no hombre, el problema es bonito y me has dejado intrigado con lo de la posible relación con el principio del palomar y te agradezco mucho que lo compartas.

    ResponderEliminar
  4. Lo del palomar ha sido puramente intuitivo y poco más.
    Me surgió de ver que en cada etapa de mi demostración, cada vez había menos conjuntos en donde elegir, hasta que, al fnail, en la última etapa, me quedaba sin conjuntos donde elegir.

    Como la última paloma... que al final debe irse a un nido ya ocupado previamente.

    ResponderEliminar
  5. Y por inducción sobre el número de conjuntos.

    Para n=1 ciervo.

    Valido hasta n.

    Para n+1. Aplicamos la hipótesis de inducción a los n primeros y nos sale un conjunto A no contenido en ninguno de los n primeros salvo el mismo. Si A no está contenido en el conjunto restante, A sería el conjunto que buscamos. Y si está contenido, pues el conjunto restante es el que buscábamos.

    ResponderEliminar
  6. Ah, y creo que sé de donde sale tu idea del palomar, de que al pensarlo, inicialmente el razonamiento era distinto:

    Tras llegar al conjunto C_m repites el razonamiento obteniendo un conjunto C_{m+1} con lo que has etiquetado m+1 conjuntos pero partes de m conjuntos así que por el principio del palomar, 2 etiquetas van al mismo conjunto, lo que es imposible por construcción!

    ResponderEliminar
  7. A mi tb me ha recordado el Principio del Palomar, nada más comenzar a leer el enunciado; pero en mi caso es debido a que me ha recordado al teorema de Ramsey

    ResponderEliminar

Si no comentas, Gauss se comerá una integral.
Y, por favor, respeta a todos con tus opiniones.