Lema de zorn

La lema de Zorn se puede utilizar para demostrar que cada gráfico conectado tiene un árbol de azotes. El conjunto de todos los subgrafos que son árboles se ordena por inclusión, y la unión de una cadena es un límite superior. La lema de Zorn dice que debe existir un árbol maximal, que es un árbol de azotes desde que el gráfico está conectado. La lema de Zorn no es necesaria para los gráficos finitos, como el que figura aquí.

El lema fue probado (asumiendo el axioma de elección) por Kazimierz Kuratowski en 1922 e independientemente por Max Zorn en 1935. Aparece en las demostraciones de varios teoremas de importancia crucial, por ejemplo, el teorema de Hahn-Banach en análisis funcional, el teorema de que todo espacio vectorial tiene una base, el teorema de Tychonoff en topología que establece que todo producto de espacios compactos es compacto, y los teoremas en álgebra abstracta de que en un anillo con identidad todo ideal propio está contenido en un ideal maximal y que todo campo tiene una clausura algebraica.

El lema de Zorn es equivalente al teorema del buen orden y también al axioma de elección, en el sentido de que dentro de ZF (teoría de conjuntos de Zermelo-Fraenkel sin el axioma de elección) cualquiera de los tres es suficiente para probar los otros dos. Una formulación anterior del lema de Zorn es el principio máximo de Hausdorff, que establece que todo subconjunto totalmente ordenado de un conjunto parcialmente ordenado está contenido en un subconjunto máximo totalmente ordenado de ese conjunto parcialmente ordenado.

Motivación

Para probar la existencia de un objeto matemático que puede ser visto como un elemento máximo en algún conjunto parcialmente ordenado de alguna manera, se puede probar la existencia de tal objeto asumiendo que no hay un elemento máximo y usando inducción transfinita y los supuestos de la situación para obtener una contradicción. El lema de Zorn ordena las condiciones que una situación debe satisfacer para que dicho argumento funcione y permite a los matemáticos no tener que repetir el argumento de inducción transfinita a mano cada vez, sino simplemente comprobar las condiciones de Zorn' s lema.

Si usted está construyendo un objeto matemático en etapas y encontrar que (i) usted no ha terminado incluso después infinitamente muchas etapas, y (ii) parece que no hay nada que dejar de seguir construyendo, entonces la lema de Zorn puede ser bien capaz de ayudarle.

—William Timothy Gowers, "Cómo usar la lema de Zorn"

Enunciado del lema

Nociones preliminares:

• Un juego P equipado con una relación binaria ≤ que es reflexivo (x ≤ x para todos x), antisimétrico (si ambos x ≤ Sí. y Sí. ≤ x Espera, entonces x = Sí.), y transitivo (si x ≤ Sí. y Sí. ≤ z entonces x ≤ z) se dice que es (partialmente) ordenado por ≤. Dados dos elementos x y Sí. de P con x ≤ Sí., Sí. se dice que es mayor o igual a x. La palabra "partial" está destinada a indicar que no todos los pares de elementos de un conjunto parcialmente ordenado se requieren para ser comparables bajo la relación del orden, es decir, en un conjunto parcialmente ordenado P con relación orden ≤ puede haber elementos x y Sí. con ninguno x ≤ Sí. ni Sí. ≤ x. Un conjunto ordenado en el que cada par de elementos es comparable se llama totalmente ordenado.
• Cada subconjunto S de un conjunto parcialmente ordenado P puede ser visto como parcialmente ordenado restringiendo la relación de orden heredada de P a S. Un subconjunto S de un conjunto parcialmente ordenado P se llama una cadena (en P) si es totalmente ordenado en el orden heredado.
• Un elemento m de un conjunto parcialmente ordenado P con relación orden ≤ es maximal (con respecto a ≤) si no hay otro elemento P más grande que m, es decir, si no hay s dentro P con s ل m y m ≤ s. Dependiendo de la relación de pedido, un conjunto parcialmente ordenado puede tener cualquier número de elementos maximales. Sin embargo, un conjunto totalmente ordenado puede tener en la mayoría de un elemento maximal.
• Dado un subconjunto S de un conjunto parcialmente ordenado P, un elemento u de P es un límite superior de S si es mayor o igual a cada elemento S. Aquí, S no es necesario ser una cadena, y u debe ser comparable a cada elemento S pero no necesita ser un elemento S.

El lema de Zorn se puede establecer como:

A veces se utilizan variantes de esta formulación, como exigir que el conjunto P y las cadenas no estén vacíos.

Aunque esta formulación parece ser formalmente más débil (puesto que coloca sobre P la condición adicional de ser no vacío, pero obtiene la misma conclusión sobre P), en De hecho, las dos formulaciones son equivalentes. Para verificar esto, suponga primero que P satisface la condición de que cada cadena en P tiene un límite superior en P. Entonces el subconjunto vacío de P es una cadena, ya que satisface la definición de forma vacía; por lo que la hipótesis implica que este subconjunto debe tener un límite superior en P, y este límite superior muestra que P de hecho no está vacío. Por el contrario, si se supone que P no es vacío y satisface la hipótesis de que toda cadena no vacía tiene un límite superior en P, entonces P también satisface la condición de que cada cadena tiene un límite superior, ya que un elemento arbitrario de P sirve como límite superior para la cadena vacía (es decir, el subconjunto vacío visto como cadena).

La diferencia puede parecer sutil, pero en muchas demostraciones que invocan el lema de Zorn, se toman uniones de algún tipo para producir un límite superior, por lo que el caso de la cadena vacía puede pasarse por alto; es decir, la verificación de que todas las cadenas tienen límites superiores puede tener que tratar con cadenas vacías y no vacías por separado. Muchos autores prefieren verificar la no vacuidad del conjunto P en lugar de tratar con la cadena vacía en el argumento general.

Aplicaciones de ejemplo

Todo espacio vectorial tiene una base

El lema de Zorn se puede usar para mostrar que todo espacio vectorial V tiene una base.

Si V = {0}, entonces el conjunto vacío es una base para V. Ahora, supongamos que V ≠ {0}. Sea P el conjunto formado por todos los subconjuntos linealmente independientes de V. Dado que V no es el espacio vectorial cero, existe un elemento distinto de cero v de V, por lo que P contiene el subconjunto linealmente independiente {v}. Además, P está parcialmente ordenado por inclusión de conjunto (ver orden de inclusión). Encontrar un subconjunto máximo linealmente independiente de V es lo mismo que encontrar un elemento máximo en P.

Para aplicar el lema de Zorn, toma una cadena T en P (es decir, T es un subconjunto de P que está totalmente ordenado). Si T es el conjunto vacío, entonces {v} es un límite superior para T en P. Supongamos entonces que T no está vacío. Necesitamos mostrar que T tiene un límite superior, es decir, existe un subconjunto linealmente independiente B de V que contiene todos los miembros de < yo>T.

Tome B como la unión de todos los conjuntos en T. Deseamos mostrar que B es un límite superior para T en P. Para hacer esto, basta con mostrar que B es un subconjunto linealmente independiente de V.

Suponga lo contrario, que B no es linealmente independiente. Entonces existen los vectores v₁, v₂,..., v _k ∈ B y escalares a₁, a_{2,..., ak, no todo cero, tal que}

${displaystyle a_{1}mathbf {v} ¿Qué? {v} _{2}+cdots ¿Qué? {0}$

Como B es la unión de todos los conjuntos en T, existen algunos conjuntos S₁, S₂,..., S_k ∈ T tal que v_i ∈ S_i para cada i = 1, 2,..., k. Como T está totalmente ordenado, uno de los conjuntos S₁, S₂,..., S_k debe contener a los demás, por lo que hay un conjunto S_i que contiene todos de v₁, v₂,..., v _k. Esto nos dice que hay un conjunto de vectores linealmente dependiente en S_i, lo que contradice que S_i es linealmente independiente (porque es miembro de P).

La hipótesis del lema de Zorn ha sido comprobada y, por lo tanto, hay un elemento maximal en P, en otras palabras, un subconjunto maximal linealmente independiente B de V.

Finalmente, mostramos que B es de hecho una base de V. Basta mostrar que B es un conjunto generador de V. Supongamos, por el bien de la contradicción, que B no está expandiendo. Entonces existe algún v ∈ V no cubierto por el tramo de B. Esto dice que B ∪ {v} es un subconjunto linealmente independiente de V que es mayor que B, lo que contradice la maximalidad de B. Por lo tanto, B es un conjunto generador de V y, por lo tanto, una base de V.

Todo anillo no trivial con unidad contiene un ideal máximo

El lema de Zorn se puede usar para mostrar que todo anillo no trivial R con unidad contiene un ideal maximal.

Sea P el conjunto formado por todos los ideales propios en R (es decir, todos los ideales en R excepto R mismo). Dado que R no es trivial, el conjunto P contiene el ideal trivial {0}. Además, P está parcialmente ordenado por inclusión de conjuntos. Encontrar un ideal maximal en R es lo mismo que encontrar un elemento maximal en P.

Para aplicar el lema de Zorn, toma una cadena T en P. Si T está vacío, entonces el ideal trivial {0} es un límite superior para T en P. Supongamos entonces que T no está vacío. Es necesario demostrar que T tiene una cota superior, es decir, existe un ideal I ⊆ R que contiene todos los miembros de T pero aún más pequeño que R (de lo contrario, no sería un ideal adecuado, por lo que no está en P).

Tome I como la unión de todos los ideales en T. Deseamos mostrar que I es un límite superior para T en P. Primero mostraremos que I es un ideal de R. Para que I sea un ideal, debe cumplir tres condiciones:

1. I es un subconjunto no vacío R,
2. Por todos x, Sí. ▪ I, la suma x + Sí. está dentro I,
3. Por todos r ▪ R y todos x ▪ I, el producto rx está dentro I.

#1 - I es un subconjunto no vacío de R.

Debido a que T contiene al menos un elemento, y ese elemento contiene al menos 0, la unión I contiene al menos 0 y no está vacía. Cada elemento de T es un subconjunto de R, por lo que la unión I solo consta de elementos en R.

#2 - Para cada x, y ∈ I, la suma x + < i>y está en I.

Suponga que x e y son elementos de I. Entonces existen dos ideales J, K ∈ T tales que x es un elemento de J y y es un elemento de K. Como T está totalmente ordenado, sabemos que J ⊆ K o K ⊆ J. Sin pérdida de generalidad, supóngase el primer caso. Tanto x como y son miembros del ideal K, por lo tanto su suma x + y es miembro de K, lo que muestra que x + y es miembro de I.

#3 - Para cada r ∈ R y cada x ∈ I, el producto rx está en I.

Suponga que x es un elemento de I. Entonces existe un ideal J ∈ T tal que x está en J. Si r ∈ R, entonces rx es un elemento de J y por lo tanto un elemento de I. Así, I es un ideal en R.

Ahora, mostramos que I es un ideal adecuado. Un ideal es igual a R si y sólo si contiene 1. (Es claro que si es R entonces contiene 1; en cambio, si contiene 1 y r es un elemento arbitrario de R, entonces r1 = r es un elemento del ideal, y entonces el ideal es igual a R). Entonces, si I fuera igual a R, entonces contendría 1, y eso significa uno de los miembros de T contendría 1 y, por lo tanto, sería igual a R, pero R está explícitamente excluido de P.

La hipótesis del lema de Zorn ha sido comprobada y, por lo tanto, hay un elemento maximal en P, en otras palabras, un ideal maximal en R.

Boceto de prueba

A continuación se presenta un bosquejo de la prueba del lema de Zorn, asumiendo el axioma de elección. Supongamos que el lema es falso. Entonces existe un conjunto parcialmente ordenado, o poset, P tal que todo subconjunto totalmente ordenado tiene un límite superior, y que para cada elemento en P hay otro elemento mayor que él. Para cada subconjunto totalmente ordenado T podemos definir un elemento mayor b(T), porque T tiene un límite superior, y ese límite superior tiene un elemento más grande. Para definir realmente la función b, necesitamos emplear el axioma de elección.

Usando la función b, vamos a definir los elementos a₀ < a₁ < a₂ < a₃ <... < a_ω < a_ω+1 <…, en P. Esta secuencia incontablemente infinita es realmente larga: los índices no son solo los números naturales, sino todos los ordinales. De hecho, la secuencia es demasiado larga para el conjunto P; hay demasiados ordinales (una clase propiamente dicha), más que elementos hay en cualquier conjunto, y el conjunto P se agotará en poco tiempo y entonces nos encontraremos con la deseada contradicción.

Los a_i están definidos por recursividad transfinita: elegimos a₀ en P arbitrario (esto es posible, ya que P contiene un límite superior para el conjunto vacío y, por lo tanto, no está vacío) y para cualquier otro ordinal w establecemos a_w = b({a_v : v < w}). Debido a que los a_v están totalmente ordenados, esta es una definición bien fundamentada.

Esta prueba muestra que en realidad una versión un poco más fuerte del lema de Zorn es cierta:

Historia

El principio maximal de Hausdorff es una declaración temprana similar al lema de Zorn.

Kazimierz Kuratowski probó en 1922 una versión del lema cercana a su formulación moderna (se aplica a conjuntos ordenados por inclusión y cerrados bajo uniones de cadenas bien ordenadas). Esencialmente, la misma formulación (debilitada por el uso de cadenas arbitrarias, no solo bien ordenadas) fue dada de forma independiente por Max Zorn en 1935, quien la propuso como un nuevo axioma de la teoría de conjuntos que reemplaza al teorema del buen orden, exhibió algunas de sus aplicaciones en álgebra., y prometió mostrar su equivalencia con el axioma de elección en otro artículo, que nunca apareció.

El nombre "Lema de Zorn" parece deberse a John Tukey, quien lo usó en su libro Convergence and Uniformity in Topology en 1940. La Théorie des Ensembles de Bourbaki de 1939 se refiere a un principio maximal como "le théorème de Zorn". El nombre "Kuratowski–Zorn lema" prevalece en Polonia y Rusia.

Formas equivalentes del lema de Zorn

El lema de Zorn es equivalente (en ZF) a tres resultados principales:

1. Principio máximo de Hausdorff
2. Axioma de elección
3. Teorema bien ordenado.

Un conocido chiste que aludía a esta equivalencia (que puede desafiar la intuición humana) se atribuye a Jerry Bona: 'El axioma de elección es obviamente verdadero, el principio del buen orden es obviamente falso, y ¿quién puede decir sobre el lema de Zorn?'

El lema de Zorn también es equivalente al teorema de completitud fuerte de la lógica de primer orden.

Además, el lema de Zorn (o una de sus formas equivalentes) implica algunos resultados importantes en otras áreas matemáticas. Por ejemplo,

1. Teorema de extensión de Banach que se utiliza para probar uno de los resultados más fundamentales en el análisis funcional, el teorema de Hahn-Banach
2. Cada espacio vectorial tiene una base, un resultado de álgebra lineal (a la cual es equivalente). En particular, los números reales, como espacio vectorial sobre los números racionales, poseen una base Hamel.
3. Cada anillo unitario comutativo tiene un ideal maximal, resultado de la teoría del anillo conocida como teorema de Krull, al cual la lema de Zorn es equivalente
4. Teorema de Tychonoff en topología (a la que también es equivalente)
5. Cada filtro adecuado está contenido en un ultrafiltro, un resultado que produce el teorema de integridad de la lógica de primer orden

En este sentido, vemos cómo el lema de Zorn puede verse como una herramienta poderosa, aplicable a muchas áreas de las matemáticas.

Análogos bajo debilitamientos del axioma de elección

Se puede demostrar una forma debilitada del lema de Zorn a partir de ZF + DC (teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección reemplazado por el axioma de elección dependiente). El lema de Zorn se puede expresar directamente al observar que el conjunto que no tiene un elemento máximo sería equivalente a afirmar que la relación de orden del conjunto sería completa, lo que nos permitiría aplicar el axioma de elección dependiente para construir una cadena contable. Como resultado, cualquier conjunto parcialmente ordenado con cadenas exclusivamente finitas debe tener un elemento maximal.

De manera más general, fortalecer el axioma de elección dependiente a ordinales superiores nos permite generalizar la afirmación del párrafo anterior a cardinalidades superiores. En el límite donde permitimos ordinales arbitrariamente grandes, recuperamos la prueba del lema de Zorn completo usando el axioma de elección de la sección anterior.

En la cultura popular

La película de 1970 Zorns Lemma lleva el nombre del lema.

Se hizo referencia al lema en Los Simpson en el episodio "El nuevo amigo de Bart".