Teoria de l'orde

Archiu:Lattice of the divisibility of 60.svg

Teoria de l'orde

Plantilla:Relació binaria 101 La teoria de l'orde és una branca de la matemàtica que estudia vàries classes de relacions binarias que capturen la noció intuïtiva de l'orde matemàtic. Este artícul proveïx una introducció detallada a este camp i inclou algunes de les definicions bàsiques. Per a una ràpida busca d'un terme orde teòric, hi ha també un glossari de teoria de l'orde. Una llista d'assunts sobre orde arreplega els artículs que existixen en relació en esta teoria

Trasfondo i motivació

L'orde apareix en tots els llocs, per lo manco si es tracta de matemàtiques i àrees relacionades, tals com l'informàtica. El primer orde que un típicament troba en l'educació matemàtica de l'escola primària és l'orde ≤ dels número natural. Este concepte intuïtiu és fàcilment estés a atres conjunts de números, tal com els sancers i reals. De fet l'idea de ser major o menor que un atre número és una de les intuïcions bàsiques dels sistemes de numeració en general (que un generalment s'interessa també en la diferència real de dos números, que no ve donada per l'orde). Un atre eixemple popular d'un orde és l'orde lexicogràfic de les paraules en un diccionari.

Els tipos antedichos d'orde tenen una propietat especial: cada element es pot comparar en qualsevol atre element, és dir és o major, o menor, o igual. No obstant, açò no sempre és un requisit desijable. Un eixemple ben conegut és l'orde dels subconjunts d'un conjunt. Si un conjunt conté els elements de cert un atre conjunt, llavors es pot dir que és major o igual. En tot, hi ha conjunts que poden no ser comparables d'esta manera, ya que cada u pot contindre algun element que no estiga present en l'atre. Per lo tant, inclusió de subconjunts és un orde parcial, en comparació als órdens totals donats abans.

Encorajades pels amplis usos pràctics dels órdens, es poden definir numeroses classes especials de conjunts ordenats, algunes de les quals han aplegat a ser camps matemàtics per sí mateixos. Ademés, la teoria de l'orde no es restringix a les vàries classes de relacions d'orde, sino que també considera funcions apropiades entre elles. Un eixemple simple d'una propietat orde teòrica ve del anàlisis a on trobem en freqüència a les funcions monòtones.

Introducció a les definicions bàsiques

Esta secció té com a objectiu donar una primera guia al regne dels conjunts ordenats. Està dirigida al llector que té un coneiximent bàsic teoria de conjunts i aritmètica i que sap qué és una relació binaria, pero que no està familiarizado, fins ara, en consideracions teòriques sobre orde.

Conjunts parcialment ordenats

Com ya es va fer alusió dalt, un orde és una relació binaria especial. Per lo tant considerem algun conjunt P i una relació binaria ≤ en P. Llavors ≤ és un orde parcial si és reflexiva, antisimètrica, i transitiva, és dir, per a tot a, b i c en P, tenim que:

a ≤ a (reflexividad)

si a ≤ b i b ≤ c llavors a ≤ c (transitividad)

si a ≤ b i b ≤ a llavors a = b, (antisimetría).

Un conjunt en un orde parcial es diu conjunt parcialment ordenat, o, en breu, poset (del anglés partially ordered set). El terme conjunt ordenat a voltes també s'utilisa per als posets, mentres estiga clar del context que no es vol significar cap atra classe d'órdens. Comprovant esta propietat, es veu immediatament que els ben coneguts órdens dels naturals, sancers, racionals i reals són tots órdens en el antedicho sentit. No obstant, tenen la propietat adicional de ser total, és dir, per a tot a, b en X

a ≤ b o b ≤ a (totalitat)

este orde es pot també cridar orde llineal o cadena. mentres que molts órdens clàssics són llineals, l'orde entre subconjunts d'un conjunt proporciona un eixemple a on este no és el cas. De fet, moltes propietats alvançades dels posets són interessants principalment per a un orde no llineal.

Visualisant órdens

Abans de procedir en més eixemples i definicions, serà profitós poder exhibir un orde d'una manera gràfica convenient, per a proporcionar un "quadro" que un puga tindre en ment (o en paper) quan s'intente accedir a conceptes més abstractes. Per a este propòsit s'han introduïts els, aixina cridats, diagrames de Hasse. Estos són grafos a on els vèrtiços són els elements del poset i la relació d'orde està indicada per les arestes i la posició relativa dels vèrtiços. Els órdens es dibuixen d'avall cap a dalt: si un element x és menor que i llavors existix una trayectòria de x fins a i que es dirigix cap a dalt. A sovint és necessari que la conexió entre punts es intersequen, pero els punts mai deuen ser situats en conexió directa entre atres dos punts.

Encara els conjunts infinits poden a voltes ser ilustrats per diagrames similars, usant punts suspensivos (...) despuix de dibuixar un suborden finito que siga lo suficientment instructivo. Açò funciona be per als número natural, pero falla per als reals, a on no existix l'immediat successor. No obstant, freqüentment s'obté una intuïció relacionada en diagrames d'este tipo.

Tots els órdens antedichos són molt comuns en matemàtica, no obstant hi ha també eixemples que un no considera a sovint com a órdens. Per eixemple, la relació d'identitat "=" en un conjunt és un orde parcial. Dins d'este orde, qualssevol dos (i.i. distints) elements són incomparables. És també l'única relació que és un orde parcial i una relació d'equivalència. El diagrama de Hasse de tal orde discret és solament una colecció de punts etiquetats, sense cap aresta entre ells.

Un atre eixemple ve dau per la relació de divisibilidad "|". Per a dos número natural n i m, escrivim n|m si n dividix a m sense restant. Un veu fàcilment que açò dona realment un orde parcial. Un eixercici instructivo és dibuixar el diagrama de Hasse per al conjunt dels número natural que són menors o iguals que, digam, 13, ordenats per |.

Elements especials dins d'un orde

En un conjunt parcialment ordenat hi ha alguns elements que eixerciten un paper especial. L'eixemple més bàsic està donat pel mínim d'un poset. Per eixemple, 1 és el mínim dels número natural i el conjunt buit és el mínim baix l'orde de subconjunts. Formalment, açò es pot descriure per la propietat:

0 ≤ a, per a tot element a del conjunt ordenat.

És freqüent trobar la notació 0 per al mínim, inclús quan no es referixca a números. No obstant, en un orde d'un conjunt numèric, esta notació pot ser inadequada o ambigua, ya que el número 0 no sempre és el mínim. Un eixemple és el antedicho orde de divisibilidad |, a on 1 és el mínim lloc que dividix a tot el restant de números. Per una atra part, 0 és un número que es dividix per tot el restant de números. ¡Per lo tant és el màxim de l'orde! Atres térmens freqüents per a estos elements són fondo i tapa o zero i un. Poden no existir els elements "mínim" o "màxim", com demostra l'eixemple dels número real. Per una atra part, si existixen són sempre únics. En contrast, considerem la relació de divisibilidad | en el conjunt {2, 3, 4, 5, 6}. Encara que este conjunt no té ni tapa ni fondo, els elements 2, 3, i 5 no tenen cap element davall, mentres que 4, 5, i 6 no tenen cap un atre número dalt. Tals elements es diuen minimales i maximales, respectivament. Formalment, un element m és minimal si:

a ≤ m implica a = m, per a tot element a.

Intercanviant ≤ en ≥ obtenim la definició de maximal. Com l'eixemple demostra, pot haver molts elements minimales o maximales i algun element pot ser maximal i minimal (i.g. 5 dalt). No obstant, si hi ha un element mínim, llavors és l'únic element minimal de l'orde. (Si se seguix estrictament la definició donada. Llamentablement hi ha una tradició matemàtica "a contrari": considerar els minimales i maximales en el conjunt despullat del seu màxim i el seu mínim, si els haver. Açò deu recordar-se. N.T.). Una volta més, en els posets no sempre hi ha infinits elements maximales - el conjunt de tots els subconjunts finitos en un conjunt infinit dau, ordenat per inclusió de subconjunts, proporciona un, entre molts, contraeixemple. Una ferramenta important per a assegurar l'existència d'elements maximales baixe certes condicions és el Lema de Zorn.

Els subconjunts d'un conjunt parcialment ordenat hereten l'orde. Ya apliquem açò en considerar el subconjunt {2, 3, 4, 5, 6} dels número natural en l'orde de divisibilidad induït. Hi ha també elements d'un poset que són especials sobre cert subconjunt de l'orde. Açò conduïx a la definició de cota superior. Donat un subconjunt S de cert poset P, una cota superior de S és un element b de P que està sobretot element de S. Formalment, açò significa que

s ≤ b, per a tot s en S.

Cota inferior es definix invertint l'orde. Per eixemple, -5 és una cota inferior dels número natural com a subconjunt dels sancers. Donat un conjunt de conjunts , una cota superior per a estos conjunts ve dau pel seu unió. De fet, esta cota superior és molt especial: és el més chicotet conjunt que conté tots els conjunts daus. Per lo tant, trobem la menor cota superior d'un conjunt de conjunts. Este concepte es diu també suprem i per a un conjunt S s'escriu sup S o VS per a la seua menor cota superior. Inversamente, la major cota inferior li la coneix com a ínfim i es denota inf S o ^S. Este concepte eixercita un paper important en molts usos de la teoria de l'orde. Per a dos elements x i i, un també escriu x v i i x ^ i per a sup{x, i} i inf{x, i}, respectivament.

Usant Wikipedia TeX markup, un pugues també escriure $\vee$ i $\wedge$, aixina com símbols grans $\bigvee$ i $\bigwedge$. Observe, no obstant, que tots eixos símbols poden no tindre símbol de tamany corresponent al de la font del text estàndar i, per tant, es preferix utilisar-los en llínees adicionals. Molts dels navegadors de hui són incapaços de representar ∨ per a v i ∧ para ^ en algunes plataformes, i per lo tant s'evita ací.

Considere un atre eixemple en la relació | per als número natural. La menor cota superior de dos números és el menor número que és múltiple d'abdós, és dir el mínim comú múltiple. Major cota inferior és, alternativament, el màxim comú divisor.

Dualitat

En les anteriors definicions, a sovint, observem que un concepte pot ser definit per invertir simplement l'orde en una definició anterior. Est és el cas per a "menor" i "major", per a "mínim" i "màxim", per a "cota superior " i "cota inferior", etcétera. Açò és una situació general en teoria d'orde: Un orde donat es pot invertir en solament intercanviar la seua direcció, pictóricamente donar regrés el diagrama de Hasse de dalt per a avall. Açò dona el, aixina cridat, orde dual, invers o opost.

Cada definició orde teòrica té el seu dual: és la noció que s'obté en aplicar la definició a l'orde invers. Donada la simetria de tots els conceptes, esta operació preserva les teoremes de l'orde parcial. Per a un resultat matemàtic dau, es pot, simplement, invertir l'orde i substituir tot definició pel seu dual i obtindre una atra teorema vàlida. Açò és important i útil, ya que un obté dos teoremes al preu d'un. Més detall i eixemples es poden trobar en l'artícul sobre dualitat en teoria d'orde.

Construcció nous órdens

Hi ha moltes maneres de construir órdens o de combinar órdens en un nou. L'orde dual és un primer eixemple. Una atra construcció important és el producte cartesiano de dos conjunts parcialment ordenats, junt en l'orde producte en parells d'elements. Açò es definix pels órdens originals fent (a, x) ≤ (b, i) si a ≤ b i x ≤ i. l'unió disjunta de dos conjunts parcialment ordenats és una atra construcció típica, a on l'orde és exactament l'unió dels órdens originals.

Com en el cas de l'orde usual de números, cada orde parcial ≤ dona lloc a un orde estricte <, en definir a < b si a ≤ b i no b ≤ a. Esta transformació pot ser invertida fent a ≤ b si a < b o a = b.

Referències

• Gierz, G., K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove i D. S. Scott, «Continuous Lattices and Domains.» En Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003. ISBN 0-521-80338-1