Los Polacos saben partir conjuntos

abril 11, 2008

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.

8 comentarios to “Los Polacos saben partir conjuntos”

  1. mroberto said

    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 said

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

  3. mroberto said

    se podria decir que me debes dos cafes?

  4. Marlowe:PI said

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

  5. godelian said

    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 said

    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 said

    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😛

  8. Marlowe:PI said

    JAJAJAJAJAJAJAJAJAJA, esa es LA demostración…

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: