Severa malforta ordo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
13 eblaj severaj malfortaj ordoj sur aro de tri eroj {a, b, c}. La partordoj estas ruĝaj, tutecaj ordoj estas nigraj. Du ordoj estas montrita kiel koneksa per streko se ili diferenciĝas per la ekzisto aŭ foresto de sola paro de rilatoj difinantaj la ordojn.

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

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

La rilato "nek a<b nek b<a" estas estas tiam ekvivalentrilato, la nekomparebleca rilato. Eroj de S estas dispartigitaj per ĉi tiu nekomparebleca rilato en ekvivalentklasoj, en ĉiu el la ekvivalentklasoj estas eroj de S kiuj ne estas ordigitaj inter si per la < en ĉiu unu ekvivalentklaso. Kaj tiam estas tuteca ordo inter la ekvivalentklasoj.

Propraĵoj[redakti | redakti fonton]

Severa 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]

Severaj malfortaj ordoj estas proksime rilatantaj al tutecaj antaŭordigojne-severaj malfortaj ordoj. Ĉiu koncepto kiu povas esti priskribita per severa 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 \lesssim havas jenajn propraĵojn:

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

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

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

Por severa malforta ordo "<" alia asociita refleksiva rilato estas ĝia refleksiva fermaĵo, (ne-severa) 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 \lesssim b kaj b \lesssim a,
  • en la (ne-severa) parta ordo nek a ≤ b nek b ≤ a.

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

En ĉiu antaŭordigo estas respektiva ekvivalentrilato kie du eroj x kaj y estas ekvivalentaj' se x \lesssim y kaj y \lesssim 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 severa 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 severan malfortan ordon sur X kiel:

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

La asociita tuteca antaŭordigo estas

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

La asociita ekvivalenteco estas

a \sim 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 severe 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 severaj 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 severa malforta ordo "<", kaj f funkcio de X al Y, tiam f generas severa malfortan ordon sur X kiel:

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

La asociita tuteca antaŭordigo estas

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

La asociita ekvivalenteco estas

a \sim b se kaj nur se f(a) \sim 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)

Severa tuteca ordo[redakti | redakti fonton]

Severa malforta ordo kiu estas trivarianta rilato (por ĉiuj x kaj y en X, veras akurate unu el x<y, y<x, x=y) estas severa 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 severaj 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 severaj 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