Teorema de Bourbaki-Witt

Teorema del punto fijo

En matemáticas , el teorema de Bourbaki-Witt en teoría del orden , llamado así por Nicolas Bourbaki y Ernst Witt , es un teorema básico de punto fijo para conjuntos parcialmente ordenados . Afirma que si X es un conjunto parcial completo en cadena no vacía , y tal que para todo entonces f tiene un punto fijo . Una función de este tipo f se llama inflacionaria o progresiva . ${\displaystyle f:X\to X}$ ${\displaystyle f(x)\geq x}$ ${\displaystyle x,}$

Caso especial de un poset finito

Si el conjunto posext X es finito, entonces el enunciado del teorema tiene una interpretación clara que conduce a la demostración. La secuencia de iteraciones sucesivas,

${\displaystyle x_{n+1}=f(x_{n}),n=0,1,2,\ldots ,}$

donde x ₀ es cualquier elemento de X , es monótona creciente. Por la finitud de X , se estabiliza:

${\displaystyle x_{n}=x_{\infty },}$para n suficientemente grande.

De ello se deduce que x _∞ es un punto fijo de f .

Prueba del teorema

Elija algunos . Defina una función K recursivamente sobre los ordinales de la siguiente manera: ${\displaystyle y\in X}$

${\displaystyle \,K(0)=y}$

${\displaystyle \,K(\alpha +1)=f(K(\alpha )).}$

Si es un ordinal límite , entonces por construcción es una cadena en X . Definir ${\displaystyle \beta }$ ${\displaystyle \{K(\alpha )\ :\ \alpha <\beta \}}$ ${\displaystyle K(\beta )=\sup\{K(\alpha )\ :\ \alpha <\beta \}.}$

Ahora se trata de una función creciente de los ordinales en X. No puede ser estrictamente creciente, ya que si lo fuera, tendríamos una función inyectiva de los ordinales en un conjunto, violando el lema de Hartog . Por lo tanto, la función debe ser eventualmente constante, por lo que para algún valor, ${\displaystyle \alpha ,\ \ K(\alpha +1)=K(\alpha );}$ ${\displaystyle \,f(K(\alpha ))=K(\alpha ).}$

Así que, tengamos nuestro punto fijo deseado. QED ${\displaystyle \,x=K(\alpha ),}$

Aplicaciones

El teorema de Bourbaki-Witt tiene varias aplicaciones importantes. Una de las más comunes es la prueba de que el axioma de elección implica el lema de Zorn . Primero lo demostramos para el caso en que X es cadena completa y no tiene ningún elemento maximalista. Sea g una función de elección en Definir una función por ${\displaystyle P(X)-\{\varnothing \}.}$ ${\displaystyle f:X\to X}$ ${\displaystyle f(x)=g(\{y\ :\ y>x\}).}$

Esto se permite ya que, por suposición, el conjunto no está vacío. Entonces f ( x ) > x , por lo que f es una función inflacionaria sin punto fijo, lo que contradice el teorema.

Este caso especial del lema de Zorn se utiliza luego para demostrar el principio de maximalidad de Hausdorff , que establece que cada conjunto parcial tiene una cadena máxima, lo 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

• Nicolás Bourbaki (1949). "Sobre el teoría 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.