En matemáticas , el teorema de extensión de Szpilrajn (también llamado principio de extensión de orden ), probado por Edward Szpilrajn en 1930, [1] establece que todo orden parcial está contenido en un orden total . Intuitivamente, el teorema dice que cualquier método de comparación de elementos que deje algunos pares incomparables puede extenderse de tal manera que cada par se vuelva comparable. El teorema es uno de los muchos ejemplos del uso del axioma de elección en la forma del lema de Zorn para encontrar un conjunto máximo con ciertas propiedades.
Definiciones y declaración
Una relación binaria R en un conjunto X se define formalmente como un conjunto de pares ordenados ( x , y ) de elementos de X , y a menudo abreviamos ( x , y ) ∈ R como xRy .
Una relación es reflexiva si xRx se cumple para cada elemento x ∈ X ; es transitivo si xRy y yRz implican xRz para todos x, y, z ∈ X ; es antisimétrico si xRy y yRx implican x = y para todo x, y ∈ X ; y es una relación connex si xRy o yRx mantiene para todos los x, y ∈ X . Un orden parcial es, por definición, una relación reflexiva, transitiva y antisimétrica. Un pedido total es un pedido parcial que está conectado.
Una relación R está contenida en otra relación S cuando todos los pares ordenados en R también aparecen en S , es decir, xRy implica xSy para todo x, y ∈ X. El teorema de extensión establece que toda relación R que es reflexiva, transitiva y antisimétrica (es decir, una orden parcial) está contenido en otra relación S que es reflexiva, transitiva, antisimétrica y conex (es decir, un orden total).
Prueba
El teorema se demuestra en dos pasos. En primer lugar, si un orden parcial no se compara x y y , que se puede ampliar mediante la adición de primero el par ( x , Y ) y luego realizar el cierre transitivo , y segundo, ya que esta operación genera un ordenamiento que estrictamente contiene el original y puede aplicarse a todos los pares de elementos incomparables, existe una relación en la que todos los pares de elementos se han hecho comparables.
El primer paso se demuestra como un lema preliminar, en el que un orden parcial, donde un par de elementos x y y son incomparable se cambia para hacerlos comparables. Esto se hace agregando primero el par x R y a la relación, lo que puede resultar en una relación no transitiva, y luego restaurando la transitividad agregando todos los pares q R p tales que q R x y y R p . Esto se hace en un solo par de elementos incomparables x y y , y produce una relación que todavía es reflexiva, antisimétrica y transitiva y que contiene estrictamente la original.
A continuación mostramos que el conjunto de órdenes parciales que contienen R , ordenados por inclusión, tiene un elemento máximo. La existencia de tal elemento máximo se prueba aplicando el lema de Zorn a este poset. Una cadena en este conjunto es un conjunto de relaciones que contienen R, de modo que dadas dos de estas relaciones, una está contenida en la otra.
Para aplicar el lema de Zorn, debemos mostrar que cada cadena tiene un límite superior en el poset. Dejar ser tal cadena, y mostramos que la unión de sus elementos, , es un límite superior para que está en el poset: contiene la relación original R ya que cada elemento dees un orden parcial que contiene R . A continuación mostramos quees una relación transitiva. Suponga que ( x , y ) y ( y , z ) están en, para que exista tal que y . Desdees una cadena que tenemos S⊆T o T⊆S. Suponga S⊆T; el argumento para cuando T ⊆ S es similar. Entonces también tenemos. Dado que todas las relaciones producidas por nuestro proceso son transitivas, ( x , z ) está en T, y por lo tanto en. Del mismo modo, podemos demostrar que es antisimétrico.
Por lo tanto, según el lema de Zorn, el conjunto de órdenes parciales que contienen R tiene un elemento máximo Q, y solo queda mostrar que Q es total. De hecho, si Q tuviera un par de elementos incomparables, entonces podríamos aplicarle el proceso del primer paso, lo que conduciría a otro orden parcial estricto que contenga R y contenga estrictamente Q, lo que contradice que Q es máximo. Por tanto, Q es un pedido total que contiene R, completando la demostración.
Otros teoremas de extensión
- Arrow afirmó que cada preorden (relación reflexiva y transitiva) puede extenderse a un preorden total (relación transitiva y conexa), y esta afirmación fue probada más tarde por Hansson.
- Suzumura demostró que una relación binaria se puede extender a un preorden total si y solo si es consistente con Suzumura , lo que significa que no hay un ciclo de elementos tal que x R y para cada par de elementos consecutivos ( x , y ), y hay algún par de elementos consecutivos ( x , y ) en el ciclo para el cual y R x no se cumple.
Referencias
- ^ Marczewski, Edward (1930), "Sur l'extension de l'ordre partiel" (PDF) , Fundamenta Mathematicae (en francés), 16 : 386–389, doi : 10.4064 / fm-16-1-386-389.