Par crítico (teoría del orden)

Diagrama de Hasse de orden parcial con un par crítico ⟨ b , c ⟩. Agregar la línea gris haría que b < c sin requerir ningún otro cambio. Por el contrario, ⟨ c , b ⟩ no es un par crítico, ya que d < c , pero no d < b .

En la teoría del orden , una disciplina dentro de las matemáticas, un par crítico es un par de elementos en un conjunto parcialmente ordenado que son incomparables pero que podrían hacerse comparables sin requerir ningún otro cambio en el orden parcial.

Formalmente, sea P = ( S , ≤) un conjunto parcialmente ordenado. Entonces un par crítico es un par ordenado ( x , y ) de elementos de S con las siguientes tres propiedades:

• xey son incomparables en P ,
• para cada z en S , si z < x entonces z < y , y
• para cada z en S , si y < z entonces x < z .

Si ( x , y ) es un par crítico, entonces la relación binaria obtenida de P sumando la relación única x ≤ y también es un orden parcial. Las propiedades requeridas de los pares críticos aseguran que, cuando se suma la relación x ≤ y , la suma no causa ninguna violación de la propiedad transitiva .

Se dice que un conjunto R de extensiones lineales de P invierte un par crítico ( x , y ) en P si existe una extensión lineal en R para la cual y ocurre antes que  x . Esta propiedad se puede utilizar para caracterizar a los realizadores de órdenes parciales finitos: un conjunto no vacío R de extensiones lineales es un realizador si y sólo si invierte cada par crítico.

Referencias

• Trotter, WT (1992), Combinatoria y conjuntos parcialmente ordenados: teoría de dimensiones , Serie Johns Hopkins en Ciencias Matemáticas, Baltimore: Johns Hopkins Univ. Prensa.