Strikta malforta ordo

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.

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.

(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 la origina rilato transformiĝas al strikta tuteca ordo inter la ekvivalentklasoj.

Ecoj

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)

Notu, 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

Striktaj malfortaj ordoj estas proksime rilatantaj al tutecaj antaŭordigoj aŭ malstriktaj 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 t.e. tuteca rilato, kio signifas, ke ne ekzistas du elementoj 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 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 $\lesssim$ kiel x $\lesssim$ y se kaj nur se ne y < x. En la alia direkto simile strikta malforta ordo < estas kreata surbaze de tuteca antaŭordigo $\lesssim$ kiel x < y se kaj nur se ne y $\lesssim$ x.

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

La du asociitaj 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 (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, en kiu du elementoj 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 elementoj 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

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

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 $\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 du ekvivalentaj elementoj de Y povas generi klason de 5 ekvivalentaj elementoj sur X. Ankaŭ f ne estas ne bezone surĵeto, tiel klaso de 2 ekvivalentaj elementoj de Y povas generi klason de nur unu elemento 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)

Strikta tuteca ordo

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

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

Por n-elementaj aroj, ĉi tiuj kvantoj estas ankaŭ nomataj nombroj de Fubini aŭ ordigitaj nombroj de Bell.

Kvanto de malsamaj tutecaj antaŭordigoj estas la sumo de kvantoj de tutecaj ordoj sur ĉiuj 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 elemento estas rilatanta al ĉiu elemento)
  • 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 elemento estas rilatanta al ĉiu elemento)
  • 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 elemento estas rilatanta al ĉiu elemento)
  • 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

• A000670 en OEIS - vico de kvantoj de malsamaj tutecaj antaŭordigoj de n-elementa aro