Conjunto parcialmente ordenado


Conjunto parcialmente ordenado

En matemáticas, especialmente en teoría del orden, un conjunto parcialmente ordenado (o poset, del inglés partially ordered set) es un conjunto equipado con una relación binaria de orden parcial. Ésta formaliza el concepto intuitivo de orden, secuencia, o arreglo de los elementos del conjunto. Un tal orden no necesariamente debe ser total, es decir, no se necesita que se puedan comparar unos con otros todos los elementos del conjunto; esto sin embargo puede ocurrir en algunos casos (en otras palabras, el orden total es un caso particular del orden parcial).

Contenido

Definición formal

Relación homogénea Relación reflexiva Relación no reflexiva Conjunto preordenado Relación de dependencia Conjunto parcialmente ordenado Relación de equivalencia Orden totalClasiBinaEs 004.svg
Acerca de esta imagen


Un orden parcial es una relación binaria R sobre un conjunto X que es reflexiva, antisimétrica, y transitiva, es decir, para cualesquiera a, b, y c en X se tiene que:

  • aRa (reflexividad).
  • Si aRb y bRa, entonces a = b (antisimetría).
  • Si aRb y bRc, entonces aRc (transitividad).

Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado o poset. A veces se usa la expresión conjunto ordenado para uno parcialmente ordenado, siempre que quede claro que no se hará referencia a otras clases de orden. En particular, a un conjunto totalmente ordenado también se lo llama ordenado a secas, en especial en campos donde éstos son más comunes que los parcialmente ordenados.

Usualmente se usa la notación de "≤" en lugar de "R" para el orden parcial.

Ejemplos

Conjunto de los subconjuntos de {x,y,z}, ordenado por inclusión.

Algunos de los ejemplos más conocidos son los siguientes:

  • El conjunto de los naturales con su orden usual (la relación "menor o igual"). Este orden es además un orden total.
  • El conjunto de los enteros con su orden usual. Este orden es también total.
  • Un subconjunto finito {1, 2,..., n} de los naturales. Este orden es también total.
  • El conjunto de naturales ordenado por la relación de divisibilidad.

Órdenes parciales estrictos y no estrictos

En algunos contextos, el orden parcial anteriormente definido se denomina no estricto o reflexivo; así pues, un orden parcial estricto o irreflexivo es una relación binaria que es irreflexiva y transitiva, y por lo tanto asimétrica. De forma equivalente, asimétrica (y por lo tanto irreflexiva) y transitiva.

Es decir, para cualesquiera a, b, y c en X se tiene que:

  • ¬(aRa) (irreflexividad).
  • Si aRb, entonces ¬(bRa) (asimetría).
  • Si aRb y bRc, entonces aRc (transitividad).

Si R es un orden parcial no estricto, entonces S = R − {(a, a) | aX} es el orden parcial estricto correspondiente. Análogamente, todo orden parcial estricto S tiene uno no estricto correspondiente, a saber, S ∪ {(a, a) | aP}, o la "clausura reflexiva" de R.

Los órdenes parciales estrictos son útiles porque se corresponden más directamente con los grafos acíclicos dirigidos: todo orden parcial estricto es un G.A.D., y la clausura transitiva de un G.A.D. es, además de un orden parcial estricto, un G.A.D. en sí misma.

Número de órdenes parciales

La secuencia A001035 de la OEIS da el número de órdenes parciales en un conjunto de n elementos.

Extensión lineal

Un orden total T es una extensión lineal de un orden parcial P si, siempre que xPy, se tiene que xTy.

Esquema de temas relacionados

Teoría del orden
Bien ordenado
Orden total
Parcialmente ordenado
Preordenado
Relación reflexiva
Relación transitiva
Relación antisimétrica
Relación total
Relación bien fundada

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Conjunto parcialmente ordenado — En matemáticas, un orden parcial, conjunto parcialmente ordenado, o poset, en inglés y para abreviar, es una relación binaria especial que formaliza el concepto intuitivo de ordenar. Los conjuntos parcialmente ordenados se estudian en la teoría… …   Enciclopedia Universal

  • Conjunto bien ordenado — En teoría de conjuntos, un conjunto bien ordenado es un conjunto no vacío totalmente ordenado tal que todo subconjunto no vacío tiene un elemento mínimo. Equivalentemente, puede decirse que un conjunto A es bien ordenado si es totalmente ordenado …   Wikipedia Español

  • Conjunto preordenado — En matemática, especialmente en teoría del orden, preórdenes son ciertas clases de relaciones binarias que se relacionan con los conjuntos parcialmente ordenados. El nombre quasiorden es también una expresión común para preórdenes. Muchas… …   Wikipedia Español

  • Orden total — En matemáticas, un orden total, orden lineal, orden simple, o simplemente orden en un conjunto X es una relación binaria sobre X que es antisimétrica, transitiva, y total; esto es, si se denota una tal relación por ≤, lo siguiente vale para… …   Wikipedia Español

  • Teoría del orden — La teoría del orden es una rama de la matemática que estudia varias clases de relaciones binarias que capturan la noción intuitiva del orden matemático. Este artículo da una introducción detallada a este campo e incluye algunas de las… …   Wikipedia Español

  • Retículo (orden) — Diagrama de Hasse del retículo de particiones del conjunto {1,2,3,4}. En matemática, un retículo es una determinada estructura algebraica con dos operaciones binarias, o bien un conjunto parcialmente ordenado con ciertas propiedades específicas… …   Wikipedia Español

  • Axioma de elección — Saltar a navegación, búsqueda En matemáticas, el axioma de elección o axioma de escogencia, abreviado usualmente AE, o AC por sus siglas en inglés, es un axioma de la teoría de conjuntos. Intuitivamente, AE dice que dada una colección de… …   Wikipedia Español

  • Filtro (matemática) — Saltar a navegación, búsqueda En matemática, y específicamente en teoría del orden, retículos y topología, un filtro es un subconjunto especial de un conjunto parcialmente ordenado. Un caso especial utilizado con frecuencia es cuando el conjunto… …   Wikipedia Español

  • Lema de Zorn — El lema de Zorn, también llamado de Kuratowski Zorn, es una proposición de la teoría de conjuntos que afirma lo siguiente: Todo conjunto parcialmente ordenado no vacío en el que toda cadena (subconjunto totalmente ordenado) tiene una cota… …   Wikipedia Español

  • Diagrama de Hasse — Saltar a navegación, búsqueda Elementos de P( P( P(P({})))) en Diagrama de Hasse. En matemáticas, un diagrama de Hasse es una representación …   Wikipedia Español