Conjuntos y relaciones · Definición

Relación de orden parcial

matemáticas discretasrelaciones

Formaliza la idea de «ir antes que» cuando no todos los elementos tienen que poder compararse.

Definición

Una relación \(\preceq\) en un conjunto \(S\) que es reflexiva, antisimétrica y transitiva, y que por tanto ordena algunos pares de elementos de \(S\).

\[a\preceq a;\quad (a\preceq b\ \wedge\ b\preceq a)\Rightarrow a=b;\quad (a\preceq b\ \wedge\ b\preceq c)\Rightarrow a\preceq c\]

Los ejemplos típicos son \(\le\) en los números, \(\subseteq\) entre conjuntos y la divisibilidad \(\mid\) entre enteros positivos. Con \(\mid\) se tiene \(2\mid4\) y \(4\mid12\), por lo que \(2\mid12\); pero ni \(2\mid3\) ni \(3\mid2\): dos elementos pueden ser incomparables. De ahí el adjetivo «parcial».

Cuando además todo par de elementos es comparable, el orden se llama total y los elementos quedan en una sola fila, como los números reales con \(\le\). La desigualdad estricta \(<\) no es un orden parcial en este sentido, porque no es reflexiva; se obtiene de \(\le\) quitando los pares \((a,a)\).

Una relación de equivalencia y una de orden comparten la reflexividad y la transitividad; difieren en que la primera es simétrica y la segunda antisimétrica. Un error frecuente es confundir antisimétrica con «no simétrica»: la relación de igualdad es a la vez simétrica y antisimétrica.

Un conjunto con un orden parcial se llama conjunto parcialmente ordenado. Para dibujarlo sin ruido se usa el diagrama de Hasse, y sobre él se definen elementos maximales, mínimos y cotas.

Para pensar

¿Es la igualdad \(=\) un orden parcial sobre un conjunto \(S\)?

Sí: es reflexiva, antisimétrica y transitiva. Es el orden en el que ningún par de elementos distintos es comparable.

Ejercicios 10

  1. ¿Cuál de estas relaciones en \(\mathbb{Z}\) es un orden parcial?
  2. ¿Qué propiedad de orden parcial falla en \(R=\{(1,1),(2,2),(1,2),(2,1)\}\) sobre \(\{1,2\}\)?
  3. En \(\{1,2,3,4,6,12\}\) con la divisibilidad, ¿qué par de elementos es incomparable?
  4. Si \(\preceq\) es un orden parcial con \(a\preceq b\) y \(b\preceq a\), ¿qué se concluye?
  5. ¿Por qué \(<\) en \(\mathbb{Z}\) no es un orden parcial?
  6. ¿Cuántos pares \((a,b)\) con \(a,b\in\{1,\dots,6\}\) cumplen \(a\mid b\)?
  7. En \(\mathcal{P}(\{a,b\})\) con \(\subseteq\), ¿cuántos pares \((A,B)\) cumplen \(A\subsetneq B\)?
  8. \(R=\{(1,1),(2,2),(3,3),(1,2),(2,3)\}\) en \(\{1,2,3\}\) no es orden parcial. ¿Qué par basta añadir para que lo sea?
  9. ¿Cuántos órdenes parciales distintos hay sobre el conjunto \(\{1,2\}\)?
  10. ¿Cuántos órdenes parciales sobre \(\{1,2,3\}\) comparan todos los pares de elementos?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §9.6
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §8.5
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §7.3