Részbenrendezett halmazok, megfordítási képletek

Részbenrendezett halmazok, megfordítási képletek A logikai szita az A_I metszethalmazok és a A₁^ß₁ n A₂^ß₂ n A₃^ß₃ n ...n A_n^ß_n alakú halmazok (elemi halmazok) elemszámai közötti kapcsolat. Minden metszethalmaz diszjunkt elemi halmazok uniójaként áll elõ, így az egyik irányú kapcsolat a két elemszám összesség között nyilvánvaló. A logikai szita ezt a nyilvánvaló összefüggést fordíja meg, azaz egy megfordítási képlet.

A metszetek között és elemi részek között is egy-egy természetes részbenrendezés van. Mindkét részbenrendezés izomorf az [n] halmaz részhalmazainak a tartalmazásra vett részbenrendezett halmazával. Másképpen a metszet elemszámok és az elemi részek elemszámai is felfoghatók úgy, mint a P([n]) halmaz elmeihez rendelt számok. Azaz a metszetelemszámok egy m:P([n]) -> Z függvény, amely az [n] halmaz I részhalmazához az |A_S-I| metszetelmeszámot rendeljük. Míg az elemi részek elemszámai egy e:P([n]) -> Z függvény, amely az [n] halmaz I részhalmazához az A₁^ß₁ n A₂^ß₂ n A₃^ß₃ n ...n A_n^ß_n elemi rész elemszámát rendeljük, ahol ß_i=-1 akkor és csak akkor teljesül, ha i eleme az I halmaznak (más esetben ß_i=1).

Könnyû belátni, hogy az m(I) érték azon e(J) értékek összege, ahol J az I halmaz részhalmazain fut keresztül. A szita formula az e(I) értéket fejezi ki az m(J) függvényértékek (metszetelemszámok) lineáris kombinációjaként, ahol az együtthatók a szitából kiolvasható módon -1,0 vagy 1. Ezt az interpretációt könnyen általánosíthatjuk.

Legyen (P,<₌) egy részbenrendezett halmaz. Legyen f:P -> R egy a részbenrendezett halmaz alaphalmazán értelmezett valós függvény. Legyen f^ az a részbenrendezett halmaz alaphalmazán értelmezett valós függvény, amely egy p elemhez azon f(q) függvényértékek összegét rendelei, amelyekre q<₌ p. Célunk, hogy belássuk f^ ismeretében f kiszámolható.

Lemma: Legyen (P,<₌) egy véges (véges alaphalmazú) részbenrendezett halmaz. Ekkor P-nek van olyan sorbarendezése, amelyre teljesül, hogy ha p < q két P-beli elemre, akkor p megelõzi q-t a sorban.

Megjegyzés: Tehát, ha p és q nem összehasonlítható, akkor semmilyen feltételünk nincs a sorbeli helyzetükre.

A lemma a következõ segédállítás felhasználásával indukcióval igazolható.

Segédállítás: Legyen (P,<₌) egy véges (véges alaphalmazú) részbenrendezett halmaz. Ekkor P-nek van eleme, amelynél nincs kisebb elem P-ben.

Megjegyzés: A segédállításbeli tulajdonság nem ugyanaz mint ``minden elemnél kisebbnek lenni ''.

Tétel: Legyen (P,<₌) egy véges (véges alaphalmazú) részbenrendezett halmaz. Legyen f:P -> R egy függvény, amelybõl a fenti módon egy f^ függvényt készítünk. Ekkor f^ ismeretében f kiszámolható.

I. Bizonyítás: Legyen p₁,p₂,p₃,...,p_n a P alaphalmaz lemmabeli sorbaállítása (n=|P|). i-re vonatkozó teljes indulcióval belátjuk, hogy f^ ismeretében f(p_i) meghatározható. f(p₁) értéke éppen f^(p₁). Általában f^(p_i) a f(p_i) érték és bizonyos a sorban p_i elõtti elemeknél vett f függvény értékeinek összege. Ha indukciós feltevésünk alapján a p_i elõtti elemeknél vett f függvény értékeket visszafejthetjük, továbbá f^ ismeretében f^(p_i)-t is tudjuk, kapjuk hogy f(p_i)-t is ki tudjuk számolni.

Megjegyzés: A fenti bizonyítás konkrét esetekre alkalmazva az is adódik, hogy f kiszámolására, pontosabban az f(p) értékekre egy lineáris függvény adható. Sõt ebben a lineáris függvényben csak azok a f^(q) értékek szerepelhetnek nem-nulla együtthatóval, amelyekre q<₌p.

II. Bizonyítás: Legyen p₁,p₂,p₃,...,p_n a P alaphalmaz lemmabeli sorbaállítása (n=|P|). Ekkor f és f^ is felfogható mint egy n hosszú (oszlop)vektor. f^ származtatása f-bõl egy lineáris leképezés, azaz f^= Ð f, ahol Ð egy a (P,<₌) részbenrendezett halmaztól függõ mátrix, a (P,<₌) részbenrendezett halmaz dzeta mátrixa. Az állítás ekvivalens azzal, hogy ez a mátrix invertálható. Ð egy alsó trianguláris mátrix 1-esekkel a fõátlón. Így az állítás adódik.