Strikta malforta ordo

El Vikipedio, la libera enciklopedio
(Alidirektita el Tuteca antaŭordigo)
La 13 eblaj striktaj malfortaj ordoj sur tri-elementa aro {a, b, c}. La partaj ordoj estas ruĝaj, tutecaj ordoj estas nigraj. Du ordoj estas montritaj kiel koneksa per streko se ili diferenciĝas per la ekzisto aŭ foresto de sola paro de rilatoj difinantaj la ordojn.

En matematiko, strikta malforta ordo estas duargumenta rilato < sur aro S, kiu estas strikta parta ordo tia, ke la rilato "nek a<b nek b<a" estas transitiva.

(Strikta parta ordo estas transitiva rilato, kiu estas malrefleksiva aŭ ekvivalente, kontraŭsimetria.)

La rilato "nek a<b nek b<a" estas tiam ekvivalentrilato, la nekomparebleca rilato. Elementoj de S estas dispartigitaj per ĉi tiu nekomparebleca rilato en ekvivalentklasoj, en ĉiu el la ekvivalentklasoj estas elementoj de S, kiuj ne estas ordigitaj inter si per la rilato < en ĉiu el la ekvivalentklasoj. Kaj tiam estas la origina rilato transformiĝas al strikta tuteca ordo inter la ekvivalentklasoj.

Ecoj[redakti | redakti fonton]

Strikta malforta ordo havas jenajn propraĵojn:

  • Por ĉiuj x, ne x < x - malrefleksiva rilato
  • Por ĉiuj x, y, x ≠ y, se x < y do ne y < x - kontraŭsimetria rilato
  • Por ĉiuj x, y, z, se x < y kaj y < z do x < z - transitiva rilato
  • Por ĉiuj x, y, z, se ne x < y kaj ne y < x (x estas nekomparebla kun y), kaj ne y < z kaj ne z < y (y estas nekomparebla kun z), do ne x < z kaj ne z < x (x estas nekomparebla kun z) - transitiveco de nekomparebleco (ekvivalenteco)

Noto ke malrefleksiveco sekvas el malrefleksiveco kaj transitiveco - se estus x < y kaj y < x, do laŭ la transitiveco estus x < x, kio ne povas esti pro la malrefleksiveco.

Transitiveco de nekomparebleco povas ankaŭ esti skribita kiel:

  • Se x < y, do por ĉiu z, x < zz < y (aŭ ambaŭ).

Ekzemplo[redakti | redakti fonton]

Estu aro de ordigitaj duopoj de reelaj nombroj (x, y). (Tio ke ĝi estas ordigita duopo signifas ke ĝenerale (x, y) ne estas la samo kiel (y, x).)

Estu (x1, y1) < (x2, y2) se kaj nur se x1 < x2.

Tiam (x1, y1) kaj (x2, y2) estas nekompareblaj se kaj nur se x1 = x2 kaj y1 ≠ y2.

Tuteca antaŭordigo[redakti | redakti fonton]

Striktaj malfortaj ordoj estas proksime rilatantaj al tutecaj antaŭordigojmalstriktaj malfortaj ordoj. Ĉiu koncepto kiu povas esti priskribita per strikta malforta ordo povas esti priskribita egale bone per tuteca antaŭordigo. Tuteca antaŭordigo estas antaŭordigo kio estas tuteca rilato; kio estas, ne ekzistas du eroj kiuj estas nekompareblaj.

Tuteca antaŭordigo havas jenajn propraĵojn:

  • Por ĉiuj x, y, z, se x y kaj y z do x z - transitiva rilato
  • Por ĉiuj x kaj y, x yy x - tuteca ordo

Tuteca ordo estas tuteca antaŭordigo kiu estas antisimetria rilato, aŭ ekvivalente kiu estas ankaŭ partordo.

La komplemento de strikta malforta ordo estas tuteca antaŭordigo kaj reen.

Ofte pli nature estas konsideri rilaton de strikta malforta ordoj kaj tuteca antaŭordigo kun la mala ordo de la argumentoj. Tiel oni prenu la inverson de la komplemento: por strikta malforta ordo < , krei tutecan antaŭordigon kiel x y se kaj nur se ne y < x. En la alia direkto simile strikta malforta ordo < estas kreata surbaze de tuteca antaŭordigo kiel x < y se kaj nur se ne y x.

Por strikta malforta ordo "<" alia asociita refleksiva rilato estas ĝia refleksiva fermaĵo, (ne-strikta) parta ordo "≤".

La du asociita refleksivaj rilatoj diferenciĝas je sia valoro por malsamaj a kaj b por kiuj nek a < b nek b < a:

  • en la tuteca antaŭordigo tiam a b kaj b a,
  • en la (malstrikta) parta ordo nek a ≤ b nek b ≤ a.

Por striktaj tutecaj ordoj ĉi tiuj du asociitaj refleksivaj rilatoj estas la sama, la respektiva (ne-strikta) tuteca ordo.

En ĉiu antaŭordigo estas respektiva ekvivalentrilato kie du eroj x kaj y estas ekvivalentaj' se x y kaj y x. Ĉe tuteca antaŭordigo la respektiva parta ordo sur la aro de ekvivalentklasoj estas tuteca ordo. Du eroj estas ekvivalentaj en tuteca antaŭordigo se kaj nur se ili estas nekompareblaj en la respektiva strikta malforta ordo.

Prezentado de malforta ordo per funkcio[redakti | redakti fonton]

Se X estas aro kaj f reelo-valora funkcio sur X tiam f generas striktan malfortan ordon sur X kiel:

a < b se kaj nur se f(a) < f(b)

La asociita tuteca antaŭordigo estas

a b se kaj nur se f(a) ≤ f(b)

La asociita ekvivalenteco estas

a b se kaj nur se f(a) = f(b)

La rilatoj ne ŝanĝiĝas se f estas anstataŭigita per funkcia komponaĵo g o f, kie g estas strikte pligrandiĝanta monotona funkcio reelo-valora funkcio difinis sur almenaŭ aro de valoroj de f.

Se X estas finia, ĉiu malforta ordo povas esti prezentita per funkcio tiamaniere. Tamen ekzistas struktaj malfortaj ordoj kiuj ne havas respektivan reelan funkcio. Ekzemple, ne ekzistas ĉi tia funkcio por la leksikografia ordo sur Rn.

Pli ĝenerale, se X estas aro, kaj Y estas aro kun strikta malforta ordo "<", kaj f funkcio de X al Y, tiam f generas strikta malfortan ordon sur X kiel:

a < b se kaj nur se f(a) < f(b)

La asociita tuteca antaŭordigo estas

a b se kaj nur se f(a) f(b)

La asociita ekvivalenteco estas

a b se kaj nur se f(a) f(b)

f ne estas ne bezone enĵeto, tiel ekzemple klaso de 2 ekvivalentaj eroj de Y povas generi klason de 5 ekvivalentaj eroj sur X. Ankaŭ f ne estas ne bezone surĵeto, tiel klaso de 2 ekvivalentaj eroj de Y povas generi klason de nur unu ero sur X, aŭ eĉe tute nenion. Estas respektiva enĵeto g kiu bildigas la dispartigon de X al tiu de Y. Tial, ĉe finiaj dispartigoj, la kvanto de klasoj en X estas malpli granda ol aŭ egala al kvanto de la klasoj en Y.

Ekzemploj[redakti | redakti fonton]

Sur la 2-dimensia reela ebeno:

  • f(x, y)= x+y
  • f(x, y)= min(x, y)

Strikta tuteca ordo[redakti | redakti fonton]

Strikta malforta ordo kiu estas trivarianta rilato (por ĉiuj x kaj y en X, veras akurate unu el x<y, y<x, x=y) estas strikta tuteca ordo. La tuteca antaŭordigo kiu estas la inverso de ĝia komplemento estas en ĉi tiu okazo tuteca ordo.

Kvanto de tutecaj antaŭordigoj kaj de striktaj malfortaj ordoj[redakti | redakti fonton]

Pro la 1 al 1 respektiveco, sur ĉiu aro kvanto de malsamaj tutecaj antaŭordigoj estas la sama kiel tiu de malsamaj strimtaj malfortaj ordoj.

Por n-eraj aroj ĉi tiuj kvantoj estas ankaŭ nomataj kiel nombroj de Fubiniordigitaj nombroj de Bell.

Kvanto de malsamaj tutecaj antaŭordigoj estas la sumo de kvantoj de tutecaj ordoj sur ĉiu dispartigoj de la aro. Ekzemple:

  • Por n=1 estas 1 tuteca antaŭordigo:
    • 1 dispartigo kiel 1, donanta 1 tutecan antaŭordigon
  • Por n=2 estas 3 tutecaj antaŭordigoj:
    • 1 dispartigo kiel 2, donanta 1 tutecan antaŭordigon (ĉiu ero estas rilatanta al ĉiu ero)
    • 1 dispartigo kiel 1+1, donanta 2! = 2 tutecajn antaŭordigojn (la tutecaj ordoj en la okazo)
  • Por n=3 estas 13 tutecaj antaŭordigoj:
    • 1 dispartigo kiel 3, donanta 1 tutecan antaŭordigon (ĉiu ero estas rilatanta al ĉiu ero)
    • 3 dispartigoj kiel 2+1, donanta 3 × 2! = 6 tutecajn antaŭordigojn
    • 1 dispartigo kiel 1+1+1, donanta 3! = 6 tutecajn antaŭordigoj (la tutecaj ordoj en la okazo)
  • Por n=3 estas 75 tutecaj antaŭordigoj:
    • 1 dispartigo kiel 4, donanta 1 tutecan antaŭordigon (ĉiu ero estas rilatanta al ĉiu ero)
    • 7 dispartigoj kun du klasoj (4 de 3+1 kaj 3 de 2+2), donanta 7 × 2! = 14 tutecajn antaŭordigojn
    • 6 dispartigoj kiel 2+1+1, donanta 6 × 3! = 36 tutecajn antaŭordigojn
    • 1 dispartigo kiel 1+1+1+1, donanta 4! = 24 tutecajn antaŭordigojn (la tutecaj ordoj en la okazo)

Ĉi tie k! estas faktorialo.

Eksteraj ligiloj[redakti | redakti fonton]

  • A000670 en OEIS - vico de kvantoj de malsamaj tuteca antaŭordigoj de n-era aro