Comparabilidad

Property of elements related by inequalities

Diagrama de Hasse de los números naturales , parcialmente ordenados por " x ≤ y si x divide a y ". Los números 4 y 6 son incomparables, ya que ninguno divide al otro.

En matemáticas , se dice que dos elementos x e y de un conjunto P son comparables con respecto a una relación binaria ≤ si al menos una de las siguientes es verdadera: x ≤ y o y ≤ x . Se denominan incomparables si no son comparables.

Definición rigurosa

Una relación binaria en un conjunto es por definición cualquier subconjunto de Dado se escribe si y solo si en cuyo caso se dice que está relacionado con por Se dice que un elemento es -comparable , o comparable ( con respecto a ), a un elemento si o A menudo, se utiliza un símbolo que indica comparación, como (o y muchos otros) en lugar de en cuyo caso se escribe en lugar de por lo cual se utiliza el término "comparable". ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle P\times P.}$ ${\displaystyle x,y\in P,}$ ${\displaystyle xRy}$ ${\displaystyle (x,y)\in R,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle R.}$ ${\displaystyle x\in P}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle y\in P}$ ${\displaystyle xRy}$ ${\displaystyle yRx.}$ ${\displaystyle \,<\,}$ ${\displaystyle \,\leq \,,}$ ${\displaystyle \,>,\,}$ ${\displaystyle \geq ,}$ ${\displaystyle R,}$ ${\displaystyle x<y}$ ${\displaystyle xRy,}$

La comparabilidad con respecto a induce una relación binaria canónica en ; específicamente, la relación de comparabilidad inducida por se define como el conjunto de todos los pares tales que es comparable con ; es decir, tal que al menos uno de y es verdadero. De manera similar, la relación de incomparabilidad en inducida por se define como el conjunto de todos los pares tales que es incomparable con , es decir, tal que ni ni son verdaderos. ${\displaystyle R}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle (x,y)\in P\times P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle (x,y)\in P\times P}$ ${\displaystyle x}$ ${\displaystyle y;}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$

Si se utiliza el símbolo en lugar de, entonces la comparabilidad con respecto a a veces se denota con el símbolo , y la incomparabilidad con el símbolo . ^[1] Por lo tanto, para cualesquiera dos elementos y de un conjunto parcialmente ordenado, exactamente uno de y es verdadero. ${\displaystyle \,<\,}$ ${\displaystyle \,\leq \,}$ ${\displaystyle \,<\,}$ ${\displaystyle {\overset {<}{\underset {>}{=}}}}$ ${\displaystyle {\cancel {\overset {<}{\underset {>}{=}}}}\!}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}$ ${\displaystyle x{\cancel {\overset {<}{\underset {>}{=}}}}y}$

Ejemplo

Un conjunto totalmente ordenado es un conjunto parcialmente ordenado en el que dos elementos cualesquiera son comparables. El teorema de extensión de Szpilrajn 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 sea comparable.

Propiedades

Ambas relaciones comparabilidad e incomparabilidad son simétricas , es decir, es comparable a si y sólo si es comparable a y lo mismo para la incomparabilidad. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x,}$

Gráficos de comparabilidad

El gráfico de comparabilidad de un conjunto parcialmente ordenado tiene como vértices los elementos de y tiene como aristas precisamente aquellos pares de elementos para los cuales . ^[2] ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \{x,y\}}$ ${\displaystyle x\ {\overset {<}{\underset {>}{=}}}\ y}$

Clasificación

Al clasificar objetos matemáticos (por ejemplo, espacios topológicos ), se dice que dos criterios son comparables cuando los objetos que obedecen a un criterio constituyen un subconjunto de los objetos que obedecen al otro, es decir, cuando son comparables bajo el orden parcial ⊂. Por ejemplo, los criterios T 1 y T 2 son comparables, mientras que los criterios T ₁ y de sobriedad no lo son.

Véase también

• Ordenamiento débil estricto  : clasificación matemática de un conjunto Pages displaying short descriptions of redirect targets, un ordenamiento parcial en el que la incomparabilidad es una relación transitiva

Referencias

1. Trotter, William T. (1992), Combinatoria y conjuntos parcialmente ordenados: teoría de la dimensión , Johns Hopkins Univ. Press, pág. 3
2. Gilmore, PC; Hoffman, AJ (1964), "Una caracterización de los gráficos de comparabilidad y de los gráficos de intervalo", Revista canadiense de matemáticas , 16 : 539–548, doi : 10.4153/CJM-1964-055-5.

Enlaces externos

• «PlanetMath: orden parcial». Archivado desde el original el 11 de julio de 2012. Consultado el 6 de abril de 2010 .