Bóng của đoạn trong poset các tập con tập đa bội

Tạp chí KHOA HỌC ĐHSP TPHCM Trần Huyên<br /> _____________________________________________________________________________________________________________<br /> <br /> <br /> <br /> <br /> BÓNG CỦA ĐOẠN TRONG POSET<br /> CÁC TẬP CON TẬP ĐA BỘI<br /> TRẦN HUYÊN*<br /> <br /> TÓM TẮT<br /> Trong bài báo này, chúng tôi xem xét về bóng của một đoạn trong poset các tập con<br /> của tập đa bội theo thứ tự từ điển và đưa ra một vài điều kiện cần và đủ để bóng của một<br /> đoạn trong poset này là một đoạn.<br /> Từ khóa: bóng tập hợp, đoạn, mức.<br /> ABSTRACT<br /> On the shadow of a segment in the poset of subsets of multiple sets<br /> In this paper, we look at the shadow of a segment in the poset of subsets of multiple<br /> set, defined lexicographic order, and prove some necessary and sufficient conditions to<br /> prove that the shadow of a segment in this poset is a segment.<br /> Keywords: shadow of the set, segment, level.<br /> <br /> 1. Mở đầu<br /> Poset S ( k1 ,k2 ,..., kn ) các tập con của tập đa bội n phần tử mà phần tử thứ i lặp ki<br /> lần, có thể đồng nhất với các vectơ nguyên x = x1 x2 ...xn mà 0 ≤ xi ≤ ki với mỗi i. Thứ<br /> tự bao hàm của các tập con chuyển sang các vectơ cho ta thứ tự tự nhiên sau:<br /> x = x1 x2 ...xn ≤ y = y1 y2 ... yn khi và chỉ khi xi ≤ yi với mọi i.<br /> Khái niệm bóng của phần tử và tập hợp trong poset S ( k1 ,k2 ,..., kn ) được xác định<br /> tương tự như trong poset các tập con tập đơn bội. Cụ thể là, với mỗi phần tử<br /> a = a1a2 ...an , bóng thứ i của a là ∆ i a = a1... ( ai − 1) ...an nếu ai > 0, còn ∆ i a = ∅ nếu<br /> ai = 0 . Bóng của phần tử a là ∆a = U ∆ i a . Nếu tập A ⊂ S ( k1 ,k2 ,..., kn ) thì bóng<br /> ∆A = U{∆a : a ∈ A} .<br /> Với mỗi x = x1 x2 ...xn , hạng của x là x = x1 + x2 + ... + xn .<br /> Với mỗi số tự nhiên k cho trước, mức hạng k trong S ( k1 ,k2 ,..., kn ) được định<br /> nghĩa là: S k = { x : x = k }.<br /> Các nhà toán học Clement và Lindstrom đã xác lập trên mỗi mức Sk một thứ tự<br /> tuyến tính – là thứ tự từ điển – như sau: Với a = a1...as ...an và b = b1...bs ...bn thì a < b<br /> nếu tồn tại số tự nhiên s, 1 ≤ s ≤ n sao cho at = bt khi t < s còn as < bs , đồng thời đã<br /> chứng minh được với thứ tự từ điển này, S ( k1 ,k2 ,..., kn ) là một k – poset. Nói riêng, họ<br /> <br /> *<br /> TS, Trường Đại học Sư phạm TPHCM<br /> <br /> <br /> 3<br /> Tạp chí KHOA HỌC ĐHSP TPHCM Số 33 năm 2012<br /> _____________________________________________________________________________________________________________<br /> <br /> <br /> <br /> <br /> đã chỉ ra rằng, bóng của một đoạn đầu xác định bởi phần tử a: IS ( a ) = { x : x ≤ a}<br /> trong S k theo thứ tự từ điển lại là một đoạn đầu trong S k −1 .<br /> Bài viết này giới thiệu vài mở rộng của kết quả trên, nhằm giải quyết vấn đề: Với<br /> những điều kiện nào cho một đoạn [ a; b ] trong S k theo thứ tự từ điển thì bóng ∆ [ a; b ]<br /> lại là một đoạn trong S k −1 ? Cũng vì lí do này, mà từ nay về sau, trong bài viết này, thứ<br /> tự mà ta nói tới chỉ là thứ tự từ điển.<br /> 2. Các kết quả chính<br /> Để tiện lợi cho sự trình bày, trước hết ta cần thống nhất một số kí hiệu.<br /> Với mỗi phần tử a ∈ S k mà tọa độ khác không đầu tiên là ai ta có thể viết:<br /> a = zai u , ở đây z = ∅ hay z = 0...0 , còn u = ai +1...an . Nếu tọa độ khác không cuối<br /> cùng của a là at thì ta viết a = vat z . Đối với các bóng thành phần của phần tử a, ta sẽ kí<br /> hiệu: ∆ h a = max {∆ i a} , ∆ l a = min {∆ i a} .<br /> Dễ thấy: nếu a = zai uat z thì ∆ h a = zai u ( at − 1) z và ∆ l a = z ( ai − 1) uat z<br /> Đối với số tự nhiên m ≤ k , ta kí hiệu:<br /> hi ( m ) = max { x = zxi u : x = m, xi ≠ 0}<br /> li ( m ) = min { x = vxi z : x = m, xi ≠ 0}<br /> Nói riêng, h ( m ) = max { x : x ∈ S m } , l ( m ) = min { x : x ∈ S m }<br /> Bây giờ, ta xét bóng ∆ [ a; b ] mà a, b có tọa độ khác 0 đầu tiên là như nhau, tức<br /> a = zai u và b = zai v . Ta sẽ phân tích ∆ [ a; b ] thành hai bộ phận được kí hiệu như sau:<br /> ∆ l [ a; b ] = {∆ l x : x ∈ [ a; b ]} = { z ( ai − 1) w : zai w ∈ [ a; b ]}<br /> <br /> và ∆ h [ a; b] = ∆ [ a; b] \ ∆l [ a; b] = { zai w ' : zai w ' ∈ ∆ [ a; b]}<br /> Để ý rằng, khi a, b thỏa mãn điều kiện trên, ta luôn có: ∆ h a ≤ ∆ hb và ∆l a ≤ ∆l b ,<br /> do đó ta có bao hàm thức: ∆ [ a; b ] ⊂ ⎡⎣ ∆ l a; ∆ hb ⎤⎦ . Vậy để có ∆ [ a; b ] là đoạn, ta cần có<br /> bao hàm thức ngược lại. Để giải quyết yêu cầu này, trước hết ta cần đến các kết quả<br /> sau:<br /> Mệnh đề 1<br /> Trong mức Sk cho a = zai u < zai v = b . Khi đó, ∆ l [ a; b ] =<br /> { z ( a − 1) w : za w ∈ [ a; b]} luôn luôn là một đoạn. Nếu a = za zl ( k − a )<br /> i i i i thì ∆ h [ a; b ]<br /> cũng là một đoạn.<br /> <br /> <br /> <br /> <br /> 4<br /> Tạp chí KHOA HỌC ĐHSP TPHCM Trần Huyên<br /> _____________________________________________________________________________________________________________<br /> <br /> <br /> <br /> <br /> Chứng minh:<br /> Kết luận thứ nhất được suy ra từ kết quả hiển nhiên sau: zai u ≤ zai w ≤ zai v khi<br /> và chỉ khi z ( ai − 1) u ≤ z ( ai − 1) w ≤ z ( ai −1) v và do đó:<br /> <br /> ∆l [ a; b] = ⎡⎣ z ( ai − 1) u; z ( ai − 1) v ⎤⎦<br /> Bởi ∆ hb = max ∆ h [ a; b ] và a ' = zai zl ( k − ai − 1) = min ∆ h [ a; b ] , nên để chỉ ra<br /> ∆ h [ a; b ] là đoạn ta chỉ cần chứng tỏ ⎡⎣ a '; ∆ hb ⎤⎦ ⊂ ∆ h [ a; b ] . Giả sử b = zai bi +1...bt z , khi<br /> đó ∆ hb = zai ... ( bt − 1) z . Lấy phần tử bất kì x ' ∈ ⎡⎣ a '; ∆ hb ⎤⎦ , x ' = zai xi +1...xn < ∆ hb ; Xảy<br /> ra các khả năng sau:<br /> - Khả năng thứ nhất: b j = x j với mọi j < t và xt < bt − 1 .<br /> Khi đó chọn x = zai ... ( xt + 1) ...xn ∈ [ a; b ] thì x ' = ∆ t x , tức x ' ∈ ∆ h [ a; b ] .<br /> - Khả năng thứ hai: tồn tại s mà i < s < t sao cho b j = x j với mọi j < s và<br /> xs < bs .<br /> Trong khả năng này, xảy ra các trường hợp sau:<br /> + Trường hợp thứ nhất: Phần tử x = zai ... ( xs + 1) ...xn ≤ b . Khi đó<br /> x ' = ∆ s x ∈ ∆ h [ a; b ] .<br /> + Trường hợp thứ hai: Phần tử x = zai ... ( xs + 1) ...xn > b . Khi đó ắt tồn tại chỉ số<br /> q, q > s sao cho xj = bj với mọi j < q và xq > bq. Do x=b nên<br /> bq +1 + ... + bt > xq +1 + ... + xn , ắt tồn tại chỉ số p mà q < p ≤ t để bp > xp. Chọn<br /> y = zai ...( x p + 1)...xn thì y ∈ [ a; b ] và x ' = ∆ p y ∈ ∆ h [ a; b ] .<br /> <br /> Vậy trong mọi khả năng và mọi trường hợp có thể xảy ra, bất kì x ' ∈ ⎡⎣ a '; ∆ hb ⎤⎦<br /> đều có x ' ∈ ∆ h [ a; b ] , cho ta kết luận: ∆ h [ a; b ] = ⎡⎣ a '; ∆ hb ⎤⎦ .+<br /> Sử dụng mệnh đề 1, ta đi tới kết quả đáng chú ý sau:<br /> Mệnh đề 2<br /> Trong mức S k cho a = zai u < zai v = b . Khi đó, ∆ [ a; b ] là đoạn khi và chỉ khi<br /> b = zai hi +1 ( k − ai ) z , còn a < a* = zai u * mà zai zl ( k − ai − 1) = ∆ j a * với j ≥ i + 1 .<br /> Chứng minh: Nếu ∆ [ a; b ] là đoạn thì ∆ [ a; b ] = ⎡⎣ ∆ l a; ∆ hb ⎤⎦ .<br /> <br /> <br /> <br /> <br /> 5<br /> Tạp chí KHOA HỌC ĐHSP TPHCM Số 33 năm 2012<br /> _____________________________________________________________________________________________________________<br /> <br /> <br /> <br /> <br /> Dễ thấy z ( ai − 1) hi +1 ( k − ai ) z , zai zl ( k − ai − 1) ∈ ⎡⎣ ∆ l a; ∆ hb ⎤⎦ , buộc các phần tử<br /> zai hi +1 ( k − ai ) và a* = zai u * mà zai zl ( k − ai − 1) = ∆ j a * (với j ≥ i + 1 ) phải thuộc<br /> [ a; b]. Từ đó suy ra b = zai hi +1 ( k − ai ) z và a < a* = zai u * .<br /> Ngược lại, nếu các đầu mút a, b thỏa các điều kiện của mệnh đề 2, trước hết ta sẽ<br /> chỉ ra ∆ [ a; b ] là đoạn. Từ sự phân tích ∆ [ a; b ] = ∆ h [ a; b ] U ∆ l [ a; b ] theo mệnh đề 1,<br /> ∆ l [ a; b ] = ⎡⎣ ∆ l a; ∆ l b ⎤⎦ ; và để ý rằng min ∆ h [ a; b ] = ∆ j a * là trội trực tiếp của ∆l b . Do<br /> đó để chứng minh ∆ [ a; b ] là đoạn ta chỉ cần chứng minh ∆ h [ a*; b ] = ⎡⎣ ∆ j a*; ∆ hb ⎤⎦ .<br /> <br /> Nếu a* = zai zl ( k − ai ) thì ∆ h [ a*; b ] là đoạn theo mệnh đề 1.<br /> <br /> Nếu a* > zai zl ( k − ai ) và x ' ∈ ⎡⎣ ∆ j a*; ∆ hb ⎤⎦ thì có hai khả năng xảy ra sau:<br /> <br /> - Khả năng thứ nhất: x ' ≥ ∆ h a * . Khi đó ắt tồn tại x mà b > x ≥ a * và chỉ số t > j<br /> sao cho ∆ t x = x ' .<br /> - Khả năng thứ hai: x ' < ∆ h a * . Khi đó ắt tồn tại x mà b > x > a * sao cho<br /> ∆ jx = x' .<br /> Như vậy theo hết các khả năng có thể xảy ra ta đều có ⎡⎣ ∆ j a*; ∆ hb ⎤⎦ ⊂ ∆ [ a*; b ] ,<br /> suy ra kết luận. +<br /> Vấn đề sẽ trở nên phức tạp hơn khi các đầu mút a, b không cùng chung tọa độ<br /> khác 0 đầu tiên. Dưới đây ta chỉ xét một vài kết quả liên quan tới các đầu mút a, b đều<br /> có tọa độ khác không đầu tiên cùng thứ i, tuy nhiên ai ≠ bi .<br /> Mệnh đề 3<br /> Trong mức S k cho a = zai u < zbi v = b với ai = bi − 1 ≠ 0 . Nếu<br /> b = zbi hi +1 (k − bi ) z hay a = zai zl ( k − ai ) thì ∆ [ a; b ] là đoạn.<br /> Chứng minh: Nếu b = zbi hi +1 ( k − bi ) z , chọn a ' = zbi zl ( k − bi ) và phân tích<br /> [ a; b] = [ a; a '] U [ a '; b] .<br /> Theo mệnh đề 2: ∆ [ a '; b ] = ⎡⎣ ∆ l a '; ∆ hb ⎤⎦ .<br /> [ ] [ ] [<br /> Khi đó ∆[a ; b] ⊂ ∆l a ; ∆hb = ∆l a ; ∆h a ' ∪ ∆l a' ; ∆hb . ]<br /> Song ∆ [ a; b ] ⊃ ∆ [ a '; b ] U ∆ [ a; a '] ⊃ ⎡⎣ ∆ l a '; ∆ hb ⎤⎦ U ∆ l [ a; a ')<br /> <br /> = ⎡⎣ ∆ l a '; ∆ hb ⎤⎦ U ⎡⎣ ∆ l a; ∆ l a ') = ⎡⎣ ∆ l a; ∆ hb ⎤⎦<br /> <br /> Vậy, ∆ [ a; b ] = ⎡⎣ ∆ l a; ∆ hb ⎤⎦ .<br /> <br /> <br /> <br /> 6<br /> Tạp chí KHOA HỌC ĐHSP TPHCM Trần Huyên<br /> _____________________________________________________________________________________________________________<br /> <br /> <br /> <br /> <br /> Nếu a = zai zl ( k − ai ) , chọn a ' = zai hi +1 ( k − ai ) z , và phân tích<br /> <br /> [ a; b] = [ a; a '] U [ a '; b]<br /> Theo mệnh đề 2: ∆ [ a; a '] = ⎡⎣ ∆ l a; ∆ h a '⎤⎦ .<br /> <br /> Theo mệnh đề 1: ∆ h ( a '; b ] ⊃ ⎡⎣ zbi zl ( k − ai ) ; ∆ hb ⎤⎦ .<br /> <br /> Để ý rằng ∆ h a ' có trội trực tiếp là zbi zl ( k − ai ) nên<br /> <br /> ∆ [ a; b ] = ∆ [ a; a '] U ∆ h [ a '; b ] = ⎡⎣ ∆ l a; ∆ hb ⎤⎦ +<br /> Xem như là hệ quả trực tiếp của mệnh đề 3, ta có:<br /> Mệnh đề 4<br /> Trong mức S k cho a = zai u < zbi v = b với 1 ≤ ai < bi − 1 . Khi đó ∆ [ a; b ] là<br /> đoạn. +<br /> Cuối cùng để kết thúc bài viết, ta lưu ý rằng các kết quả trên được phát biểu cho<br /> các mức S k với độ lớn k thích hợp. Khi độ lớn k khá bé cần có những điều chỉnh nhất<br /> định. Chẳng hạn khi k = 2, ta có các kết quả cụ thể hơn như sau mà việc kiểm chứng<br /> chúng xin được nhường lại cho độc giả.<br /> Mệnh đề 5<br /> Trong mức S 2 cho a < b . Khi đó<br /> i) Nếu ∆ h a = ∆ hb = z1i z thì ∆ [ a; b ] là đoạn khi và chỉ khi hoặc b = z 2i z hoặc<br /> b = z11<br /> i z.<br /> <br /> ii) Nếu ∆ hb = z1i z còn ∆ h a = z1i +t z với t > 1 thì ∆ [ a; b ] = IS ∆ hb .( )<br /> iii) Nếu ∆ hb = z1i z còn ∆ h a = z1i +1 z thì ∆ [ a; b ] = IS ∆ hb ( ) khi và chỉ khi<br /> ∆l b ≥ ∆l a . +<br /> <br /> TÀI LIỆU THAM KHẢO<br /> 1. Anderson, I. (1989), “Combinatorics of finite set”, Clarendon press, Oxford.<br /> 2. Clement, G. F and Lindstrom, B. (1969), “A generalization of a combinatorial<br /> therem of Macaulay”, J. Combinat, Theory 7.<br /> 3. Clement, G. F (1984), “Antichains in the set of subsets of a multiset”, Pariod. Math<br /> Hung, 15.<br /> 4. Tran Huyen, Le Cao Tu (2007), “Some prolem on the shadow of segments in finite<br /> boolean rings”, VNU journal of Science. Math - phys - 23.<br /> <br /> (Ngày Tòa soạn nhận được bài: 26-9-2011; ngày chấp nhận đăng: 27-10-2011)<br /> <br /> <br /> <br /> <br /> 7<br />