Strikta malforta ordo

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

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 < z aŭ z < y (aŭ ambaŭ).

Ekzemplo

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 (x₁, y₁) < (x₂, y₂) se kaj nur se x₁ < x₂.

Tiam (x₁, y₁) kaj (x₂, y₂) estas nekompareblaj se kaj nur se x₁ = x₂ kaj y₁ ≠ y₂.

Tuteca antaŭordigo

Severaj malfortaj ordoj estas proksime rilatantaj al tutecaj antaŭordigoj aŭ ne-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:

• Por ĉiuj x, y, z, se x $\lesssim$ y kaj y $\lesssim$ z do x $\lesssim$ z - transitiva rilato
• Por ĉiuj x kaj y, x $\lesssim$ y aŭ y $\lesssim$ x - tuteca ordo
  • Do, por ĉiu x, x $\lesssim$ x - refleksiva rilato

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

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 Rⁿ.

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

Sur la 2-dimensia reela ebeno:

• f(x, y)= x+y

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

Severa tuteca ordo

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

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 Fubini aŭ ordigitaj 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

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