Los Polacos saben partir conjuntos

Lema de Sierpinski: Demostrar que existe una familia no numerable de conjuntos infinitos, \{N_\alpha\}, con N_\alpha \subset \mathbb N, y tal que la intersección de dos cualesquiera es finita.

Esta entrada fue publicada el a las Viernes 11 de Abril de 2008 y está archivada bajo las categorías Uncategorized. Puedes seguir las respuestas de esta entrada a través de sindicación RSS 2.0. Puedes dejar una respuesta, o trackback desde tu propio sitio.

8 comentarios para “Los Polacos saben partir conjuntos”

  1. mroberto Dice:
    Abril 14, 2008 a las 3:07 am | Responder

    Para cada x \in \mathbb{R} elijo una sucesión de números racionales distintos, que tienda a x
    Dados dos números reales distintos, estas sucesiones son distintas ya que tienen distinto limite, además la cantidad de números reales en los que pueden coincidir sus imágenes es finita (quedan finitos términos que distan a mas de un \epsilon de sus respectivos limites, y tomo el \epsilon menor que la mitad entre la distancia entre ellos)

    Esto es:
    1) se tiene un continuo de sucesiones distintas
    2) sus términos toman valores distintos
    3) la intersección de las imágenes de dos sucesiones distintas es un conjunto finito

    Tomando ahora una biyección entre \mathbb{Q} y \mathbb{N}, y a cada imagen de una sucesión asignándole el subconjunto de \mathbb{N} que le corresponde mediante esta biyección, es claro que vale el lema.

  2. Marlowe:PI Dice:
    Abril 14, 2008 a las 11:32 am | Responder

    ¡Perfecto! ¿Cómo llegaste hasta la página mroberto?

  3. mroberto Dice:
    Abril 14, 2008 a las 11:53 am | Responder

    se podria decir que me debes dos cafes?

  4. Marlowe:PI Dice:
    Abril 14, 2008 a las 1:11 pm | Responder

    no, porque nunca prometí un café por la solución de esto.

  5. godelian Dice:
    Abril 21, 2008 a las 12:49 pm | Responder

    Hay varias soluciones clásicas bastante interesantes del problema, que conviene mirar un poquito. Algunas son más explícitas que otras y algunas usan más axiomas que otras. Casi se podría decir que hay una solución para cada rama:

    SOLUCIÓN DE LOS ANALISTAS: Sea f:N->{0,1}, y S_f:N->N definida como S_f(0) = f(0), S_f(n) = 2 S_f(n-1) + f(n). Entonces, si T_f = Imagen(S_f), resulta que dos T_f distintos tienen intersección finita y además los T_f tienen la cardinalidad del continuo (porque las f la tienen).

    SOLUCIÓN DE LOS ALGEBRISTAS: Para cada secuencia estrictamente creciente s=(p_1, p_2, …) de números primos, se define: X_s={p_1, p_1p_2, p_1p_2p_3, …}. Entonces los X_s tienen intersección finita y el conjunto de los X_s tiene el cardinal del continuo (porque las secuencias crecientes lo tienen).

    Y por supuesto, mi favorita:

    SOLUCIÓN DE LOS LÓGICOCONJUNTISTAS (ADVERTENCIA: Se dan por verdaderos el axioma de elección y la hipótesis del continuo):

    (1) Sea S el conjunto de clases infinitas A de subconjuntos de N tales que:

    x es infinito para todo x en A

    x,y en A y x =/= y => x /\ y es finito.

    (2) S es no vacío (se puede construir explícitamente algún elemento de S, que no es difícil).

    (3) Si S está ordenado por inclusión, entonces por el lema de Zorn contiene algún elemento maximal.

    (4) Todo elemento maximal de S es no numerable. En efecto, sea A un elemento maximal y supongamos que fuera numerable. Sea a_1, a_2, a_3, … una enumeración de A.

    (6) Veamos que la cadena:

    a_1, a1 U a_2, a_1 U a_2 U a_3, …

    es estrictamente creciente: si no lo fuera, entonces para algún n, a_(n+1) es un subconjunto de a_1 U … a_n. Pero entonces:

    a_(n+1) = (a_(n+1) /\ a_1) U … (a_(n+1) /\ a_n)

    absurdo, porque el miembro izquierdo es infinito y el derecho es finito por hipótesis.

    (7) Seleccionemos una secuencia w_1, w_2, w_3, … de elementos de N, tales que:

    w_1 está en a_1
    w_2 está en a_2 – a_1
    w_3 está en a_3 – (a_1 U a_2)
    …

    (8) Sea W = {w_1, w_2, w_3, …}. Por construcción, W es distinto de a_n para todo n, así que W no está en A.

    (9) Pero W tiene intersección finita con cada elemento de A, así que:

    A U {W} está en S

    lo que contradice la maximalidad de A. Luego, A es no numerable.

    (10) Por la hipótesis del continuo, si A es no numerable, tiene cardinal c como mínimo. Pero por contener subconjuntos de N, tiene cardinal a los sumo c, así que su cardinal es exactamente c.

  6. Marlowe:PI Dice:
    Abril 21, 2008 a las 9:34 pm | Responder

    1. Nadie pidió que el cardinal fuera c. Simplemente que fuera no numerable, así que el paso 10 (y la suposición de que vale HC) es totalmente gratuito.

    2. Dos palabras: fakiu chris :p.

  7. godelian Dice:
    Abril 21, 2008 a las 10:19 pm | Responder

    1. Es verdad. Pero si los analistas y los algebristas pudieron probar que el cardinal era c, mirá si los lógicoconjuntistas se van a quedar atrás!

    2. Me faltó la solución más innovadora, aunque sólo la puedo reproducir parcialmente por cuestiones de copyright:

    SOLUCIÓN DE DAVID LYNCH: Sea d el dígito nº 47 del desarrollo decimal de la parte imaginaria del primer cero no trivial de la función zeta de Riemann. Entonces [xxxxxxCENSURADOxxxxxx], lo que prueba que ZFC es inconsistente de modo que el lema es trivialmente cierto :P

  8. Marlowe:PI Dice:
    Abril 21, 2008 a las 10:25 pm | Responder

    JAJAJAJAJAJAJAJAJAJA, esa es LA demostración…

Escribe un comentario