Teoría de Conjuntos - 28. Conjuntos parcialmente ordenados

28.1 Introducción

En el tema anterior vimos que una relación de orden parcial es reflexiva, antisimétrica y transitiva. Cuando un conjunto se estudia junto con una relación de ese tipo, obtenemos un conjunto parcialmente ordenado.

Estos conjuntos aparecen en jerarquías, dependencias, subconjuntos, permisos, versiones, tareas y estructuras donde algunos elementos pueden compararse y otros no.

28.2 Definición de conjunto parcialmente ordenado

Un conjunto parcialmente ordenado es un par formado por un conjunto A y una relación de orden parcial ≤ definida sobre A.

(A, ≤)

También se lo conoce como poset, abreviatura de "partially ordered set".

28.3 Condiciones del orden parcial

Para que (A, ≤) sea un conjunto parcialmente ordenado, la relación debe cumplir tres propiedades.

Propiedad	Condición	Interpretación
Reflexiva	a ≤ a	Todo elemento se compara consigo mismo
Antisimétrica	Si a ≤ b y b ≤ a, entonces a = b	No hay ciclos entre elementos distintos
Transitiva	Si a ≤ b y b ≤ c, entonces a ≤ c	Las comparaciones pueden encadenarse

28.4 Elementos comparables

Dos elementos a y b son comparables si se cumple a ≤ b o b ≤ a.

a y b son comparables si a ≤ b o b ≤ a

En un orden parcial, no todos los elementos tienen que ser comparables.

28.5 Elementos incomparables

Dos elementos son incomparables si ninguno está relacionado con el otro por el orden.

a y b son incomparables si no se cumple a ≤ b ni b ≤ a

Esta es la diferencia principal entre un orden parcial y un orden total.

28.6 Ejemplo con inclusión de conjuntos

Sea A = {1, 2}. El conjunto potencia P(A) ordenado por inclusión forma un conjunto parcialmente ordenado.

P(A) = {∅, {1}, {2}, {1, 2}} Relación: ⊆

Los conjuntos {1} y {2} son incomparables porque ninguno está contenido en el otro.

28.7 Ejemplo con divisibilidad

La divisibilidad también define un orden parcial en ciertos conjuntos de números.

A = {1, 2, 3, 6} a ≤ b si a divide a b

En este orden, 2 y 3 son incomparables porque 2 no divide a 3 y 3 no divide a 2. Pero ambos dividen a 6.

28.8 Elemento mínimo

Un elemento mínimo es un elemento que no tiene otro elemento estrictamente menor dentro del conjunto.

m es mínimo si no existe x tal que x < m

Puede haber más de un elemento mínimo en un conjunto parcialmente ordenado.

28.9 Elemento máximo

Un elemento máximo es un elemento que no tiene otro elemento estrictamente mayor dentro del conjunto.

m es máximo si no existe x tal que m < x

También puede haber más de un elemento máximo.

28.10 Menor elemento y mayor elemento

El menor elemento de un conjunto parcialmente ordenado es un elemento que está por debajo de todos los demás. El mayor elemento está por encima de todos los demás.

Concepto	Condición	Observación
Menor elemento	m ≤ x para todo x	Si existe, es único
Mayor elemento	x ≤ m para todo x	Si existe, es único
Elemento mínimo	No hay nada estrictamente menor	Puede haber varios
Elemento máximo	No hay nada estrictamente mayor	Puede haber varios

28.11 Diagramas de Hasse

Un diagrama de Hasse representa visualmente un conjunto parcialmente ordenado. Se dibujan los elementos y las relaciones inmediatas entre ellos, omitiendo flechas reflexivas y relaciones que se deducen por transitividad.

Para P({1, 2}) ordenado por inclusión: {1, 2} / \ {1} {2} \ / ∅

El diagrama muestra que {1} y {2} son incomparables.

28.12 Cotas superiores e inferiores

Dado un subconjunto, una cota superior es un elemento que está por encima de todos sus elementos. Una cota inferior está por debajo de todos ellos.

u es cota superior de S si x ≤ u para todo x ∈ S l es cota inferior de S si l ≤ x para todo x ∈ S

Estas ideas serán útiles en estructuras ordenadas más avanzadas.

28.13 Representar un poset en JavaScript

Podemos representar los elementos y una función que decide si un elemento es menor o igual que otro.

const subconjuntos = [
  [],
  [1],
  [2],
  [1, 2]
];

function esSubconjunto(a, b) {
  return a.every(elemento => b.includes(elemento));
}

console.log(esSubconjunto([1], [1, 2]));
console.log(esSubconjunto([1], [2]));

La función modela el orden parcial dado por inclusión.

28.14 Detectar elementos comparables en JavaScript

function esSubconjunto(a, b) {
  return a.every(elemento => b.includes(elemento));
}

function sonComparables(a, b, menorOIgual) {
  return menorOIgual(a, b) || menorOIgual(b, a);
}

console.log(sonComparables([1], [1, 2], esSubconjunto));
console.log(sonComparables([1], [2], esSubconjunto));

El primer caso es comparable; el segundo no lo es.

28.15 Aplicaciones prácticas

Área	Orden parcial	Uso
Permisos	Conjunto de permisos por inclusión	Comparar niveles de acceso
Dependencias	Tarea A debe preceder a tarea B	Planificar ejecución
Versiones	Dependencias entre versiones	Determinar compatibilidad
Taxonomías	Categorías por inclusión	Organizar conceptos
Grafos	Alcanzabilidad sin ciclos	Modelar jerarquías

28.16 Errores frecuentes

Creer que en un orden parcial todos los elementos deben ser comparables.
Confundir elemento mínimo con menor elemento.
Confundir elemento máximo con mayor elemento.
Olvidar que un diagrama de Hasse omite relaciones reflexivas y transitivas deducibles.
Tratar una relación de orden parcial como si siempre fuera un orden total.

28.17 Qué debes recordar de este tema

Un conjunto parcialmente ordenado es un par (A, ≤).
La relación debe ser reflexiva, antisimétrica y transitiva.
No todos los elementos tienen que ser comparables.
La inclusión de subconjuntos es un ejemplo de orden parcial.
Los diagramas de Hasse representan órdenes parciales de forma visual.
En JavaScript, un orden parcial puede modelarse con una función de comparación.

28.18 Conclusión

Los conjuntos parcialmente ordenados permiten modelar jerarquías donde no todas las comparaciones son posibles. Son fundamentales para estudiar inclusión, dependencias, permisos y estructuras ordenadas.

En el próximo tema estudiaremos funciones como relaciones especiales.

Volver al índice