Conjunto parcialmente ordenado

Un conjunto parcialmente ordenado es un concepto matemático que formaliza las ideas intuitivas de ordenar, la disposición de los elementos en una determinada secuencia. De manera informal, un conjunto está parcialmente ordenado si se especifica qué elementos siguen a qué (qué elementos son mayores que cuáles). En general, puede resultar que algunos pares de elementos no estén relacionados por la relación " sigue " .

Como ejemplo abstracto, podemos dar una colección de subconjuntos de un conjunto de tres elementos ( el booleano de un conjunto dado), ordenados por la relación de inclusión. $\{x,y,z\}$

Definición y ejemplos

La relación de orden , u orden parcial , en un conjunto es una relación binaria en(definida por algún conjunto) que satisface las siguientes condiciones [1] : $METRO$ $\varphi$ $METRO$ $R_{{\varphi }}\subconjunto M\veces M$

reflexividad : $\forall a\;(a\varphi a)$
transitividad : $\forall a,b,c\;(a\varphi b)\cuña (b\varphi c)\Rightarrow a\varphi c$
Antisimetría : $\forall a,b\;(a\varphi b)\cuña (b\varphi a)\Rightarrow a=b$

El conjunto sobre el que se da la relación de orden parcial se llama parcialmente ordenado . Para ser bastante preciso [2] , entonces un conjunto parcialmente ordenado es un par , donde es un conjunto y es una relación de orden parcial en . $METRO$ $\langle M,\varphi \rangle$ $METRO$ $\varphi$ $METRO$

La dimensión de un conjunto parcialmente ordenado es igual al número máximo del conjunto de órdenes lineales ( ). Esta definición se basa en la propiedad de extensibilidad de un orden parcial a uno lineal. ${\ estilo de visualización \ langle M, \ varphi \ rangle}$ ${\ estilo de visualización <_{i))$ $yo en yo$

Terminología y notación

La relación de orden parcial se suele denotar con el símbolo , por analogía con la relación "menor o igual que" sobre el conjunto de los números reales . Además, si , entonces decimos que el elemento no excede a , o que está subordinado a . $\leqslant$ $a\leqslant b$ $a$ $b$ $a$ $b$

Si y , entonces escriben y dicen que es menor que , o que está estrictamente subordinado a . $a\leqslant b$ $a \ neq b$ $a<b$ $a$ $b$ $a$ $b$

A veces, para distinguir un orden arbitrario en un determinado conjunto de la conocida relación "menor que o igual" en el conjunto de números reales, se utilizan los símbolos especiales y en lugar de y , respectivamente. $\leqslant$ $<$ $\preccurlyeq$ $\prec$

Orden estricto y no estricto

Una relación que satisface las condiciones de reflexividad, transitividad y antisimetría también se denomina orden reflexivo o no estricto . Si la condición de reflexividad se reemplaza por la condición de antirreflexividad (entonces la propiedad de antisimetría se reemplaza por asimetría):

\forall a\;\neg (a\varphi a)

entonces obtenemos la definición de orden estricto o antirreflexivo .

Si es un orden no estricto en el conjunto , entonces la relación , definida como: $\leqslant$ $METRO$ $<$

a<b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a\leqslant b)\cuña (a\neq b)

es un orden estricto en . Por el contrario, si es un orden estricto, entonces la relación definida como $METRO$ $<$ $\leqslant$

a\leqslant b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a<b)\vee (a=b)

es un orden no estricto.

Por lo tanto, es lo mismo especificar un orden no estricto o estricto en el conjunto . El resultado es la misma estructura. La diferencia es solo en terminología y notación.

Intervalo

Para un intervalo cerrado [ a , b ] es un conjunto de elementos x que satisfacen la desigualdad (es decir, y ). El intervalo contiene al menos los elementos a y b . $a\leqslant b$ $a\leqslant x\leqslant b$ $a\leqslant x$ $x\leqslant b$

Si usamos la desigualdad estricta "<", obtenemos un intervalo abierto ( a , b ), un conjunto de elementos x que satisfacen la desigualdad a < x < b (es decir , a < x y x < b ). Un intervalo abierto puede estar vacío incluso si a < b . Por ejemplo, el intervalo abierto (1,2) para enteros está vacío porque no hay enteros i tales que 1 < i < 2.

A veces, la definición se amplía para permitir a > b . En este caso, el intervalo está vacío.

Los intervalos semiabiertos [ a , b ) y ( a , b ] se definen de manera similar.

Un poset es localmente finito si todo intervalo es finito. Por ejemplo, los números enteros son localmente finitos en su ordenación natural. El orden lexicográfico en el producto directo ℕ×ℕ no es localmente finito porque, por ejemplo, . $(1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)$

El concepto de un intervalo en posets no debe confundirse con una clase específica de posets conocida como órdenes de intervalo .

Ejemplos

El conjunto de los números reales está parcialmente ordenado según la relación "menor o igual que" - . $\matemáticas {R}$ $\leqslant$

Sea el conjunto de todas las funciones de valor real definidas en el segmento , es decir, funciones de la forma $METRO$ $[a,b]$

f\dos puntos [a,b]\to {\mathbb {R}}

Introduzcamos la relación de orden en como sigue: , si la desigualdad se cumple para todo . Obviamente, la relación presentada es de hecho una relación de orden parcial. $\leqslant$ $METRO$ $f \ leqslant g$ $x\en[a,b]$ $f(x)\leqslant g(x)$

Sea un conjunto. El conjunto de todos los subconjuntos (el llamado booleano ), está parcialmente ordenado por inclusión . $METRO$ ${\ matemáticas {P}} (M)$ $METRO$ $M\subconjunto N$

El conjunto de todos los números naturales está parcialmente ordenado por la relación de divisibilidad . $\matemáticas {N}$ $m\mid n$

Definiciones relacionadas

Elementos incomparables

Si y son números reales , entonces solo se cumple una de las siguientes relaciones: $a$ $b$

a<b,\qquad a=b,\qquad b<a

Si y son elementos de un conjunto arbitrario parcialmente ordenado, entonces existe una cuarta posibilidad lógica: ninguna de las tres relaciones anteriores se cumple. En este caso, los elementos y se denominan incomparables . Por ejemplo, si es el conjunto de funciones de valor real en el segmento , entonces los elementos y serán incomparables. La posibilidad de la existencia de elementos incomparables explica el significado del término "conjunto parcialmente ordenado" . $a$ $b$ $a$ $b$ $METRO$ $[0,1]$ $f(x) = x$ $g(x)=1-x$

Elementos Mínimo/Máximo y Mínimo/Mayor

Debido a que puede haber pares de elementos incomparables en un conjunto parcialmente ordenado, se introducen dos definiciones diferentes: el elemento mínimo y el elemento mínimo .

Se dice que un elemento es mínimo si el elemento no existe . En otras palabras, es el elemento mínimo si para cualquier elemento , o , o y son incomparables. Un elemento se llama el más pequeño si para cualquier elemento se cumple la desigualdad . Obviamente, cualquier elemento más pequeño también es mínimo, pero lo contrario no es cierto en el caso general: el elemento mínimo puede no ser el más pequeño si hay elementos que no son comparables con . $un \ en M$ $b<a$ $a$ $b\en M$ $b>a$ $b=a$ $b$ $a$ $a$ $b\en M$ $b \ geqslant a$ $a$ $b$ $a$

Obviamente, si hay un elemento más pequeño en un conjunto, entonces es único. Pero puede haber varios elementos mínimos. Como ejemplo, considere el conjunto de números naturales sin unidad, ordenados por la relación de divisibilidad . Aquí, los elementos mínimos serán números primos , pero el elemento más pequeño no existe. ${\mathbb {N}}\setminus \{1\}=\{2,3,\ldots \}$ $\medio$

Los conceptos de elementos máximos y mayores se introducen de manera similar.

Caras superior e inferior

Sea un subconjunto de un conjunto parcialmente ordenado . Un elemento se llama límite superior si ningún elemento excede . El concepto de límite inferior del conjunto se introduce de manera similar . $A$ $\langle M,\leqslant \rangle$ $u\en M$ $A$ $a \ en A$ $tu$ $A$

Cualquier elemento mayor que alguna cara superior también será una cara superior . Y cualquier elemento menor que algún ínfimo será también un ínfimo . Estas consideraciones conducen a la introducción de los conceptos de límite superior mínimo y límite inferior máximo . $A$ $A$ $A$ $A$

Conjuntos superior e inferior

Para un elemento de un conjunto parcialmente ordenado, el conjunto superior es el conjunto de todos los elementos precedidos por ( ). $metro$ $\langle M,\leqslant \rangle$ $M\flecha arriba m$ $metro$ $\{x\in M\mid m\leqslant x\}$

El conjunto inferior se define dualmente como el conjunto de todos los elementos que preceden al dado: . $M\downarrow m{\stackrel {{\mathrm {def}}}{=}}\{x\in M\mid x\leqslant m\}$

Condiciones de ruptura

Se dice que un conjunto parcialmente ordenado satisface la condición de terminación de cadena estrictamente creciente si no existe una secuencia infinita estrictamente creciente . Esta condición es equivalente a la condición de estabilización para cadenas no estrictamente crecientes : cualquier secuencia no estrictamente creciente de sus elementos se estabiliza. Es decir, para cualquier sucesión de la forma $METRO$ ${\ estilo de visualización (a_{i}\,<\,a_{i+1})}$ $(a_{i}\,\leqslant\,a_{i+1})$

a_{1}\,\leqslant \,a_{2}\,\leqslant \,a_{3}\,\leqslant \,\cdots

hay un natural tal que $norte,$

a_{n}=a_{{n+1}}=a_{{n+2}}=\cdots.

Definido de manera similar para cadenas decrecientes, obviamente satisface la condición de terminación de la cadena descendente si y solo si se estabiliza cualquier secuencia no estrictamente decreciente de sus elementos. Estos conceptos se utilizan a menudo en álgebra general ; véase, por ejemplo, anillo de Noether, anillo de Artinian . $METRO$

Tipos especiales de conjuntos parcialmente ordenados

Conjuntos linealmente ordenados

Sea un conjunto parcialmente ordenado. Si en cualesquiera dos elementos son comparables, entonces el conjunto se llama linealmente ordenado . Un conjunto linealmente ordenado también se llama conjunto perfectamente ordenado , o simplemente, conjunto ordenado [3] . Así, en un conjunto ordenado linealmente, para dos elementos cualesquiera y , se cumple una y sólo una de las relaciones: o , o , o . $\langle M,\leqslant \rangle$ $METRO$ $METRO$ $a$ $b$ $a<b$ $a=b$ $b<a$

Además, cualquier subconjunto ordenado linealmente de un conjunto parcialmente ordenado se denomina cadena , es decir, una cadena en un conjunto parcialmente ordenado es su subconjunto en el que dos elementos cualesquiera son comparables. $\langle M, \leqslant \rangle$

De los ejemplos de conjuntos parcialmente ordenados anteriores, solo el conjunto de números reales está ordenado linealmente. El conjunto de funciones de valores reales en el intervalo (bajo la condición ), Boolean (para ), números naturales con una relación de divisibilidad no están ordenados linealmente. $[a,b]$ $a<b$ ${\ matemáticas {P}} (M)$ $|M|\geqslant 2$

En un conjunto ordenado linealmente, los conceptos de mínimo y mínimo, así como de mayor y máximo, son los mismos.

Conjuntos bien ordenados

Un conjunto ordenado linealmente se llama bien ordenado si cada uno de sus subconjuntos no vacíos tiene un elemento mínimo [4] . Tal orden en un conjunto se denomina orden completo , en un contexto en el que no puede confundirse con un orden completo en el sentido de conjuntos completos parcialmente ordenados .

Un ejemplo clásico de un conjunto bien ordenado es el conjunto de los números naturales . La afirmación de que cualquier subconjunto no vacío contiene el elemento más pequeño es equivalente al principio de inducción matemática . Un ejemplo de un conjunto ordenado linealmente pero no bien ordenado es el conjunto naturalmente ordenado de números no negativos . De hecho, su subconjunto no tiene el elemento más pequeño. $\matemáticas {N}$ $\matemáticas {N}$ ${\mathbb {R}}_{{+}}=\{x:x\geqslant 0\}$ $\{x:x>1\}$

Los conjuntos bien ordenados juegan un papel excepcionalmente importante en la teoría general de conjuntos .

La pose completa

Un poset completo es un poset que tiene un fondo , el único elemento que precede a cualquier otro elemento y que cada subconjunto dirigido tiene un límite superior exacto [5] . Los conjuntos completos parcialmente ordenados se utilizan en cálculo λ e informática , en particular, se introduce en ellos la topología de Scott , sobre la base de la cual se construye un modelo consistente de cálculo λ y semántica denotacional . Un caso especial de un conjunto completo parcialmente ordenado es un retículo completo : si algún subconjunto, no necesariamente dirigido, tiene un límite superior mínimo, resulta ser un retículo completo.

Un conjunto ordenado es un conjunto completo parcialmente ordenado si y sólo si cada función monótona con respecto al orden ( ) tiene al menos un punto fijo : . $METRO$ $f\dos puntos M\flecha derecha M$ $a\leqslant b\Rightarrow f(a)\leqslant f(b)$ $\existe _ {{x\en M}}f(x)=x$

Cualquier conjunto se puede convertir en uno completo parcialmente ordenado extrayendo el fondo y definiendo el orden para todos los elementos del conjunto . $METRO$ $\bot$ $\leqslant$ $\bot \leqslant m$ $m\leqslant m$ $metro$ $METRO$

Teoremas sobre conjuntos parcialmente ordenados

Los teoremas fundamentales sobre conjuntos parcialmente ordenados incluyen el principio máximo de Hausdorff y el lema de Kuratowski-Zorn . Cada uno de estos teoremas es equivalente al axioma de elección .

En teoría de categorías

Cada poset (y cada preorden ) puede verse como una categoría , en la que cada conjunto de morfismos consta de un elemento como máximo. Por ejemplo, esta categoría se puede definir de la siguiente manera: si A ≤ B (y el conjunto vacío en caso contrario); regla de composición de morfismos: ( y , z )∘( x , y ) = ( x , z ). Cada categoría de pedido anticipado es equivalente a un conjunto pedido parcialmente. ${\mathrm {Hom}}(A,B)$ ${\mathrm {Hom}}(A,B)=\{(A,B)\}$

Un funtor de un conjunto de categorías parcialmente ordenadas (es decir, un diagrama cuya categoría de índice es un poset) es un diagrama conmutativo .

Notas

↑ Kolmogorov, 2004 , pág. 36.
↑ Aleksándrov, 1977 , pág. 78.
↑ Kolmogorov, 2004 , pág. 38.
↑ Kolmogorov, 2004 , pág. 40
↑ Barendregt, 1985 , pág. 23

Literatura

Aleksandrov PS Introducción a la teoría de conjuntos y topología general. — M .: Nauka , 1977. — 368 p.
Barendregt, Henk. Cálculo lambda. Su sintaxis y semántica = El Cálculo Lambda. Su sintaxis y semántica. — M .: Mir , 1985. — 606 p. - 4800 copias.
Kolmogorov AN, Fomin SV Elementos de la teoría de funciones y análisis funcional. - 7ª ed. — M .: Fizmatlit , 2004. — 572 p. — ISBN 5-9221-0266-4 .
Hausdorff F. Teoría de conjuntos. - 4ª ed. — M .: URSS , 2007. — 304 p. - ISBN 978-5-382-00127-2 .
Gurov S. I. Álgebras de Boole, conjuntos ordenados, redes: Definiciones, propiedades, ejemplos. - 2ª ed. — M .: Librokom , 2013. — 352 p. - ISBN 978-5-397-03899-7 .