En matemáticas , el teorema de Bourbaki-Witt en la teoría del orden , llamado así por Nicolas Bourbaki y Ernst Witt , es un teorema básico de punto fijo para conjuntos parcialmente ordenados . Establece que si X es un poset completo de cadena no vacío , y tal que para todos entonces f tiene un punto fijo . Esta función f se llama inflacionaria o progresiva .
Caso especial de un poset finito
Si el poset X es finito, entonces el enunciado del teorema tiene una interpretación clara que conduce a la demostración. La secuencia de iteraciones sucesivas,
donde x 0 es cualquier elemento de X , es monótono creciente. Por la finitud de X , se estabiliza:
- para n suficientemente grande.
De ello se deduce que x ∞ es un punto fijo de f .
Prueba del teorema
Elige algunos . Defina una función K de forma recursiva en los ordinales de la siguiente manera:
Si es un ordinal límite , luego por construcciónes una cadena en X . Definir
Esto es ahora una función creciente de los números ordinales en X . No puede ser estrictamente creciente, como si tuviéramos una función inyectiva de los ordinales a un conjunto, violando el lema de Hartogs . Por lo tanto, la función debe ser eventualmente constante, por lo que para algunos es decir,
Así que dejando tenemos nuestro punto fijo deseado. QED
Aplicaciones
El teorema de Bourbaki-Witt tiene varias aplicaciones importantes. Uno de los más comunes está en la prueba de que el axioma de elección implica el lema de Zorn . Primero lo probamos para el caso en el que X es una cadena completa y no tiene un elemento máximo. Sea g una función de elección en Definir una función por
Esto está permitido ya que, por supuesto, el conjunto no está vacío. Entonces f ( x )> x , entonces f es una función inflacionaria sin punto fijo, lo que contradice el teorema.
Este caso especial del lema de Zorn se usa luego para probar el principio de máxima de Hausdorff , que cada poset tiene una cadena máxima, que se ve fácilmente como equivalente al lema de Zorn.
Bourbaki – Witt tiene otras aplicaciones. En particular en informática , se utiliza en la teoría de funciones computables . También se utiliza para definir tipos de datos recursivos, por ejemplo, listas enlazadas, en la teoría de dominios .
Referencias
- Nicolas Bourbaki (1949). "Sur le théorème de Zorn". Archiv der Mathematik . 2 (6): 434–437. doi : 10.1007 / bf02036949 . S2CID 117826806 .
- Ernst Witt (1951). "Beweisstudien zum Satz von M. Zorn". Mathematische Nachrichten . 4 : 434–438. doi : 10.1002 / mana.3210040138 .