En matematiko, aparte orda teorio, partordo (ankaŭ potaro) formaligas kaj ĝeneraligas la intuician koncepton de mendado, sekvencante, aŭ aranĝon de la elementoj de aro.
Potaro konsistas el aro kune kun duargumenta rilato indikante ke, por certaj paroj de elementoj en la aro, unu el la elementoj antaŭas la alian en la mendado.
La vorto "parta" en la nomoj "parta ordo" aŭ "partordo" estas utiligita kiel indiko ke ne ĉiu paro de elementoj bezonas estu komparebla.
Tio estas, povas ekzisti paroj de elementoj por kiuj nek elemento antaŭas la alian en la potaro.
Partaj ordoj tiel ĝeneraligas tutecajn ordojn, en kiuj ĉiu paro estas komparebla.
#000001
Por esti parta ordo, duargumenta rilato devas esti refleksiva (ĉiu elemento estas komparebla al si mem), kontraŭsimetria (neniuj du malsamaj elementoj antaŭas unu la alian), kaj transitivaj (la komenco de ĉeno de prioritatrilatoj devas antaŭi la finon de la ĉeno).
#000002
Unu konata ekzemplo de partordo estas kolekto de homoj ordonitaj per genealogia descendancy.
Kelkaj paroj de homoj portas la posteul-prapatran rilaton, sed aliaj paroj de homoj estas unikaj, kie nek estas epigono de la aliaj.
#000003
Potaro povas esti bildigita tra sia Hasse-diagramo, kiu prezentas la mendantan rilaton.
#000004
1 Akuta kaj malakuta ordo
#000006
(Ne-strikta) parta ordo [2] estas duargumentrilata ≤ super aro P kontentiganta specialajn aksiomojn kiuj estas diskutitaj malsupre.
Kie ≤ b, ni diras ke estas rilatita al b.
(Tio ne implicas ke b ankaŭ estas al , ĉar la rilato ne devas esti simetria.
#000007
La aksiomoj por ne-strikta parta ordo deklaras ke la rilat≤ estas refleksiva, kontraŭsimetria, kaj transitiva.
Tio estas, por ĉio , b, kaj c en P, ĝi devas kontentigi:
#000008
≤ ( refleksiveco: ĉiu elemento estas rilatita al si mem).
se ≤ b kaj b ≤ , tiam = b ( kontraŭsimetrio: du apartaj elementoj ne povas esti rilataj en ambaŭ indikoj).
se ≤ b kaj b ≤ c, tiam ≤ c ( transitiveco: se unua elemento estas rilatita al dua elemento, kaj, en victurno, ke elemento estas rilatita al tria elemento, tiam la unua elemento estas rilatita al la tria elemento).
#000009
En aliaj vortoj, parta ordo estas kontraŭsimetria preordo.
#000010
Aro kun parta ordo estas nomita partordo (ankaŭ vokis potaron).
La esprimo ordigita aro foje estas ankaŭ uzita, tiel longe kiel ĝi estas klara de la kunteksto kiun tiel neniu alia speco de ordo estas signifita.
Aparte, totale ordonis ke aroj ankaŭ povas esti referitaj kiel "ordigitaj aroj", precipe en lokoj kie tiuj strukturoj estas pli oftaj ol potaroj.
#000011
Por , b, elementoj de partordo P, se ≤ b aŭ b ≤ , tiam a kaj b estas kompareblaj .
Parta ordo sub kiu ĉiu paro de elementoj estas komparebla estas nomita tuteca ordo aŭ linia ordo;
komplete ordigita aro ankaŭ estas nomita ĉeno (ekz., la naturaj nombroj kun ilia normordo).
Elemento laŭdire estas kovrita per alia elemento b, skribita
<: b, se estas strikte malpli ol b kaj neniu tria elemento c konvenas inter ili;
formale: se kaj ≤ b kaj ≠ b estas veraj, kaj ≤ c ≤ b estas falsaj por ĉiu c kun ≠ c ≠ b.
Pli konciza difino estos donita sub uzado de la strikta ordo egalrilatanta al" ≤".
#000012
Normekzemploj de potaroj ekestantaj en matematiko inkludas:
#000013
Ekzistas pluraj nocioj de "plej granda" kaj "malplej" elemento en potaro P, precipe:
#000015
Ekzemple, pripensas la pozitivajn entjerojn, ordonitajn per dividebleco: 1 estas malplej elemento, ĉar ĝi disigas ĉiujn aliajn elementojn;
aliflanke tiu potaro ne havas plej grandan elementon (kvankam se oni inkludus 0 en la potaro, kio estas multoblo de iu entjero, kiu estus plej granda elemento;
Tio partordo ne eĉ havas iujn ajn maksimumajn elementojn, ĉar ĉiu g disigas ekzemple 2g, kiu estas aparta de ĝi, tiel ke g ne estas maksimuma.
Se la numero 1 estas ekskludita, konservante divideblecon kiel ordigante sur la elementoj pli granda ol 1, tiam la rezulta potaro ne havas malplej elementon, sed ĉiu primo estas minimuma elemento por ĝi.
, kiu ne havas ajnan pli malaltan liganta (ĉar 1 ne estas en la potaro);
aliflanke 2 estas pli malalta saltego de la subaro de potencoj de 2, kiu ne havas ajnan supran bound.
#000017
Ordoj sur la karteza produkto de partordojn
#000018
En ordo de kreskanta forto, t.e., malpliigi arojn de paroj, tri el la eblaj partaj ordoj sur la karteza produkto de du partordoj estu (vidu figurojn):
#000019
la leksikografa ordo: (, b
la refleksiva fino de la rekta produkto de la ekvivalentaj striktaj ordoj: (, b
#000020
Ĉiuj tri povas simile esti difinitaj por la karteza produkto de pli ol du aroj.
#000021
Aplikite al ordigitaj vektoraj spacoj super la sama kampo, la rezulto estas en ĉiu kazo ankaŭ ordigita vektora spaco.
#000022
Vidu ankaŭ ordoj sur la karteza produkto de komplete ordigitaj aroj.
#000023
Alia maniero kombini du potarojn estas la orda sumo [3] (aŭ linia sumo [4] ), Z = X ⊕ Y, difinita sur la unio de la subestaj aroj X kaj Y fare de la ordo al ≤ Z b se kaj nur se:
#000024
Se du potaroj estas bonordaj, tiam tiel estas sia orda sumo.
La orda sumo operacio estas unu el du operacioj uzitaj por formi seri-paralelajn partajn ordojn, kaj en tiu kunteksto estas nomita seriokonsisto.
La alia operacio kutimis formi tiujn ordojn, la disan union de du partordojn (kun neniu ordrilato inter elementoj de unu aro kaj elementoj de la alia aro) estas vokita en tiu kunteksta paralela kunmetaĵo.
#000025
Striktaj kaj ne-striktaj partaj ordoj
#000026
En kelkaj kuntekstoj, la parta ordo difinis supre estas nomita ne-strikta (aŭ refleksiva, aŭ malforta) parta ordo.
En tiuj kuntekstoj, strikta (aŭ irefleksive) parta ordo "<" estas duargumenta rilato kiu estas irefleksive, transitiva kaj malsimetria, t.e. kiu kontentigas por ĉio , b, kaj c en P:
#000027
se < b tiam ne b< (malsimetrio;
implicite per irefleksiveco kaj transitiveco [6] ).
#000028
Striktaj kaj ne-striktaj partaj ordoj estas parencaj.
Ne-strikta parta ordo povas esti konvertita al strikta parta ordo forigante ĉiujn rilatojn de la formo ≤ .
Inverse, strikta parta ordo povas esti konvertita al strikta parta ordo tuŝante ĉiujn rilatojn de tiu formo.
Tiel, se" ≤ "estas ne-strikta parta ordo, tiam la ekvivalenta strikta parta ordo"<" estas la irefleksive-kerno donita per:
#000029
Inverse, se"< "estas strikta parta ordo, tiam la ekvivalenta ne-strikta parta ordo-" ≤" estas la refleksiva fino donita per:
#000030
Tio estas la kialo de uzado de la notacio-" ≤".
#000031
Uzante la striktan ordon"<", la rilato " estas kovrita per b " povas esti ekvivalente revortigita kiel "
Striktaj partaj ordoj estas utilaj ĉar ili egalrilatas pli rekte al direktitaj aciklaj kurvoj (pendotufoj): ĉiu strikta parta ordo estas pendotufo, kaj la transitiva fino de pendotufo estas kaj strikta parta ordo kaj ankaŭ pendotufo mem.
#000032
La inversa aŭ inversa ≥ de parta ordrilat≤ kontentigas x ≥ y se kaj nur se y ≤ x.
La inversa de parta ordrilato estas refleksiva, transitiva, kaj kontraŭsimetria, kaj tial sin parta ordrilato.
La orddualo de partordo estas la sama aro kun la parta ordrilato anstataŭigita per ĝia inversa.
La irefleksive kiun rilato> estas al ≥ kiel< estas al ≤.
#000033
Ĉiu el la kvar rilat≤,<, ≥, kaj> sur antaŭfiksita aktoraro unike determinas la aliajn tri.
#000034
Ĝenerale du elementoj x kaj y de parta ordo povas stari en iuj da kvar reciproke ekskluzivaj rilatoj al unu la alian: aŭ x < y, aŭ x = y, aŭ x > y, aŭ x kaj y estas unikaj (neniu el la aliaj tri).
Komplete ordigita aro estas unu kiu ekskludas tiun kvaran eblecon: ĉiuj paroj de elementoj estas kompareblaj kaj ni tiam diru ke trikotomio tenas.
La naturaj nombroj, la entjeroj, la rationals, kaj la realoj estas ĉio komplete ordigis memstare algebra (subskribita) magnitudo dum la kompleksaj nombroj ne estas.
Tio estas ne diri ke la kompleksaj nombroj ne povas esti totale ordonitaj;
Ordigi ilin de absoluta magnitudo donas preordon en kiu ĉiuj paroj estas kompareblaj, sed tio ne estas parta ordo ekde 1 kaj mi havas la saman absolutan magnitudon sed ne estas egalaj, malobservante kontraŭsimetrion.
#000035
Ekzemple, mapa f: N → P (N) de la aro de naturaj nombroj (ordonitaj de dividebleco) al la aro de ĉiuj subaroj de naturaj nombroj (ordonitaj per arinkludo) povas esti difinita prenante ĉiun nombron al la aro de ĝiaj ĉefaj dividantoj.
Ĝi estas ord-marinada: se x dislimoj y, tiam ĉiu ĉefa dividanto de x ankaŭ estas ĉefa dividanto de y.
nek ordo-reflektado (ekde krom 12 ne disigas 6).
Preni anstataŭe ĉiun nombron al la aro de ĝiaj ĉefaj potenc dividantoj difinas mapon g: da N → P (N) kiu estas ord-marinada, ord-reflektante, kaj tial ordo-enkonstruadon.
, sed ĝi povas fariĝi unu limigante it kodomajnon al g (N).
La dekstra bildo montras subaron de N kaj sian izomorfan bildon malpli ol g.
La konstruado de tia ordo-izomorfio en aron de ĉiuj subarojn povas esti ĝeneraligita al larĝa klaso de partaj ordoj, nomitaj distribukadroj, vidi " la reprezentantarteoremon de Birkhoff ".
#000037
Sekvenco A001035 en OEIS donas la nombron da partaj ordoj sur aktoraro de n etikeditaj elementoj:
#000038
La nombro da striktaj partaj ordoj estas la sama kiel tiu de partaj ordoj.
#000039
Se la kalkulo fariĝas nur supren al izomorfio, la seqeuence 1, 1, 2, 5, 16, 63, 318, ...
(sekvenco A000112 en la OEIS) akiriĝas.
#000040
Parta ord≤ ÷ sur aktoraro X estas etendaĵo de alia parta ord≤ sur X kondiĉe ke por ĉiu elementoj x kaj y de X, kiam ajn x ≤ y, ĝi ankaŭ estas la kazo tiu x ≤ ÷ y.
Linia etendaĵo estas etendaĵo kiu ankaŭ estas linia (t.e., totala) ordo.
Ĉiu parta ordo povas esti ampleksita tutecan ordon ( ord-etendaĵa principo).
#000041
En komputado, algoritmoj por trovado de liniaj etendaĵoj de partaj ordoj (reprezentitaj kiel la atingeblo ordoj de direktitaj aciklaj kurvoj) estas nomitaj topologia ordigo.
#000042
Ĉiu potaro (kaj ĉiu preordo) povas esti konsiderita kategorion en kiu ĉiu hom-aro havas maksimume unu elementon.
Pli eksplicite, lasis hom ( x, y
se x ≤ y (kaj alie la malplena aro) kaj ( y, z) ∘ ( x, y
Tiaj kategorioj foje estas nomitaj posetaj.
#000043
Posets estas ekvivalenta unu al la alia se kaj nur se ili estas izomorfaj.
En potaro, la plej malgranda elemento, se ĝi ekzistas, estas komenca objekto, kaj la plej granda elemento, se ĝi ekzistas, estas fina objekto.
Ankaŭ, ĉiu preordigita aro estas ekvivalenta al potaro.
Finfine, ĉiu subkategorio de potaro estas izomorfi-fermita.
#000044
Partaj ordoj en topologiaj spacoj
#000045
Por ≤ b, la fermita intervalo [, b] estas la aro de elementoj x kontentigante ≤ x ≤ b (t.e. ≤ x kaj x ≤ b).
Ĝi minimume enhavas la elementojn a kaj b.
#000046
Malferma intervalo povas esti malplena eĉ se < b.
Ekzemple, la malferma intervalo (1,2) sur la entjeroj estas malplena ĉar ekzistas neniuj entjeroj mi tia ke 1< mi < 2.
#000047
Foje la difinoj estas etenditaj por permesi > b, en kiu kazo la intervalo estas malplena.
#000048
La duone malfermitaj intervaloj [, b) kaj (, b] estas difinitaj simile.
#000049
Potaro estas loke finhava se ĉiu intervalo estas finhava.
Ekzemple, la entjeroj estas loke finhavaj sub sia natura mendado.
La leksikografa ordo sur la karteza produktoN×N ne estas loke finhava, ekde ekz. (1,2) ≤ (1,3) ≤ (1,4) ≤ (1,5) ≤ ...
Utiligante la intervalnotacion, la posedaĵo " estas kovrita per b " povas esti revortigita ekvivalente kiel [, b
#000050
Tiu koncepto de intervalo en parta sinsekvo ne devus esti konfuzita kun la akurata klaso de partaj ordoj konataj kiel la intervalordoj.
#000051
antimatroida, formaligo de mendadoj sur aktoraro kiu permesas pli ĝeneralajn familiojn de mendadoj ol potaroj
Funkcio de Möbius sur potaroj
potartopologio, speco de topologia spaco kiu povas esti difinita de iu potaro
Scott-kontinueco - kontinueco de funkcio inter du partaj ordoj.
#000052
A001035: Nombro da potaroj kun n etikedis elementojn en la OEIS
A000112: Nombro da potaroj kun n unlabelis elementojn en la OEIS
#000055
Partordo estas rilato, kiu estas refleksiva, transitiva kaj malsimetria.
#000056
Akuta ordo estas refleksiva, transitiva kaj malsimetria rilato kaj malakuta estas kontraŭrefleksiva, kaj transitiva (kontraŭrefleksiva kaj transitiva estas samtempe malsimetria) rilato.
#000057
Se per oni signifis malakutan partordon en aro . Tiam rilato en estas difinata per:
#000058
Foje oni estas uzata samtempe akutan kaj malakutan ordon, do por malakuta ordo oni uzas por akuta .
#000059
La aro de naturaj nombroj ekipita kun la malpli granda ol aŭ egala al rilato.
La aro de naturaj nombroj ekipita kun la dividebleca rilato.
La aro de subaroj de donita aro (aro de ĉiuj subaroj) ordigita per inkluziveco.
#000060