Teorema de Mazurkiewicz sobre 2-Punto Conjuntos

¿Existe un subconjunto del plano tal que cada línea recta encuentra el subconjunto en exactamente dos puntos?

( Observación. Un conjunto que cruza todas las líneas del plano en exactamente n puntos se llama n-punto conjunto o algunas veces un conjunto de Mazurkiewicz. Un 1-punto conjunto es claramente imposible, y esta cuestión se pregunta si 2-punto conjuntos existen.)

¿Quiere una sugerencia? Haga clic aquí.

Haga clic aquí para ver la respuesta completa.

Sugerencia 1

La respuesta es Sí, aunque es difícil de visualizar tal conjunto. Este resultado fue demostrado por Stefan Mazurkiewicz en 1914, y vamos a mostrar su demostración. En este artículo vamos a mostrar cómo construir el conjunto por uso de la recursión transfinita. Sorprendentemente, la construcción utiliza casi ningún hecho sobre la geometría o el plano, pero sí utiliza algunos hechos sobre los números transfinitos, por lo que debe estar familiarizado con este tema. (La mayoría de los libros sobre la teoría de conjuntos discuten este tema.)

Vamos a practicar en una versión más simple del problema antes de dar un salto en el transfinito. Supongamos que tenemos un conjunto finito de líneas rectas en el plano L_1, ..., L_N. Describa un método para generar un conjunto de puntos en el plano de tal manera que (1) cada línea de esta colección cruza exactamente dos miembros del conjunto, y (2) cualquiera línea el en plano cruza un máximo de dos miembros del conjunto. Una manera fácil de hacer esto sería dibujar un círculo muy grande, suficientemente grande para que cada línea se corta, pero este método no generaliza bien. Pensar en algún otro método para seleccionar los puntos, uno a la vez.

Sugerencia 2

El conjunto de puntos puede ser definido de una manera sencilla por inducción. Vamos a definir una secuencia de puntos y_1, y_2, .... También definimos una secuencia de conjuntos A_2, A_3, ... por A_k = \{y_1, y_2, ..., y_{k-1} \}. Escribimos A para el conjunto de todo y_k.

• Definir y_1 como cualquier punto de L_1.
• Una vez definido y_1, ..., y_{k-1}, definimos y_k por la regla siguiente. Si todos los L_i cruzan A_k en por lo menos dos puntos, estamos acabados. De lo contrario, elegir el más pequeño i tal que L_i cruza A_k en menos que dos puntos. Elegir y_k como cualquier punto de L_i que no es ya en A_k y que no es co-lineal con cualquier dos puntos de A_k.

Por construcción, no hay tres puntos de cualquier A_k que son co-lineales, por lo que ninguna línea en el plano cruza A en mas que dos puntos. Es claro que la construcción termina después de un máximo de 2N pasos, porque cada paso añade un punto y hay no mas que 2 puntos en cada línea.

Tenga en cuenta que en esta construcción, poco a poco mueve a través de las líneas. En general, se añaden dos puntos en cada línea, a continuación, paso a la siguiente línea de número, y en el caso general nos encontramos con un conjunto que contiene 2N puntos. Es posible que el conjunto final puede ser menor, puede ocurir que un punto escogido para una línea también es en una línea más adelante, así que cuando lleguemos a la segunda línea no tenemos que agregar dos puntos.

Ahora tenemos que saltar a los números transfinitos. Nuestras construcciones funciona bien para un conjunto de líneas finito, ¿cómo podemos extenderla al conjunto de todas las líneas del plano?

El Resto de la Respuesta

Puede utilizar la misma construcción en una recursión transfinito que paso a través de todas las líneas del plano. Pero tenemos que definir el paso recursivo con un poco más de cuidado para garantizar que utilice todas las líneas.

Escribir c para la cardinalidad del continuo, es decir, el cardinal transfinito para la línea real. Esta es también la cardinalidad de los puntos del plano, y la cardinalidad de las líneas rectas en el plano (cada línea recta está determinada por dos puntos). También escribimos O_c para el primer ordinal transfinito que tiene cardinalidad c (hay un primero porque los ordinales son bien ordenados). La colección de todas las líneas rectas en el plano tiene cardinalidad c y por lo tanto se puede poner en una correspondencia biunívoca (uno-a-uno) con O_c. Esto establece un buen orden de esta colección, por lo que puede hacer referencia a las líneas individuales de indexación de los mismos:

Tenga en cuenta que esta opción de indexación tiene la propiedad especial que cualquier segmento inicial de \{L_i | i < d\} en que d < c tiene menor cardinalidad de c, a pesar de que el conjunto de líneas tiene cardinalidad c, porque O_c es el ordinal menor con cardinalidad c. De la misma manera que podemos indexar todos los puntos del plano: {x_i} en que i < c.

Nuestra construcción de y_k y A_k es casi lo mismo como antes. El paso de recursión transfinito es que, haber definido todo y_i para i < k en que k < c es número ordinal, definimos y_k como antes. Para hacer la recursión bien definida, siempre escogimos el primer punto apropiado en la línea (con el orden en x_i).

En el caso infinito necesitamos un argumento para demostrar que siempre existe una línea de L_i que funciona, y necesitamos un nuevo argumento para demostrar que todas las líneas se cruzan A en al menos dos puntos (como antes, por la construcción se cruzan A_k como máximo en dos puntos).

Es fácil ver que no se quedará sin líneas. Para cualquier k, A_k tiene cardinalidad menos de c (k es un segmento inicial de O_c), y cada línea contiene un máximo de dos y_i , por lo que el número de líneas que se cruzan A_k también tiene cardinalidad menos que c.

Mostrando que cada línea se cruza al menos dos puntos de A es más sutil, pero es la misma idea que el caso finito: Nos estamos trabajando a través de las líneas en orden, añadiendo dos puntos por línea, por lo que si alguna línea tiene menos de dos puntos, esto significa que el proceso se ha estancado de alguna manera, y nos muestran que esto es imposible. Para hacer esta argumento específico, supongamos que hay un entrecruzamiento de líneas A en menos de dos puntos. Luego hay una línea, en primer lugar, llamela L_r. Observamos que A tiene cardinalidad c, porque tiene un elemento y_i para cada i < c. El conjunto de líneas de

tiene cardinalidad menos que c, y cada uno contiene al más dos elementos de A, por lo que hay elementos de A que no son en ninguna línea de este conjunto. Usando la ordenación de y_i (no a ordenación de x_i) sea y_m ser el punto primero de ellos. Sabemos que y_m no es en A_m , porque se añade a A_m para formar A_{m+1} . Sea L_s la línea que utilizamos en la selección y_m , tal que y_m es en L_s. Ahora vamos a derivar una contradicción al considerar donde el ordinal s esta relativa a r. Sabemos que s > r es imposible, porque L_r cruza A en menos de dos puntos y así, en particular, se cruza A_m en menos de dos puntos, lo que significa que no podría haber elegido la mas posterior L_s de que escogimos y_m. También sabemos que s \le r es imposible, porque L_s sería una línea de la colección G, pero hemos elegido y_m de modo que no es de ninguna línea de esa colección. Por lo tanto tenemos una contradicción, y no hay una línea, tal como L_r.

Buena Ordenación, el Axioma de Elección, y el Lema de Zorn

La demostración de Mazurkiewicz es un raro ejemplo de la inducción transfinito utilizado para demostrar algún resultado fuera de la teoría de conjuntos (su teorema es considerado como la topología). En relación con los axiomas de Zermelo-Fraenkel de la teoría de conjuntos, hay tres resultados que son equivalentes (en el sentido de que cualquier puede demostrar fácilmente de cualquier otra):

• Principio de buena ordenación: Cualquier conjunto puede ser bien ordenado (es decir, podemos darlo un orden total tal que cualquier subconjunto tiene un mínimo).
• Axioma de Elección: Cualquier colección de conjuntos tiene una función de elección, es decir, una función que se asigna a cada conjunto un elemento de ese conjunto. Informalmente esta dice que siempre se puede escribir "escoger un elemento de cada conjunto", incluso para las colecciones infinitas.
• Lema de Zorn: Si cada totalmente ordenado subconjunto de un conjunto ordenado tiene un límite superior en el conjunto, entonces hay un elemento maximal en el conjunto.

En matemáticas en general (fuera de la teoría de conjuntos) el Lema de Zorn es el más utilizado de estos tres resultados. Un ejemplo de su uso es el teorema de Tychonoff de que el producto cartesiano de cualquier colección de espacios topológicos compactos (incluso una colección infinita) es compacto.

Referencias

• (en inglés) La pregunta original de Sam está aquí.
• La demostración original de Mazurkiewicz fue publicado en el idioma polaco en 1914. Seguimos la traducción al francés que fue publicado en sus obras completas en 1969. "Sur un ensemble plan qui a avec chaque droite deux et seulement deux points communs", en: Travaux de Topologie et ses Applications por Stefan Mazurkiewicz, editado por Karol Borsuk et al., PWN, 1969.