Phân hoạch xích đối xứng trên một vành Bool hữu hạn

Phân hoạch xích đối xứng trên một vành Bool hữu hạn: Luận văn Thạc sĩ chuyên ngành đại số và lý thuyết số Tống Minh Hải LÔØI CAÛM ÔN Tröôùc heát toâi xin baøy toû loøng bieát ôn saâu saéc ñeán Thaày höôùng daãn luaän vaên TS Traàn Huyeân, vì söï ñoäng vieân tinh thaàn trong suoát quaù trình nghieân cöùu, cuõng nhö nhöõng tri thöùc môùi meû trong nhieàu lónh vöïc, ñaëc bieät laø loái tö duy ñoäc ñaùo, saéc saûo khi xem xeùt moät vaán ñeà duø trong lónh vöïc toaùn hoïc hay ngoaøi cuoäc soáng. Keá tieáp toâi voâ cuøng bieát ôn PGS.TS Buøi Töôøng Trí vì söï hieåu bieát vaø caûm thoâng saâu saéc, ñaõ ñoäng vieân vaø taïo ñieàu kieän cho toâi hoaøn thaønh baûn luaän vaên naøy . Qua nhöõng baøi giaûng treân lôùp toâi xin baøy toû söï khaâm phuïc tröôùc taøi naêng vaø loøng nhieät tình trong nghieân cöùu khoa hoïc cuûa thaày Mî Vinh Quang. Toâi coù aán töôïng raát saâu saéc vôùi phong caùch laøm vieäc côûi môû, gaàn guõi, nghieâm tuùc vaø khoa hoïc cuûa TS Buøi Xuaân Haûi. Cuoái cuøng toâi xin chaân thaønh caùm ngöôøi baïn toát vaø thoâng minh, Ths Leâ Cao Tuù vì nhöõng nhaän xeùt saâu saéc veà moät soá vaán ñeà lieân quan tôùi ñeà taøi vaø söï ñoäng vieân tinh thaàn trong luùc khoù khaên. Taùc giaû luaän vaên Toáng Minh Haûi LÔØI MÔÛ ÑAÀU Keå töø khi Spenner ñöa ra keát quaû nghieân cöùu veà soá cöïc ñaïi caùc phaàn töû cuûa moät ñôn xích treân taäp P (X) (X höõu haïn) thì raát nhieàu nhöõng khaùm phaù trong lónh vöïc lyù thuyeát toå hôïp ñöôïc caùc nhaø toaùn hoïc tìm ra. Trong ñoù coù moät caáu truùc raát ñeïp laø caáu truùc ñoái xöùng trong P (X). Ñaëc bieät caáu truùc naøy coù theå ñöôïc öùng duïng ñeå giaûi quyeát moät soá vaán ñeà khaùc cuûa lyù thuyeát toå hôïp. Baûn luaän vaên naøy goàm hai chöông. Chöông I trình baøy moät soá tính chaát cô baûn cuûa vaønh bool, xaây döïng quan heä thöù töï, chöùng minh söï toàn taïi cuûa caùc phaàn töû toái tieåu töø ñoù chæ ra söï ñaúng caáu cuûa giöõa vaønh bool höõu haïn B(n) vôùi vaønh Z2xZ2x…xZ2 Chöông II chuùng toâi khaûo saùt moät caáu truùc khaù ñeïp treân moät soá caùc poset ñoù laø caáu truùc ñoái xöùng. Nhôø tính chaát ñoái xöùng trong caùc xích, maø ta coù theå deã daøng kieåm tra ñöôïc soá löôïng cuûa caùc antichain trong moät poset tính ñöôïc soá löôïng cuûa moät hoï caùc taäp hôïp thoûa tính chaát bao haøm chöùa trong, rôøi nhau... Chuùng toâi seõ xaây döïng caùc phaân hoaïch xích ñoái xöùng cho caùc poset thöôøng gaëp laø .... (hay P(S)), poset caùc öôùc cuûa moät soá nguyeân döông in cho tröôùc vaø tích tröïc tieáp cuûa caùc poset vôùi nhau. Ngoaøi ra, vôùi moät phaân hoaïch xích ñoái xöùng cuûa moät poset P, chuùng toâi ñi saâu vaøo tìm hieåu caáu truùc cuûa phaân hoaïch naøy ôû khía caïnh naøy ôû khía caïnh soá xích ñoái xöùng, caùc ñoä daøi caùc xích, soá löôïng caùc xích cuøng chieàu daøi i. Sau ñoù laø moät soá baøi toaùn giaûi quyeát baèng xích ñoái xöùng keát thuùc phaàn naøy baèng moät caùch xaây döïng khaùc cuûa phaân hoaïch xích ñoái xöùng BCO vaø nhöõng öùng duïng cuûa caùch xaây döïng naøy ñeå tính soá antinh trong P(S) vaø tính soá ñöôøng.... trong maët phaúng toïa ñoä. 1 MUÏC LUÏC CHÖÔNG 1 : CAÁU TRUÙC THÖÙ TÖÏ TREÂN VAØNH BOOL HÖÕU HAÏN §1.1Caùc khaùi nieäm veà vaønh bool………………................................ 3 1.1.1Ñònh nghóa vaønh bool……………………………………………. 3 1.1 .2Caùc tính chaát cô baûn cuûa vaønh bool …………………………..... 5 1.1.3 Quan heä thöù töï treân vaønh bool…………………………………………………………. 6 §1.2Vaønh bool höõu haïn……………………………………………………………………………. 7 1.2.1 Söï toàn taïi cuûa caùc phaàn töû toái tieåu…………………………………………….. 7 1.2.2 Söï ñaúng caáu giöõa vaønh B(n) vôùi vaønh Z2xZ2x…xZ2 …………. 11 §1.3Moät soá ñònh nghóa lieân quan ñeán xích ñoái xöùng 1.3.1 Ñònh nghóa quan heä thöù töï treân P…………………………………………….. 12 1.3.2 Haøm haïng r(x)……………………………………………… ……………………………….. 12 1.3.3 Ñònh nghóa xích ñoái xöùng …………………………………………………………….. 12 CHÖÔNG 2 : PHAÂN HOAÏCH XÍCH ÑOÁI XÖÙNG VAØ CAÙC ÖÙNG DUÏNG §2.1Moät soá ñònh nghóa……………………………………………………………………………….. 13 2.1.1 Ñònh nghóa xích trong B(n)………………………………………………………….. 13 2.1.2 Ví duï veà xích ñoái xöùng……………………………………………………………………. 14 §2.2 Caáu truùc ñoái xöùng cuûa moät soá poset thöôøng gaëp…………………… 14 §2.3 Caáu truùc cuûa moät xích ñoái xöùng……………………………………………………… 26 §2.4 Xaây döïng tröïc tieáp phaân hoaïch xích ñoái xöùng cho P (S) …… 33 2.4.1 ÖÙng duïng cuûa caáu truùc xích ñoái xöùng……………………… …………. 42 2 Chöông I CAÁU TRUÙC THÖÙ TÖÏ TREÂN VAØNH BOOL HÖÕU HAÏN Trong chöông naøy, chuùng ta xeùt moät lôùp vaønh ñaëc bieät, lôùp caùc vaønh Bool höõu haïn. Cho moät vaønh Bool höõu haïn B baát kyø (coù 2n phaàn töû). Chuùng ta chæ ra raèng B ñaúng caáu vôùi vaønh Bool Z2 xZ2x…x Z2 (coù n thöøa soá). Hôn nöõa, P(X) goàm taát caû caùc taäp con cuûa taäp X vôùi pheùp giao vaø toång ñoái xöùng cuõng laø moät vaønh Bool coù 2n phaàn töû, neân P(X) ñaúng caáu vôùi B maët khaùc caùc ñaúng caáu naøy baûo toaøn quan heä thöù töï do ñoù ñeå thuaän tieän cho vieäc trình baøy. Trong moät soá tröôøng hôïp, chuùng toâi choïn vaønh Bool Z2 xZ2x…x Z2 ñeå laøm vieäc. Keá tieáp, chuùng toâi trình baøy moät soá khaùi nieäm vaø keát lieân quan ñeán quan heä thöù töï treân B caàn thieát cho chöông sau. §1. Caùc khaùi nieäm veà vaønh Bool Ñònh nghóa 1.1. Moät vaønh B coù ñôn vò ñöôïc goïi laø vaønh Bool neáu moïi phaàn töû x ∈ B thoûa x2 = x. Moät ví duï quen thuoäc veà vaønh Bool laø taäp P(X), taäp taát caû caùc taäp con cuûa taäp X khaùc roãng, cuøng vôùi hai pheùp toaùn ∩ vaø Δ ; trong ñoù ∩ laø pheùp giao thoâng thöôøng cuûa hai taäp hôïp vaø Δ laø pheùp coäng ñoái xöùng xaùc ñònh nhö sau: ∀ A, B ∈ P(X) AΔB = (A \ B) ∪ (B \ A). Vaø ñeå thuaän tieän cho vieäc trình baøy veà sau ta vieát ∩ theo loái nhaân (.) vaø Δ theo loái coäng (+). Baây giôø ta chöùng minh (P(X),+...) laø moät vaønh Bool. Ta caàn kieåm tra caùc tieân ñeà cuûa vaønh: • Pheùp toaùn coäng coù tính keát hôïp : ∀A, B, C ∈ P(X), ta caàn kieåm tra: (A + B) + C = A + (B + C) i) Chöùng minh (A + B) + C ⊂ A + (B + C) Laáy x ∈ (A + B) + C, khi ñoù ta coù: x ∈ C \ [(A \ B) ∪ (B \ A)] hoaëc x ∈ [(A \ B) ∪ (B \ A)] \ C + Neáu x ∈ [(A \ B) ∪ (B \ A)] \ C thì x ∈ (A \ B) ∪ (B \ A) vaø x ∉ C töùc laø x ∈ A \ B ; x ∉ C hoaëc x ∉ B \ A ; x ∉ C + Trong tröôøng hôïp thöù nhaát ta coù : x ∈ A ; x ∈ B ; x ∈ C do ñoù x ∈ A vaø x ∉ (B \ C) ∪ (C \ B) 3 töùc laø: x ∈ A \ [(B \ C) ∪ (C \ B)]. + Trong tröôøng hôïp thöù hai, ta coù x ∈ B, x ∉ A, x ∉ C do ñoù : x ∈ (B \ C) ∪ (C \ B) vaø x ∉ A töùc laø : x ∈ [(B \ C) ∪ (C \ B)] \ A neân x ∈ A + (B + C) Vaäy (A + B) + C ⊂ A + (B + C) ii) Chieàu ngöôïc laïi: A + (B + C) ⊂ (A + B) + C. Chöùng minh töông töï. Vaäy (A + B) + C = A + (B + C). • Pheùp toaùn coäng coù tính giao hoaùn : Vôùi moïi A, B ∈ P(X) ta coù : A + B = (A \ B) ∪ (B \ A) = (B \ A) ∪ (A \ B) = B + A • Pheùp coäng coù phaàn töû khoâng laø taäp φ vì ∀A ∈ P(X), ta coù : A + Φ = (A \φ ) ∪ (φ \ A) = A • Phaàn töû ñoái cuûa phaàn töû A laø phaàn töû A vì : ∀ A ,A + A = (A\A) ∪ (A\A) ∈ (A\A) = φ • Tính keát hôïp cuûa pheùp nhaân : ∀A, B, C ∈ P(X) ta coù : (A ∩ B) ∩ C = A ∩ (B ∩ C) neân (AB)C = A(BC) • Pheùp toaùn nhaân phaân phoái vôùi pheùp toaùn coäng : ∀A, B, C ∈ P(X) ta coù : A(B + C) = A [(B \ C) ∪ (C \ B)] = [A (B \ C)] ∪ [A (C \ B)] = [A B \ AC] ∪ [AC \ AB] = AB + AC vaø (B+C)A = [(B \ C) ∪ (C \ B)] A = [(B \ C) A] ∪ [(C \ B) A] = (BA \ CA) ∪ (CA \ BA) = BA + CA • Pheùp toaùn nhaân coù phaàn töû ñôn vò laø X vì ∀ A ∈ P(X) XA = A ∩ A = A AX = A ∩ X = A 4 Vaäy P(X) laø vaønh Bool. Nhaän xeùt : Trong vaønh Bool P(X), ta ñaõ chöùng minh A ∈ P(X) thì phaàn töû ñoái laø A vaø P(X) laø moät vaønh giao hoaùn. Ta cuõng môû roäng tính chaát naøy leân cho vaønh Bool toång quaùt, cuï theå ta coù : Ñònh lyù 1.2. Trong vaønh Bool B, moïi phaàn töû ñeàu coù phaàn töû ñoái laø chính noù, nghóa laø : ∀x ∈ B -x = x Chöùng minh : Do B laø vaønh neân ∀x ∈ B ⇒ -x ∈ B Theo ñònh nghóa vaønh Bool : (x+x)2 = x+x hay x2 +x2+ x2+ x2 = x + x ⇔ x + x + x+ x = x+x ⇔ x+x =0 x =-x ⇔ Nhaän xeùt : Do keát quaû naøy, vaønh Bool laø vaønh coù ñaëc soá 2. Ñònh lyù 1.3. Moïi vaønh Bool ñeàu giao hoaùn Chöùng minh : ∀x, y ∈ B ta coù : x2 + y2 = x + y = (x + y)2 = x2 + xy + yx + y2 neân xy + yx = 0 Suy ra : xy = -yx = (-y)x = yx (do -y = y) ñònh lyù 1.1) Vaäy B laø vaønh Bool giao hoaùn. Ta bieát raèng, trong vaønh Bool P(X) coù quan heä thöù töï töï nhieân nhö sau : A ⊆ B ⇔ AB = A, ∀A, B ∈ P(X) Quan heä naøy cuõng ñöôïc toång quaùt leân cho moïi vaønh Bool nhö sau : Ñònh lyù 1.4. Trong vaønh Bool B, ñònh nghóa quan heä : ∀x, y ∈ B : x ≤ y ⇔ xy = x. khi ñoù : ≤ laø moät quan heä thöù töï treân B. Chöùng minh : + ∀x ∈ B ta coù : x.x = x neân x ≤ x, töùc coù tính chaát phaûn xaï. + ∀x, y ∈ B sao cho : x ≤ y vaø y ≤ z, ta coù : xy = x vaø yz = y. Do vaønh Bool giao hoaùn neân xy = yx hay x = y töùc quan heä ≤ coù tính phaûn ñoái öùng. + Vôùi x, y, z ∈ B sao cho x ≤ y vaø y ≤ z ta coù : xy = x vaø yz = y Suy ra : xz = (xy)z = x(yz) = xy = x, töùc laø : x ≤ z 5 Neân ≤ coù tính chaát baéc caàu. Vaäy ≤ laø moät quan heä thöù töï cuûa B. Chuù yù : 1. Khi x ≤ y ta noùi : x nhoû hôn hoaëc baèng y hay y lôùn hôn hoaëc baèng x. 2. Vôùi x, y ∈ B ta noùi : x, y so saùnh ñöôïc vôùi nhau neáu x ≤ y hoaëc y ≤ x. Trôû laïi vaønh Bool P(X), ta bieát P(X) coù phaàn töû ñôn vò laø X vaø phaàn töû khoâng laø roãng vaø ta cuõng coù : moãi A ∈ P(X) thì toàn taïi CA = X + A thoûa : CA + A = X vaø (CA) A = Φ CA : goïi laø phaàn buø cuûa A. Ñoái vaønh Bool baát kyø ta cuõng coù ñieàu töông töï. Cuï theå laø : Ñònh lyù 1.5. Cho B laø vaønh Bool, vôùi moãi x ∈ B luoân toàn taïi duy nhaát phaàn töû x* ∈ B thoûa : x + x* = 1 xx* = 0 Chöùng minh : • Söï duy nhaát : vôùi moãi x ∈ B, giaû söû coù y ∈ B cuõng thoûa : x + y = 1 xy = 0 khi ñoù : y = 1 - x = x*∈ B Neân x* laø duy nhaát. • Söï toàn taïi : Vôùi moïi x ∈ B, xeùt x* = 1 + x Khi ñoù : x + x* = x + (1 + x) = x + x + 1 = 1 vaø xx* = x (1 + x) = x + xx = x + x =0 Chuù yù : Phaàn töû x* trong ñònh lyù cuõng goïi laø phaàn töû buø cuûa phaàn töû x ∈ B vaø x* = 1 + x. Khaùi nieäm phaàn buø coù moät soá tính chaát ñôn giaûn laø : 1* = 0 vaø 0* = 1 vaø (x*)* = x, ∀x ∈ B Thöïc ra laø söï môû roäng caùc keát quaû trong P(X): CX = Φ, CΦ = X vaø C(CA) = A, ∀A ∈ P(X) 6 §2. Vaønh Bool höõu haïn Trong muïc naøy ta seõ moâ taû vaønh Bool höõu haïn thoâng qua caùc phaàn töû cöïc tieåu. Vì theá tröôùc tieân ta nghieân cöùu caùc phaàn töû cöïc tieåu cuûa vaønh Bool höõu haïn. Ta coù ñònh nghóa sau : Ñònh nghóa 2.1. Cho vaønh Boll höõu haïn B vôùi quan heä thöù töï ≤ ñöôïc ñònh nghóa trong muïc 1, phaàn töû a ∈ B \ {0} goïi laø phaàn töû cöïc tieåu cuûa B neáu moïi phaàn töû x ∈ B \ {0} maø x ≤ a thì x = a. Chaúng haïn, ñoái vôùi vaønh Bool P(X), vôùi X = {x1, x2,...xn} coù höõu haïn phaàn töû laø 2n vaø vôùi pheùp toaùn bao haøm laø quan heä thöù töï thì caùc phaàn töû cöïc tieåu laø {x1}, i=1,.... n. Baây giôø trong vaønh Bool höõu haïn B ta chöùng minh söï toàn taïi cuûa phaàn töû cöïc tieåu. Ñònh lyù 2.1. Trong vaønh Bool höõu haïn thì toàn taïi phaàn töû cöïc tieåu. Chöùng minh : Xeùt x ∈ P(X) \ {0} + Neáu x laø phaàn töû cöïc tieåu cuûa B thì x laø phaàn töû caàn tìm. Neáu khoâng x coù phaàn töû x1 ∈ B \ {0} sao cho x1 < x. + Neáu x1 laø phaàn töû cöïc tieåu cuûa B thì x1 laø phaàn töû caàn tìm. Neáu khoâng x1 coù phaàn töû x2 ∈ B \ {0} sao cho x2 < x1. + Neáu x2 laø phaàn töû cöïc tieåu cuûa B thì x2 laø phaàn töû caàn tìm. Neáu khoâng x2 coù phaàn töû x3 ∈ B \ {0} sao cho x3 < x2. Do B höõu haïn vaø caùc phaàn töû x1, x2,... ñoâi moät khaùc nhau, quaù trình seõ döøng laïi sau höõu haïn böôùc, khi ñoù toàn taïi x0 laø phaàn töû cöïc tieåu cuûa B. Nhö vaäy, taäp hôïp taát caû caùc phaàn töû cöïc tieåu cuûa vaønh Bool höõu haïn laø khaùc roãng. Ñeå tieän lôïi cho vieäc trình baøy, töø ñaây veà sau ta giaû söû B laø vaønh Bool höõu haïn coù taäp caùc phaàn töû cöïc tieåu laø M = {x1, x2, .... xn}. Baèng caùch chöùng minh töông töï ñònh lyù 2.1, ta coù keát quaû sau : Ñònh lyù 2.2. Moïi x ∈ B \ {0} thì taäp N caùc phaàn töû cöïc tieåu cuûa B nhoû hôn hoaëc baèng x laø khaùc roãng. Chuùng ta xeùt caùc ñaëc tröng cuûa phaàn töû cöïc tieåu cuûa B, döïa vaøo töø toång quaùt cuûa vaønh Bool höõu haïn P(X). Trong P(X), taäp caùc phaàn töû cöïc tieåu laø : X = {x1 x2,... xn}. Khi ñoù ta coù {xi} ∩ {xj} = Φ hay {xi} , {xj} = 0. Vaø moïi A ∈ P(X) thì A laø hôïp cuûa caùc phaàn töû cöïc tieåu töùc A = , m ≤ n thì A = }x....x,x{ mkkk 21 7 }x{ ik ∪....∪ = Δ Δ... , vôùi chuù yù trong P(X) : Neáu A, B ∈ P(X) vaø A ∩ B = Φ thì AΔB = A ∪ B. Ñieàu naøy seõ ñöôïc toång quaùt cho vaønh Bool baát kyø nhö sau : }x{ mk }x{ ik }x{ k2 }x{ mk Ñònh lyù 2.3. Neáu xi, xj laø hai phaàn töû cöïc tieåu phaân bieät cuûa B thì xixj = 0 Chöùng minh : Giaû söû xixj ≠ 0 töùc xixj ∈ B \ {0} Ta coù : xixj ≤ xi vaø xixj ≤ xj (Do xi(xixj) = (xixi)xj = xixj vaø xi(xixj) = (xixj) xj = xixj) Vì xixj laø caùc phaàn töû cöïc tieåu neân xixj = xi vaø xixj = xj Neân xi = xj , ñieàu naøy maâu thuaãn. Vaäy xixj = 0 Ñònh lyù 2.4. Moïi ∀ x ∈ B \ {0} ñeàu coù theå vieát döôùi daïng : x = trong ñoù : , i = 1,... m laø caùc phaàn töû cöïc tieåu cuûa B thoûa : ≤ x. mkkk x....xx +++ 21 ik x ik x Chöùng minh : Do ∀x ∈ B \ {0} neân theo ñònh lyù 2.2, toàn taïi phaàn töû cöïc tieåu xk ≤ x vaø goïi taäp laø caùc phaàn töû cöïc tieåu cuûa B nhoû hôn hoaëc baèng x laø taäp khaùc roãng. }x....x,x{ mkkk 21 Ñaët y =x+ ( mkkk x....xx +++ 21 ). Giaû söû y 0 . Khi ñoù toàn taïi phaàn töû cöïc tieåu a≠ ≤ y Maët khaùc ,ta coù y≤x Thaät vaäy : yx =xx+ ( mkkk x....xx +++ 21 ) x = x+ xx....xxxx mkkk +++ 21 = x+( mkkk x....xx +++ 21 ) = y (do ≤ x ⇔ x = ) ik x ik x ik x Suy ra a x, do ñoù toàn taïi i sao cho a =≤ ik x laø cöïc tieåu cuûa x Khi ñoù: ya = y ik x = ik x ≠ 0 (do ik x laø phaàn töû cöïc tieåu) Va øy ik x =x ik x +( mkkk x....xx +++ 21 ) ik x = ik x + ik x =0 (tính chaát vaønh bool) 8 ⇒ maâu thuaãn, vaäy y=0 ⇔ x= mkkk x....xx +++ 21 Keát luaän : Moãi phaàn töû khaùc khoâng cuûa B luoân bieåu dieãn thaønh toång caùc phaàn töû cöïc tieåu cuûa B nhoû hôn hoaëc baèng x. baây giôø, chuùng ta khaúng ñònh caùch bieåu dieãn qua caùc phaàn töû cöïc tieåu treân laø duy nhaát sai khaùc moät hoaùn vò thöù töï cuûa caùc phaàn töû cöïc tieåu. Ñònh lyù 2.5. Neáu , .... laø caùc phaàn töû cöïc tieåu cuûa B sao cho : 1l y tl y x = + + ... + thì D = { , , ... }= C ={ } 1l y 2l y tl y 1l y 2l y tl y mkkk x,...x,x 21 Trong ñoù : laø caùc phaàn töû cöïc tieåu cuûa B thoûa ≤ x. mkk x,...x 1 ik x Chöùng minh : Giaû söû , .... laø caùc phaàn töû cöïc tieåu cuûa B thoûa : 1l y tl y x = + + ...+ = 1l y 2l y tl y mkkk x....xx +++ 21 giaû söû toàn taïi vaø kl y D∈ kl y C∉ khi ñoù ta coù x =( + + ...+ ) =( kl y 1l y 2l y tl y kl y mkkk x....xx +++ 21 ) kl y kl y = = 0 (do tích caùc phaàn töû cöïc tieåu khaùc nhau baèng 0) 2 kl y ⇒ maâu thuaãn (vì caùc phaàn töû cöïc tieåu ñeàu khaùc 0) ⇒ { , , ... } = { } (1) 1l y 2l y tl y mkkk x,...x,x 21 Ñeán ñaây ta coù theå khaúng ñònh : Toång caùc phaàn töû cöïc tieåu cuûa B ñeàu thuoäc vaøo B vaø ngöôïc laïi x B \ {0} ñeàu ñöôïc vieát thaønh toång caùc phaàn töû cöïc tieåu cuûa B nhoû hôn hoaëc baèng x. Vaäy ta coù : B = {∑ vaø xi laø phaàn töû cöïc tieåu cuûa B}. = ∈εεn i iii },{lx 1 10 Maët khaùc : Z2 ⊕ Z2 ⊕ ... ⊕ Z2 = {(ε1,...., εn) / εi ∈ {0, 1}} Xeùt ñoàng caáu ψ : B → Z2 ⊕ Z2 ⊕ ... ⊕ Z2 x = ∑ = εεεn i nii ),....,(x 1 16 ta coù ñöôïc do moãi phaàn töû x cuûa B ñeàu ñöôïc vieát moät caùch duy nhaát x = neáu ta coá ñònh thöù töï töø 1 ñeán n. ∑ = εn i iix 1 9 Roõ raøng ψ laø moät song aùnh neân ta coù heä quaû sau : Heä quaû. Neáu B laø moät vaønh Bool höõu haïn, coù taäp caùc phaàn töû cöïc tieåu laø ... thì soá phaàn töû cuûa vaønh B laø 2n. Hôn theá nöõa, aùnh xaï ψ coøn baûo toaøn caùc pheùp toaùn trong B, baûo toaøn quan heä thöù töï trong B. Sau ñaây chuùng ta seõ chöùng minh ñieàu ñoù : Ñònh lyù 2.6. Neáu (ε1,...., εn), (ε’1,...., ε’n) thì (ε1,...., εn) + (ε’1,...., ε’n) = (ε’1+ ε1,..., ε’n + εn) vôùi ε1 + ε’i = 0 neáu ε1 + ε’i vaø baèng 1 neáu ε1 ≠ ε’i Chöùng minh : Giaû söû B coù taäp caùc phaàn töû cöïc tieåu laø {x1,...., xn} Vôùi moïi (ε1 ,...., εn) = ψ ( ) vaø (ε’1,...., ε’n) = ψ ( ) ∑ = εn i iix 1 ∑ = εn i ii ' x 1 Xeùt x + y = (ε1 + ε’1) x1 + (ε2 + ε’2)x2 + ....+ (εn + ε’n)xn ÔÛ ñaây : + Neáu εi + ε’i (töùc cuøng baèng 0 hoaëc cuøng baèng 1) thì ta coù (εi + ε’i)xi = 0 (do B laø vaønh coù ñaëc soá 2). + Neáu εi ≠ ε’i (töùc trong {εi , ε’i} coù moät phaàn töû baèng 0 vaø phaàn töû coøn laïi baèng 1) neân (εi + ε’i) xi = xi Do vaäy x + y = vaø ψ (x + y) = (ε’1 + ε1,....., ε’n + εn) ∑ = ε+εn i ini x)( 1 Ñònh lyù 2.7. Neáu (ε1 ,..... εn), (ε'1 ,...., ε’n) ∈ B thì (ε1 ,...., εn) (ε’1,...., ε’n) = (ε1 ε’1,...., εnε’n) vôùi εiε’i baèng 1 neáu εi = ε’i = 1 vaø baèng 0 neáu εi = 0 hoaëc ε’i = 0 Chöùng minh. Giaû söû B coù taäp caùc phaàn töû cöïc tieåu laø {x1,...., xn} Vôùi moïi (ε1 ,...., εn) = ψ ( ) vaø (ε’1 ,...., ε’n) = ψ (∑ ) ∑ = εn i iix 1 = εn i ii x' 1 Töø hai ñònh lyù treân ta coù : Ñònh lyù 2.8. Vaønh Bool höõu haïn B coù taäp caùc phaàn töû cöïc tieåu laø .... thì B ñaúng caáu vôùi vaønh ... (toång cuûa n soá haïng Z..) trong ñoù vaønh... coù pheùp toaùn + vaø.. nhö trong ñònh lyù 2.6 vaø ñònh lyù 2.7. Chuùng ta ñaõ bieát trong P(X) vôùi x = {x 10 Heä quaû 2.9. Moïi vaønh Bool B höõu haïn baát kyø ñeàu ñaúng caáu vôùi vaønh P(X) vôùi X laø taäp coù n phaàn töû naøo ñoù. Ngoaøi söï chuyeån caùc pheùp toaùn treân B qua vaønh... (toång cuûa n soá haïng Z...) y coøn chuyeån caùc phaàn töû buø vaø quan heä thöù töï nhö sau : Ñònh lyù 2.10. Neáu x = ∈ B thì (ε1 ,...., εn)* = (ε*1 ,...., ε*n) ∑ = εn i iix 1 Vôùi ε*i = 1 neáu εi = 0 vaø ε*i = 0 hoaëc εi = 1, i = 1,..., n. Chöùng minh. Vôùi moïi (ε1 ,...., εn) = ψ ( ) vaø (ε1 ,...., εn)* = ψ (x*) ∑ = εn i iix 1 Thì x* = 1 + x = 1 + ε1 x1 + .... + εnxn = (x1 + ....+ xn) + (ε1 x1 +...+ εnxn) = (1 + ε1) x1 + ....+ (1 + εn) xn Ñaët ε*i = 1 + εi ; i = 1, .... n. Khi ñoù : ε*1 = 1 neáu εi = 0 vaø ε*i = 0, neáu εi = 1 (do 2x1 = 0) Neân (ε*1,..., ε*n) = y (x*) hay (ε1 ,...., εn)* = (ε*1 ,...., ε*n) Ñònh lyù 2.11. Neáu x = , y = ∈ B vaø x ≤ y thì ∑ = εn i iix 1 ∑ = εn i ii x' 1 ε1 ≤ ε’i , i = 1, ...n Chöùng minh. Giaû söû (ε1 ,...., εn) ≤ (ε’1 ,...., ε’n)xn = (ε1x1 +...+ εnxn) Do x ≤ y ⇔ xy = x töùc : (ε1ε’1)x1 + ....+ (εnε’n)xn = (ε1x1 + ....+ εnxn) Suy ra εi (1 + ε’i) = 0, i = 1,...., n. Khi ñoù : εi = 0 hoaëc ε’i = 1, i = 1,....,n. Caû hai khaû naêng ta ñeàu coù εi ≤ ε’i , i = 1,..., n Toùm laïi, trong chöông naøy ta thu ñöôïc keát quaû sau : Cho moät vaønh Bool höõu haïn B baát kyø thì B ñaúng caáu vôùi toång tröïc tieáp vôùi moät soá caùc tröôøng Z2 vaø cuøng ñaúng caáu vôùi vaønh P(X), trong ñoù X laø moät taäp höõu haïn phaàn töû naøo ñoù. Vaø hôn nöõa khaùi neäim phaàn töû buø, caùc quan heä thöù töï ñeàu töông öùng vôùi nhau giöõa B vaø P(X). 3.1. Moät soá khaùi nieäm cô baûn. Cho moät taäp coù thöù töï P baát kyø, (P, ≤). Chuùng ta coù moät soá khaùi nieäm sau : • Hai phaàn töû x, y ∈ P goïi laø so saùnh ñöôïc vôùi nhau neáu x ≤ y hoaëc y ≤ x. • Neáu x ≤ y vaø x ≠ y thì ta vieát x ≤ y • Neáu x < y vaø khoâng coù phaàn töû z ∈ P naøo thoûa x < z < y thì ta goïi phaàn töû y phuû x. 11 • Neáu toàn taïi duy nhaát phaàn töû z ∈ P sao cho z ≤ x, vôùi moïi x ∈ P thì ta goïi z laø phaàn töû khoâng vaø ñöôïc kí hieäu laø 0. • Neáu phaàn töû x ∈ P thoûa khoâng toàn taïi y ∈ P naøo sao cho y < x thì x goïi laø phaàn töû toái tieåu. Ngöôïc laïi, neáu phaàn töû x ∈ P thoûa khoâng toàn taïi y ∈ P naøo sao cho x < y thì x goïi laø phaàn töû toái ñaïi. • Neáu x1 < x2 <.... < xn thì ta goïi x1, x2,..., xn laäp neân xích. Moät xích baûo hoøa laø xích x1 < x2 <...< xn sao cho xi+1 phuû xi, ∀i < n. • Neáu taát caû caùc xích baûo hoøa töø 0 ñeán x coù cuøng kích thöôùc vaø neáu ñònh nghóa ñoä daøi cuûa moät xích laø löïc löôïng cuûa xích tröø ñi 1. Khi ñoù : ta coù theå ñònh nghóa haïng cuûa phaân töû x laø r(x), laø ñoä daøi cuûa moät xích baûo hoøa töø 0 ñeán x. Vôùi khaùi nieäm haïng r(x), ta coù ñònh nghóa haøm haïng nhö sau : Ñònh nghóa 3.2: Haøm soá r : P → R+ goïi laø haøm haïng cuûa P x 6 r(x) trong ñoù : r(x) laø ñoä daøi cuûa moät xích baûo hoøa baát kyø töø 0 ñeán x nhö ñònh nghóa treân. Ñeå deã daøng trong vieäc söû duïng haøm haïng cuûa moät taäp coù thöù töï P ta tìm caùc töông ñöông cuûa noù nhö sau : Meänh ñeà 3.1.2. Cho (P, ≤) vôùi haøm haïng r. Khi ñoù : (i) r(x) ∈ N vaø r(0) = 0, N : laø taäp caùc soá töï nhieân. (ii) Neáu x phuû y thì r(x) = r(y) + 1 Chöùng minh. (i) Theo ñònh nghóa haøm haïng r ta coù r(x) laø ñoä daøi cuûa moät xích baûo hoøa baát kyø töø 0 ñeán x neân r(x) laø moät soá töï nhieân vaø r(0) = 0 (ii) Giaû söû x phuû y, vì y ∈ P neân xeùt moät xích baûo hoøa baát kyø töø 0 ñeán y laø 0 < x1 < x2 < ... < xr(y)-1 < y neân ta coù moät xích baûo hoøa töø 0 ñeán x laø 0 < x1 < x2 < ... < xr(y)-1 < y < x neân theo ñònh nghóa haïng cuûa moät phaàn töû, ta coù r(x) = r(y) + 1. 3.3 Moät soá keát quaû cô baûn treân taäp coù thöù töï Tröôùc heát ta coù theâm moät soá ñònh nghóa cô baûn sau : Ñònh nghóa 3.4.1. Cho moät taäp coù thöù töï (P, ≤), coù haøm haïng r. Vôùi x1, x2....xn goïi laø laäp neân moät xích ñoái öùng x1 < x2 < ....< xn neáu : (i) xi+1 phuû xi, ∀i < h (ii) r(x1) + r(xh) = r(P) vôùi r(P) laø haïng lôùn nhaát trong P. 12 P : goïi laø coù thöù töï xích ñoái xöùng neáu P coù theå phaân hoaïch thaønh caùc xích ñoái xöùng. 13 CHÖÔNG II : PHAÂN HOAÏCH XÍCH ÑOÁI XÖÙNG VAØ CAÙC ÖÙNG DUÏNG Trong chöông naøy, chuùng toâi seõ khaûo saùt moät caáu truùc khaù ñeïp treân moät soá caùc poset ñoù laø caáu truùc ñoái xöùng. Nhôø tính chaát ñoái xöùng trong caùc xích, maø ta coù theå deã daøng kieåm tra ñöôïc soá löôïng cuûa caùc antichain trong moät poset tính ñöôïc soá löôïng cuûa moät hoï caùc taäp hôïp thoûa tính chaát bao haøm chöùa trong, rôøi nhau... Chuùng toâi seõ xaây döïng caùc phaân hoaïch xích ñoái xöùng cho caùc poset thöôøng gaëp laø .... (hay P(S)), poset caùc öôùc cuûa moät soá nguyeân döông in cho tröôùc vaø tích tröïc tieáp cuûa caùc poset vôùi nhau. Ngoaøi ra, vôùi moät phaân hoaïch xích ñoái xöùng cuûa moät poset P, chuùng toâi ñi saâu vaøo tìm hieåu caáu truùc cuûa phaân hoaïch naøy ôû khía caïnh naøy ôû khía caïnh soá xích ñoái xöùng, caùc ñoä daøi caùc xích, soá löôïng caùc xích cuøng chieàu daøi i. Sau ñoù laø moät soá baøi toaùn giaûi quyeát baèng xích ñoái xöùng keát thuùc phaàn naøy baèng moät caùch xaây döïng khaùc cuûa phaân hoaïch xích ñoái xöùng BCO vaø nhöõng öùng duïng cuûa caùch xaây döïng naøy ñeå tính soá antinh trong P(S) vaø tính soá ñöôøng.... trong maët phaúng toïa ñoä. I. MOÄT SOÁ ÑÒNH NGHÓA Trong poset P(S), taäp taát caû caùc taäp con cuûa n-taäp S chuùng ta coù moät thöù töï bao haøm A ≤ B ⇒ A ⊂ B. Töông öùng trong poset B(n) coù thöù töï laø : a ≤ b ⇔ a.b = a, trong ñoù : ab laø vectô ñaïi dieän cuûa taäp A, B töùc laø a = (a1,... an) vôùi a1 = 1 neáu ai ∈ A vaø aj = 0 neáu aj ∉ A vaø töông töï cho B. Chuù yù ñeå cho thuaän tieän chuùng thöôøng vieát vectô a = (a1 ... an) laø a = a1a2... an. Cho a = a1a2... al ∈ BCK vaø b = b1 ...b1 ∈ BCL) thì ta vieát ab ñeå chæ cho vectô a1....ak b1....bl ∈ B (k + l) I.1. Ñònh nghóa : Trong poset B(n) taäp taát caùc vectô Bool n chieàu a) Moät xích caùc phaàn töû trong B(n) laø moät daõy caùc phaàn töû a1 < a2 < .... < am vôùi a1 ∈ B(n) (1) b) Xích (1) ñöôïc goïi laø xích baûo hoøa neáu r (ai+1) = r(ai) + 1 ∀ i = 1,..., m c) Xích (1) ñöôïc goïi laø xích ñoái xöùng neáu noù laø xích baûo hoøa vaø thoûa theâm tính chaát r (a1) + r (am) = n. Trong ñoù : a = a1 .... an ∈ B(n) thì r Ca = a1 + a2 + ... +an goïi laø haïng cuûa vectô a. II.2. Nhaän xeùt : • Khi n chaün thì ñoä daøi m cuûa xích laø soá leû 14 • Khi n leû thì ñoä daøi m cuûa xích laø soá chaün Ví duï : Trong poset B (5) thì : 00100 < 10100 < 10110 < 10111 laø moät xích ñoái xöùng. Trong poset B (4) thì 0010 < 1010 < 1011 laø moät xích ñoái xöùng. II. CAÁU TRUÙC ÑOÁI XÖÙNG CUÛA MOÄT SOÁ POSET THÖÔØNG GAËP. 1. Caáu truùc ñoái xöùng cuûa poset B(n) (hay P(S). Chuùng ta seõ chæ ra raèng trong poset B(n) coù caáu truùc ñoái xöùng tröôùc taäp B(n) laø hôïp cuûa caùc xích ñoái xöùng rôøi nhau baèng caùch xaây döïng quy naïp theo n bôûi ñònh lyù sau : 1.1. Ñònh lyù II.1. Poset B(n) caùc vectô Bool n chieàu coù moät phaân hoaïch thaønh caùc xích ñoái xöùng. Chöùng minh: Chöùng minh baèng quy naïp theo soá chuaån n cuûa vectô. Vôùi n = 1, trong B(1) coù moät phaân hoaïch xích ñoái xöùng laø 0 < 1, do ñoù ñònh lyù ñuùng cho tröôøng hôïp n = 1. Baây giôø, giaû söû ñònh lyù ñuùng cho tröôøng hôïp n = k, töùc laø trong B(n) coù moät phaân hoaïch ra thaønh caùc xích ñoái xöùng. Xeùt vaønh Bool B(n) + a, ta chæ ra B(n) + 1) cuõng coù phaân hoaïch xích ñoái xöùng baèng thuû tuïc nhö sau : laáy moät xích ñoái xöùng baát kyø trong phaân hoaïch xích ñoái xöùng cuûa B(n) laø : a1 < a2 < ..... < ah. Ta xeùt hình chöõ nhaät daïng sau: ai0 < a20 .... < ah-10 < ah 0 ai1 < a21 .... < ah-11 < ah 1 Vaø sinh ra 2 xích trong vaønh Bool B(n)+1 nhö chæ daãn trong hình chöõ nhaät laø: ai0 < a20 .... < ah-10 < ah 0 < ah 1 (1) vaø ai1 < a21 .... < ah-11 (2) Vaø 2 xích (1) vaø (2) laø 2 xích ñoái xöùng. Thaät vaäy : • Trong xích (1), theo giaû thuyeát quy naïp : r (a1) + r (a2) = n Hay r(a10) + r(a20) = n cho neân r(a10) + r (a11) = n + 1 vaø xích (1) laø xích baûo hoøa neân (1) laø xích ñoái xöùng trong B(n)+1) • Trong xích (2), theo giaû thuyeát quy naïp : r (a1) + r (ah-1) = n -1 Neân r(a11) + r(ah-11) = n -1 + 2 = n + 1 Vaø do xích a1 < a2 .... < ah baûo hoøa neân xích (2) cuõng baûo hoøa neân xích (2) laø moät xích ñoái xöùng trong B(n+1). 15 Hôn nöõa, B(n+1) {a.o ⎜ a ∈ B(n)} ∪ { an ⎜ a ∈ B(n)} Do ñoù cöù laàn löôït, laáy töøng xích trong B(n) baèng caùch laøm treân ta coù ñöôïc B(n)+1) coù phaân hoaïch xích ñoái xöùng. Ñeå minh hoïa cho caùch xaây döïng phaân hoaïch xích ñoái xöùng cuûa B(n) ta xeùt ví duï xaây döïng cho B(5). Ñeå xaây döïng ñöôïc cho B(5) ta phaûi xaây döïng cho B(1), B(2), B(3) vaø B(4) tröôùc. 1.2. Ví duï II.2. Xaây döïng phaân hoaïch xích ñoái xöùng cho B(5) nhö sau : • Ñoái vôùi B(1) Ta coù : 0 < 1 • Ñoái vôùi B(2) Xeùt hình chöõ nhaät 00 < 10 01 < 11 ta coù phaân hoaïch xích ñoái xöùng B(2) laø : 01 00 < 10 < 11 • Ñoái vôùi B(3). Xeùt caùc hình chöõ nhaät. 010 011 000 < 100 < 110 001 < 101 < 111 Ta coù phaân hoaïch xích ñoái xöùng cho B(5) laø : 010 < 011 001 < 101 000 < 100 < 110 < 111 • Ñoái vôùi B(4). Xeùt caùc hình chöõ nhaät. 0100 < 0110 0101 < 0111 0010 < 1010 0011 < 1011 0000 < 1000 < 1100 < 1110 0001 < 1001 < 1101 < 1111 Ta coù phaân hoaïch xích ñoái xöùng cho B(4) laø : 0101 0011 16 0100 < 0110 < 0111 0010 < 1010 < 1011 0001 < 1001 < 1101 0000 < 1000 < 1100 < 1110 < 1111 • Ñoái vôùi B(5). Xeùt caùc hình chöõ nhaät. . 01010 01011 . 00110 00111 . 01000 < 01100 < 01110 01001 < 01101 < 01111 . 00100 < 10100 < 10110 00101 < 10101 < 10111 . 00010 < 10010 < 11010 00011 < 10011 < 11011 00000 < 10000 < 11000 < 11100 < 11110 00001< 10001 < 11001 < 11101 < 11111 Ta coù phaân hoaïch xích ñoái xöùng cho B(5) laø : 01010 < 01011 00110 < 00111 01001 < 01101 00101 < 10101 00011 < 10011 01000 < 01100 < 01110 < 01111 00100 < 10100 < 10110 < 10111 00010 < 10100 < 11010 < 11011 00001 < 10001 < 11001 < 11101 00000 < 10000 < 11000 < 11100 < 11110 < 11111 2. Caáu truùc ñoái xöùng cho ta taäp M(m) : M(m) - hôïp taát caû caùc öôùc cuûa soá nguyeân döông m cho tröôùc. Ta ñaõ bieát M(m) coù theå ñöôïc xem nhö laø toång quaùt hoùa cuûa poset P(S). Baèng caùch töông töï nhö B(n) (hay P(S) töùc baèng phöông phaùp quy naïp thì lieäu M(m) coù ñöôïc caáu truùc 17 ñoái xöùng nhö P(S) hay B(m) hay khoâng ? Ñeå tìm lôøi khaúng ñònh cho caâu hoûi naøy, tröôùc heát ta nhaéc laïi moät soá khaùi nieäm. 2.1. Ñònh nghóa : Trong ña taäp M(m) a) Moät xích trong M(m) laø n daõy phaàn töû daïng : d1 < d2 <...< dh trong ñoù : di < di+1 ⇔ di / di+1 ∀i = 1,.... h+1 b) Xích (2) ñöôïc goïi laø xích baûo hoøa neáu phöông soá di+1 / di laø moät soá nguyeân toá. c) r(d) laø haïng cuûa phaàn töû d laø soá caùc thöøa soá nguyeân toá cuûa d. d) Xích (2) ñöôïc goïi laø xích ñoái xöùng neáu noù vöøa laø xích baûo hoøa vaø thoûa maõn: r(d1) + r (d2) = r(m). Ví duï : . r(23) = r (2.2.2) = 3. . r(23.35) = r (2.2.3.3.3.3) = 2 + 5 = 7 . s < 2.3 < 2.32 ⊂ 2.22 5 laø moät xích ñoái xöùng hay nb (22.32.5) 2.2. Ñònh lyù 2 : Poset M(m) taäp taát caû caùc öôùc cuûa moät soá nguyeân döông m cho tröôùc coù phaân hoaïch xích ñoái. Chöùng minh: Ta chöùng minh phöông phaùp quy naïp theo n soá caùc öôùc nguyeân toá khaùc nhau cuûa m : Vôùi n = 1 hay m coù daïng m = pα thì M(m) = {1, p. p2...., pα} coù phaân hoaïch xích ñoái xöùng laø 1 < p < p2 < ....< pα. Vaäy ñònh lyù ñuùng cho tröôøng hôïp n = 1. Baây giôø giaû söû ñònh lyù ñuùng cho tröôøng hôïp n = k, töùc M(m1) coù phaân hoaïch xích ñoái xöùng. Ta caàn chöùng minh raèng ñònh lyù cuõng ñuùng trong tröôøng hôïp n = k + 1, töùc m coù daïng m = pαm1 vôùi m1 coù 4 thöøa soá nguyeân toá._.