Teoría da orde

A teoría da orde é unha rama das matemáticas que investiga a noción intuitiva de orde mediante relacións binarias. Ofrece un marco formal para describir afirmacións como "isto é menor que iso" ou "isto precede a iso". Este artigo presenta o campo e proporciona definicións básicas. Na Wikipedia en inglés hai un glosario de termos Glosario da teoría da orde.

Antecedentes e motivación

Algunhas ordes, como "menor que" nos números naturais e a orde alfabética nas palabras, teñen unha propiedade especial: cada elemento pódese comparar con calquera outro elemento, é dicir, é máis pequeno (antes), máis grande (posterior) ou idéntico a. Porén, moitas outros tipos de orde non. Considere, por exemplo, a orde do subconxunto nunha colección de conxuntos: aínda que o conxunto de aves e o conxunto de cans son ambos os dous subconxuntos do conxunto de animais, nin os paxaros nin os cans constitúen un subconxunto do outro. Aquelas ordes como a relación "subconxunto de" para as que existen elementos incomparables chámanse ordes parciais; ordes para as que cada par de elementos é comparable son ordes totais .

A teoría da orde recolle a intuición das ordes que xorde a partir deste tipo de exemplos nun contexto xeral. Isto conséguese especificando as propiedades que debe ter unha relación ≤ para ser unha orde matemática.

Impulsados polo amplo uso práctico do que é a orde, definíronse numerosos tipos especiais de conxuntos ordenados, algúns dos cales se converteron en campos matemáticos propios. A maiores, a teoría da orde non se restrinxe ás diversas clases de relacións de ordenación, senón que tamén considera funcións adecuadas entre elas. Un exemplo sinxelo dunha propiedade teórica de orde para funcións provén da análise onde se atopan frecuentemente funcións monótonas.

Definicións básicas

Esta sección introduce conxuntos ordenados a partir dos conceptos de teoría de conxuntos, aritmética e relacións binarias.

Conxuntos parcialmente ordenados

Unha orde é unha relación binaria especial. Supoñamos que P é un conxunto e que ≤ é unha relación sobre P (enténdese que 'relación sobre un conxunto' significa 'relación entre os seus elementos', é dicir, ≤ é un subconxunto do produto cartesiano P x P). Entón ≤ é unha orde parcial se é reflexiva, antisimétrica e transitiva, é dicir, se para todos a, b e c en P, temos que:

a ≤ a (reflexividade)

se a ≤ b e b ≤ a entón a = b (antisimetría)

se a ≤ b e b ≤ c entón a ≤ c (transitividade).

Un conxunto cunha orde parcial sobre el chámase conxunto parcialmente ordenado, ou poset (do inglés "partial ordered set". Ao comprobar estas propiedades, vese inmediatamente que a orde coñecida sobre números naturais, enteiros, números racionais e reais son todas ordes no sentido anterior. No entanto, estes exemplos teñen a propiedade adicional de que dous elementos calquera son comparables, é dicir, para todo a e b en P, temos que:

a ≤ b ou b ≤ a .

Unha orde parcial con esta propiedade chámase orde total. Este tipo de orde tamén pode denominarse orde linear ou cadea. Aínda que moitas ordes coñecidas son lineais, a orde de subconxuntos nos conxuntos ofrece un exemplo onde este non é o caso. Outro exemplo vén dado pola relación de divisibilidade (ou "é un factor de"). Para dous números naturais n e m, escribimos n | m se n divide m sen resto. Vese facilmente que isto dá unha orde parcial. Por exemplo, nin 3 divide 13 nin 13 divide 3, polo que 3 e 13 non son elementos comparables da relación de divisibilidade no conxunto de números enteiros. A relación de identidade = en calquera conxunto tamén é unha orde parcial na que cada dous elementos distintos son incomparables. Tamén é a única relación que é tanto unha orde parcial como unha relación de equivalencia porque satisfai tanto a propiedade de antisimetría das ordes parciais como a propiedade de simetría das relacións de equivalencia. Moitas propiedades avanzadas dos posets son interesantes principalmente para unha orde de tipo non linear.

Visualización dun poset

Diagrama de Hasse do conxunto de todos os divisores de 60, parcialmente ordenados pola divisibilidade

Os diagramas de Hasse poden representar visualmente os elementos e as relacións dunha ordenación parcial. Trátase de debuxos gráficos onde os vértices son os elementos do poset e a relación de ordenación indícase tanto polos bordos como pola posición relativa dos vértices. As ordes son debuxadas de abaixo cara arriba: se un elemento x é menor que (precede) a y, existe un camiño de x a y dirixido cara arriba. A miúdo é necesario que os elementos de conexión dos bordos se crucen entre si, mais os elementos nunca deben situarse dentro dun bordo. Un exercicio instrutivo consiste en debuxar o diagrama de Hasse para o conxunto de números naturais que son menores ou iguais a 13, ordenados pola relación divisor).

Mesmo algúns conxuntos infinitos poden diagramarse superpoñendo puntos suspensivos dentro dunha suborde finita. Isto funciona ben para os números naturais, mais falla para os reais, onde non hai un sucesor inmediato por riba de 0; porén, moitas veces pódese obter unha intuición relacionada con diagramas de tipo similar.

Elementos especiais dentro dunha orde

Nun conxunto parcialmente ordenado pode haber algúns elementos que xogan un papel especial. O exemplo máis básico é o menor elemento dun poset . Por exemplo, 1 é o elemento menor dos enteiros positivos e o conxunto baleiro é o conxunto menos baixo a orde do subconxunto. Formalmente, un elemento m é un elemento mínimo se:

m ≤ a, para todos os elementos a da orde.

Os elementos menores e maiores poden non existir, como mostra o exemplo dos números reais. Mais se existen, sempre son únicos. En contraste, considere a relación de divisibilidade | no conxunto {2,3,4,5,6}. Aínda que este conxunto non ten nin superior nin inferior en relación coa divisibilidade, os elementos 2, 3 e 5 non teñen ningún elemento por debaixo, mentres que 4, 5 e 6 non teñen ningún por riba. Estes elementos chámanse minimal e maximal, respectivamente. Formalmente, un elemento m é minimal se:

a ≤ m implica a = m, para todos os elementos a da orde.

Mudando ≤ por ≥ obtemos a definición de maximal. Como mostra o exemplo, pode haber moitos elementos maximais e algúns elementos poden ser tanto maximal como minimal (por exemplo, o 5 anterior). No entanto, se hai un elemento menor, entón é o único elemento minimal da orde. De novo, en posets infinitos non sempre existen elementos maximais: o conxunto de todos os subconxuntos finitos dun conxunto infinito dado, ordenados pola inclusión de subconxuntos, proporciona un dos moitos contraexemplos. Unha ferramenta importante para garantir a existencia de elementos maximais baixo certas condicións é o Lema de Zorn.

Os subconxuntos de conxuntos parcialmente ordenados herdan a orde. Xa aplicamos isto considerando o subconxunto {2,3,4,5,6} dos números naturais coa orde de divisibilidade inducida. Tamén hai elementos dun poset que son especiais con respecto a algún subconxunto da orde. Isto leva á definición de elementos maiorantes. Dado un subconxunto S dalgún conxunto P, un elemento maiorante de S é un elemento b de P que está por riba de todos os elementos de S. Formalmente, isto significa que

s ≤ b, para todos os s en S .

Os elementos minorantes defínense de novo invertendo a orde. Por exemplo, -5 é un elemento minorante dos números naturais como un subconxunto dos enteiros. Dado un conxunto de conxuntos, un elemento maiorante para estes conxuntos baixo a ordenación do subconxunto vén dado pola súa unión. De feito, este elemento maiorante é bastante especial: é o conxunto máis pequeno que contén todos os conxuntos. Así damos cun novo concepto, o elemento maiorante mínimo dun conxunto de conxuntos. Este concepto tamén se denomina supremo ou join, e para un conxunto S escríbese sup(S) ou $\bigvee S$. Pola contra, o elemento minorante máis grande coñécese como infimo ou meet e denomínase inf(S) ou $\bigwedge S$. Estes conceptos xogan un papel importante en moitas aplicacións da teoría da orde. Para dous elementos x e y, tamén se escribe $x\vee y$ e $x\wedge y$ para sup({ x, y }) e inf({ x, y }), respectivamente.

Por exemplo, 1 é o ínfimo dos enteiros positivos como subconxunto de enteiros.

Dualidade

Nas definicións anteriores, a miúdo observamos que un concepto pode definirse con só inverter a ordenación nunha definición anterior. Este é o caso de "menor" e "maior", de "minimal" e "maximal", de "maiorante" e "minorante", etc. Esta é unha situación xeral na teoría da orde: unha orde dada pódese inverter simplemente trocando a súa dirección, volteando pictóricamente o diagrama de Hasse de arriba abaixo. Isto produce a chamada orde dual, inversa ou oposta.

Pódense atopar algúns detalles e exemplos máis no artigo sobre a teoría da dualidade na teoría da orde.

Construción de novas ordes

Hai moitas formas de construír ordes a partir de ordes dadas. A orde dual é un exemplo. Outra construción importante é o produto cartesiano de dous conxuntos parcialmente ordenados, xunto coa orde do produto en pares de elementos. A ordenación defínese por (a, x) ≤ (b, y) se (e só se) a ≤ b e x ≤ y. (Nótese con coidado que hai tres significados distintos para o símbolo de relación ≤ nesta definición.) A unión disxunta de dous posetos é outro exemplo típico de construción de ordes, onde a orde é só a unión (disxunta) das ordes orixinais.

Toda orde parcial ≤ dá lugar á chamada orde estrita <, ao definir a < b se a ≤ b e non b ≤ a. Esta transformación pódese inverter establecendo a ≤ b se a < b ou a = b. Os dous conceptos son equivalentes aínda que nalgunhas circunstancias pode ser máis cómodo traballar cun que o outro.

Funcións entre ordes

É razoable considerar funcións entre conxuntos parcialmente ordenados que teñan certas propiedades adicionais que están relacionadas coas relacións de ordenación dos dous conxuntos. A condición máis fundamental que se dá neste contexto é a monotonía. Unha función f dun poset P a un poset Q é monótona, ou conserva a orde, se a ≤ b en P implica f (a) ≤ f (b) en Q (observando que, estritamente, as dúas relacións aquí son diferentes xa que se aplican a distintos conxuntos). A inversa desta implicación leva a funcións que reflicten a orde, é dicir, funcións f como as anteriores para as que f (a) ≤ f (b) implica a ≤ b. Por outra banda, unha función tamén pode ser inversora de orde ou antítona, se a ≤ b implica f (a) ≥ f (b).

Unha inserción de orde é unha función f entre ordes que é á vez conservadora e reflectora da orde. Por exemplo, a función que asigna un número natural ao seu sucesor é claramente monótona con respecto á orde natural. Calquera función dunha orde discreta, é dicir, dun conxunto ordenado pola orde de identidade "=", tamén é monótona. A correspondencia de cada número natural co número real correspondente dáse un exemplo de incorporación de orde. O complemento dun conxunto nun conxunto das partes é un exemplo dunha función antítona.

Unha cuestión importante é cando dúas ordes son "esencialmente iguais", é dicir, cando son iguais ata o cambio de nome dos elementos. Os isomorfismos de orde son funcións que definen esa mudanza de nome. Un isomorfismo de orde é unha función bixectiva monótona que ten unha inversa monótona. Isto equivale a ser unha orde sobrexectiva por inserción. Polo tanto, a imaxe f(P) dunha orde por inserción é sempre isomorfa a P, o que xustifica o termo "inserción".

Un tipo máis elaborado de funcións vén dado polas chamadas conexións de Galois. As conexións monótonas de Galois pódense ver como unha xeneralización de isomorfismos de orde, xa que constitúen un par de dúas funcións en direccións inversas, que "non son totalmente" inversas entre si, pero teñen relacións estreitas.

Outro tipo especial de automapas nun poset son os operadores de pechamento, que non só son monótonos, senón tamén idempotentes, é dicir, f(x) = f( f (x)), e extensivos (ou inflacionarios), é dicir, x ≤ f(x). Estes teñen moitas aplicacións en todo tipo de “pechamentos” que aparecen nas matemáticas.

Cando se fala de posets con elemento menor, pode parecer razoable considerar só as funcións monótonas que conservan este elemento, é dicir, que mapean elementos menores con elementos menores. Se existe un ínfimo binario ∧, entón unha propiedade razoable podería ser esixir que f(x∧y) = f(x)∧f(y), para todos os x e y. Todas estas propiedades, e de feito moitas máis, pódense compilar baixo a etiqueta de funcións de preservación de límites.

Finalmente, pódese inverter a vista, mudando de funcións de orde a orde de funcións. De feito, as funcións entre dous posets P e Q poden ordenarse mediante a orde punto a punto. Para dúas funcións f e g, temos f ≤ g se f(x) ≤ g (x) para todos os elementos x de P. Isto acontece, por exemplo, na teoría de dominios, onde os espazos de función xogan un papel importante.

Tipos especiais de orde

Moitas das estruturas que se estudan na teoría da orde empregan relacións de orde con outras propiedades. De feito, incluso algunhas relacións que non son ordes parciais teñen especial interese. Hai que mencionar principalmente o concepto de preorde. Unha preorde é unha relación que é reflexiva e transitiva, mais non necesariamente antisimétrica. Cada preorde induce unha relación de equivalencia entre elementos, onde a é equivalente a b, se a ≤ b e b ≤ a. As preordes pódense converter en ordes identificando todos os elementos que son equivalentes relativos a esta relación.

Pódense definir varios tipos de pedidos a partir de datos numéricos sobre os elementos da orde: unha orde total resulta de unir distintos números reais a cada elemento e empregar as comparacións numéricas para ordenar os elementos; no seu lugar, se se permite que distintos elementos teñan valoracións numéricas iguais, obtense unha ordenación débil estrita. Esixir que dúas valoracións estean separadas por un limiar fixo antes de poder comparalas leva ao concepto de semiorde, mentres que permitir que o limiar varíe por elemento produce unha orde por intervalos.

Unha propiedade adicional simple e útil leva ao chamado ben-fundada, paraa que todos os subconxuntos non baleiros teñen un elemento minimal. Xeneralizando unha ben-orde pasando de orde linear a orde parcial, temos que un conxunto está ben parcialmente ordenado se todos os seus subconxuntos non baleiros teñen un número finito de elementos minimais.

Moitos outros tipos de orde xorden cando se garante a existencia de ínfima e supremo de determinados conxuntos. Centrándose neste aspecto, xeralmente denominado completitude de orde, obtense:

• Posets limitados, é dicir, posets cun elemento mínimo e maior (que son exactamente o supremo e o ínfimo do subconxunto baleiro),
• Retículas nas que todo conxunto finito non baleiro ten un supremo e un ínfimo,
• Retículas completas , onde cada conxunto ten un ínfimo e supremo,
• Ordes parciais completas dirixidas (dcpos), que garanten a existencia de supremo de todos os subconxuntos dirixidos e que se estudan na teoría de dominios.
• As ordes parciais con complementos, ou conxuntos poc, son posets cun único elemento inferior 0, así como unha involución inversa de orde $*$ tal que $a\leq a^{*}\implies a=0.$

No entanto, pódese ir aínda máis lonxe: se existen todos os ínfimos finitos non baleiros, entón ∧ pódese ver como unha operación binaria total no sentido de álxebra universal. Polo tanto, nunha retícula, están dispoñibles dúas operacións ∧ e ∨, e pódense definir novas propiedades dando identidades, como

x ∧ ( y ∨ z ) = ( x ∧ e ) ∨ ( x ∧ z ), para tódolos x, y e z.

Esta condición chámase distributividade e dá lugar a retículas distributivas. Hai algunhas outras leis importantes de distributividade que se comentan no artigo sobre a distributividade na teoría da orde. Algunhas estruturas de orde adicionais que adoitan especificarse mediante operacións alxébricas e definir identidades son

• Álxebras de Heyting e
• Álxebras de Boole,

onde ambas as dúas introducen unha nova operación ~ chamada negación. Ambas as dúas estruturas xogan un papel na lóxica matemática e especialmente as álxebras de Bool teñen importantes aplicacións en informática. Finalmente, varias estruturas en matemáticas combinan orde con operacións aínda máis alxébricas, como no caso dos cuánticos, que permiten definir unha operación de suma.

Un poset é localmente finito se cada intervalo pechado [a, b] nel é finito. Os posets localmente finitos dan lugar a álxebras de incidencia que á súa vez poden usarse para definir a característica de Euler dos posets finitos.

Subconxuntos de conxuntos ordenados

Nun conxunto ordenado, pódense definir moitos tipos de subconxuntos especiais en función da orde dada. Un exemplo sinxelo son os conxuntos superiores; é dicir, conxuntos que conteñen todos os elementos que están por riba deles na orde. Formalmente, o pechamento superior dun conxunto S nun poset P vén dado polo conxunto {x en P | hai algún y en S con y ≤ x}. Un conxunto que é igual ao seu pechamento superior chámase conxunto superior. Os conxuntos inferiores defínense dualmente.

Subconxuntos inferiores máis complicados son os ideais , que teñen a propiedade adicional de que cada dous dos seus elementos teñen un elemento maiorante dentro do ideal. O seu dual ven dado por filtros. Un concepto relacionado é o dun conxunto dirixido, que como un ideal contén elementos maiorantes de subconxuntos finitos, mais non ten que ser un conxunto inferior. A maiores, adoita xeneralizarse a conxuntos preordenados.

Un subconxunto que está ordenado linerlmente, chámase cadea. A noción oposta, a anticadea, é un subconxunto que non contén dous elementos comparables; é dicir, que é unha orde discreta.

Áreas matemáticas relacionadas

Álxebra universal

Un exemplo é a correspondencia entre as álxebras de Boole e os aneis booleanos. Outras cuestións están relacionadas coa existencia de construcións libres, como as retículas libre baseadas nun determinado conxunto de xeradores. Ademais, os operadores de pechamento son importantes no estudo da álxebra universal.

Topoloxía

En topoloxía, as ordes xogan un papel moi destacado. De feito, a colección de conxuntos abertos proporciona un exemplo clásico dunha retícula completa, máis precisamente unha álxebra de Heyting completa (ou "marco"). Os filtros e as redes son nocións moi relacionadas coa teoría da orde e o operador de pechamento de conxuntos pódese usar para definir unha topoloxía.

Como contrapartida, na teoría da orde, adoita facer uso de resultados topolóxicos. Existen varias formas de definir subconxuntos dunha orde que se poden considerar como conxuntos abertos dunha topoloxía. Considerando topoloxías nun poset (X, ≤) que á súa vez inducen ≤ como a súa orde de especialización, a topoloxía máis fina é a topoloxía de Alexandrov, que se dá tomando todos os conxuntos superiores como abertos. Pola contra, a topoloxía máis grosa que induce a orde de especialización é a topoloxía superior, tendo os complementos dos ideais principais (é dicir, conxuntos da forma {y en X | y ≤ x} para algúns x) como subbase. Ademais, unha topoloxía con orde de especialización ≤ pode ser consistente na orde, o que significa que os seus conxuntos abertos son "inaccesibles por supremos dirixido" (en relación a ≤). A topoloxía coherente de orde máis fina é a topoloxía de Scott, que é máis grosa que a topoloxía Alexandrov. Unha terceira topoloxía importante neste senso é a topoloxía de Lawson. Existen conexións estreitas entre estas topoloxías e os conceptos da teoría da orde. Por exemplo, unha función conserva o supremo dirixido se e só se é una función continua con respecto á topoloxía de Scott (por este motivo esta propiedade teórica da orde tamén se chama Scott-continuidade).

Teoría de categorías

A visualización dunha orde con diagramas de Hasse pode mostrarse coma un grafo. Deste xeito, cada orde é visa como equivalente a un grafo acíclico dirixido, onde os nós son os elementos do poset e hai un camiño dirixido de a a b se e só se a ≤ b. Eliminando o requisito de ser acíclico, tamén se poden obter todos as preordes.

Cando están equipados con todas as arestas transitivas, estes grafos á súa vez son só categorías especiais, onde os elementos son obxectos e cada conxunto de morfismos entre dous elementos é como máximo singleton. As funcións entre ordes convértense en functores entre categorías. Moitas ideas da teoría da orde son só conceptos da teoría de categorías en pequeno. Por exemplo, un ínfimo é só un produto categórico. De forma máis xeral, pódese recoller a noción de ínfimo e supremo baixo a noción abstracta dun límite categórico (ou colímite, respectivamente). Outro lugar onde se producen ideas categóricas é o concepto de conexión de Galois (monótona), que é o mesmo que un par de functores adxuntos.

Esta liña de investigación leva a varios teoremas de representación, a miúdo recollidos baixo a etiqueta de dualidade de Stone .

Véxase tamén

Bibliografía

• Birkhoff, Garrett (1940). Lattice Theory 25 (3rd Revised ed.). American Mathematical Society. ISBN 978-0-8218-1025-5. 
• Burris, S. N.; Sankappanavar, H. P. (1981). A Course in Universal Algebra. Springer. ISBN 978-0-387-90578-5. 
• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 0-521-78451-4. 
• Gierz, G.; Hofmann, K. H.; Keimel, K.; Mislove, M.; Scott, D. S. (2003). Continuous Lattices and Domains. Encyclopedia of Mathematics and its Applications 93. Cambridge University Press. ISBN 978-0-521-80338-0. 

Ligazóns externas

• Orders at ProvenMath partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory.
• Nagel, Felix (2013). Set Theory and Topology. An Introduction to the Foundations of Analysis