Một số vấn đề về K - Poset các tập con của tập đa bội

hau: một là thứ tự bao hàm các tập con của S; hai là thứ tự tuyến tính để so sánh các tập hợp cùng size, sau này được gọi là thứ tự nén. Tập đa bội là tập hợp mà mỗi phần tử của nó có thể lập lại nhiều lần và các tập con của nó có mô hình quen thuộc nhất là các ước nguyên dương của số tự nhiên m nào đó. Nó thực sự rộng hơn họ gồm các tập con của tập đơn bội. Người ta đã mở rộng nhiều tính chất vốn có của họ các tập con tập đơn bội sang họ các tập con tập đa bội và thu được nhiều kết quả đẹp. Trong đó phải kể đến kết quả của hai nhà toán học Clements và Lindstrom vào năm 1969, đã chứng minh được họ các tập con của tập đa bội lập thành một k – poset Luận văn như là sự lý giải về các nội dung trên, được trình bày làm hai chương. Chương I: Kiến Thức Chuẩn bị Phần này, chủ yếu trình bày khái niệm k – poset.. Chương II: Tính k – poset các tập con của tập đa bội Phần này trình bày khái niệm tập đa bội và tính k – poset các tập con của nó. Cuối cùng, tác giả xin gửi: Lời cảm ơn chân thành đến các thầy cô trong trường, đặc biệt là khoa Toán – Tin, đã nhiệt tình giảng dạy và giúp đỡ trong quá trình học tập. Lời cảm ơn sâu sắc đến thầy hướng dẫn đã nhiệt tình quan tâm giúp đỡ tác giả trong quá trình hoàn thành luận văn. Lời cảm ơn đến phòng KHCNSĐH của trường ĐHSP TPHCM đã tạo mọi điều kiện thuận lợi giúp tác giả sớm hoàn thành luận văn. 2 TP. HCM, ngày 08 tháng 08 năm 2011 Tác giả 3 MỤC LỤC 0TLỜI NÓI ĐẦU0T ...................................................................................................................... 1 0TMỤC LỤC0T ............................................................................................................................ 3 0TChương I0T ............................................................................................................................... 4 0TKIẾN THỨC CHUẨN BỊ0T .................................................................................................... 4 0T1. Khái niệm k – poset.0T...................................................................................................... 4 0T2. Tính k – poset các tập con của tập hữu hạn 0T { }S = 1,2, ...,n 0T .0T ..................................... 7 0TChương II0T ........................................................................................................................... 27 0T ÍNH K – POSET CÁC TẬP CON CỦA TẬP ĐA BỘI0T ................................................... 27 0T§1. Khái niệm tập đa bội0T ................................................................................................ 27 0T§2. Tính các k – poset các tập con của tập đa bội0T .......................................................... 32 0TKẾT LUẬN0T ......................................................................................................................... 48 0T ÀI LIỆU THAM KHẢO0T .................................................................................................. 49 4 Chương I: KIẾN THỨC CHUẨN BỊ Chương này chủ yếu giới thiệu khái niệm k – poset. Xem như độc giả đã biết những khái niệm: • Tập hợp cùng các phép toán trên nó như là , , , , \.∪ ∩ ⊂ ⊃ • Các quy tắc phát biểu mệnh đề với các ký hiệu , , ,...∀ ∃∈ • Các quy tắc đếm quy tắc cộng và quy tắc nhân, hai tính chất cơ bản của số k nC như là k n k n nC C −= và 11 1 k k k n n nC C C − − −= + . Một số quy ước trong luận văn: • Thuật ngữ “size” được dùng để chỉ độ lớn của một đối tượng nào đó, ký hiệu . Chẳng hạn như size A, ký hiệu A , là chỉ cho lực lượng tập A. • Tập S luôn hữu hạn, ( )SP là họ gồm tất cả các tập con của S. • Đôi khi, ký hiệu n k       được dùng thay .knC 1. Khái niệm k – poset. Ta nhắc lại khái niệm poset (an partially ordered set) Định nghĩa 1.1. Quan hệ ≤ trên một tập hợp M được gọi là thứ tự bộ phận của nó nếu có tính chất sau đây: i. x x≤ với mọi x M∈ . ii. Nếu x y≤ và y x≤ thì x y= . iii. Nếu x y≤ và y z≤ thì x z≤ . 5 Tập M cùng với thứ tự bộ phận ≤ được gọi là tập hợp được sắp thứ tự bộ phận hay poset và được ký hiệu là ( ),P M= ≤ . Quan hệ ≤ được gọi là quan hệ thứ tự Ta nói ,x y là so sánh được với nhau (comparable) nếu x y≤ hoặc y x≤ . Nếu x y≤ và x y≠ , ta viết x y< và nói: x bé thua y, hoặc x đứng trước y, hoặc x thực sự được chứa trong y. y được gọi là phủ x hay liền sau x nếu x y< và không tồn tại z thỏa x z y< < . z được gọi là phần tử không nếu z là phần tử duy nhất thỏa mãn z x≤ với mọi x M∈ , kí hiệu là 0. z được gọi là phần tử tối tiểu nếu không tồn tại x thỏa x z< . z được gọi là phần tử tối đại nếu không tồn tại x thỏa z x< . M được gọi là tập được sắp tuyến tính nếu mọi phần tử thuộc M đều so sánh được với nhau. M được gọi là tập được sắp tốt nếu mọi bộ phận khác rỗng của M đều chứa phần tử bé nhất. Tất nhiên khi đó M là tập được sắp tuyến tính. Dãy 1 2, , , nx x xK được gọi là xích (chain) hay dây xích nếu 1 2 nx x x< < <K . Chiều dài hay size của xích là số các phần tử trong xích trừ đi 1. Xích 1 2 nx x x< < <K được gọi là bão hòa (saturated chain) nếu 1ix + phủ ix .  Ví dụ 1.1. Nếu { }1,2,3,...,S n= thì ( )( ),S ⊆P là poset, với ∅ là phần tử 0, xích bão hòa là các xích 1 2 hA A A⊂ ⊂ ⊂K thỏa 1 1i iA A+ = + với mọi 1 1i h≤ ≤ − chẳng hạn như { } { } { }1 1,2 1,2,...,h⊂ ⊂ ⊂K .  Một số poset ( ),P M= ≤ có tính chất sau: 6 Với mọi x y< , tất cả xích bão hòa từ x đến y có cùng số lượng phần tử trong sự biểu diễn của xích tức là mọi xích bão hòa từ x đến y có cùng size (size đó chỉ phụ thuộc vào x, y). Đặc biệt, mọi xích bão hòa từ 0 đến x có cùng size. Đối với những poset như trên, ta định nghĩa hạng hay size của phần tử x là size mọi xích bão hòa từ 0 đến x, ký hiệu ( )r x hoặc x . Khi đó, ta nói ( ),P M= ≤ là poset có hạng với hàm hạng là ( )r x x= . Ví dụ 1.2. Với { }1,2,3,...,S n= , ( )( ),S ⊆P là poset có hạng với hàm hạng ( )r A A= là size của tập hợp A.  Định nghĩa 1.2. Cho ( ),M ≤ là poset có hạng với hàm hạng ( )r x x= . { }:kM x M x k= ∈ = được gọi là mức hạng k của M. { }: 1,a x M x a x a∆ = ∈ = − < được gọi là bóng của phần tử a M∈ Nếu kA M⊂ thì tập a A A a ∈ ∆ = ∆U được gọi là bóng của A. Khi đó, 1kA M −∆ ⊂  Ví dụ 1.3. Với { }1,2,3,4,5S = , poset ( )( ),S ⊆P có { } { } { }{ } 31,2,3 , 2,3,4 , 1,3,5 M= ⊂A { } { } { } { } { }{ } { }{ } 21,2 , 1,3 , 2,3 , 2,4 , 3,4 1,5 , 3,5 M∆ = ⊂A  Khi ( ),M ≤ là poset có hạng thì size của x sẽ không bằng size của y nếu hai phần tử ,x y là so sánh được với nhau (vì x y< nếu x y< ). Do đó, thứ tự của poset không thể so sánh các phần tử trên cùng mức hạng k. 7 Định nghĩa 1.3. Cho M là poset có hạng mà trên mỗi kM , ta trang bị thứ tự tuyến tính p . Nếu A là bộ phận trong mức hạng k của M thì tập gồm A phần tử đầu tiên có size k theo thứ tự p được gọi là cái nén của A, ký hiệuCA . A được gọi là nén hay đoạn đầu nếu A CA=  Định nghĩa 1.4. Poset có hạng M, trên mỗi mức kM được trang bị thứ tự tuyến tính p , được gọi là k – poset nếu nó thỏa mãn thêm hai điều kiện sau: 1. A∆ là đoạn đầu nếu A là đoạn đầu 2. ( ) ( )CA C A∆ ⊆ ∆ với A là bộ phận tùy ý trong mức hạng k của M. Điều đó có nghĩa là bóng của đoạn đầu có size bé nhất trong tất cả các bộ phận trong mức hạng k có cùng lực lượng.  Phần còn lại của chương I, luận văn trình bày về tính k – poset của họ các tập con của tập hữu hạn { }1,2,...,S n= , cho ta ví dụ về k – poset. 2. Tính k – poset các tập con của tập hữu hạn { }S = 1,2, ...,n . Trước hết, luận văn giới thiệu một số thứ tự trên mức hạng k. Định nghĩa 1.5. Cho { }1,2,...,S n= , A, B là tập con của S có cùng size k. Khi đó A được gọi là nhỏ hơn B theo thứ tự từ điển (lexicographic order) nếu phần tử bé nhất của tập hợp ( ) ( )' 'A B A B A B∆ = ∩ ∩U thuộc về A, ký hiệu .LA B<  8 Ví dụ 1.4. Theo thứ tự từ điển, các tập con size 3 của { }1,2,3,4,5S = là { } { } { } { } { } { } { } { }1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5L L L L L L L L< < < < < < < < { } { }2,4,5 3,4,5 .L L< <  Một cách tương tự, ta có thứ tự từ điển ngược. Định nghĩa 1.6. Cho { }1,2,...,S n= , A, B là tập con của S có cùng size k. Khi đó A được gọi là nhỏ hơn B theo thứ tự từ điển ngược (antilexicographic order) nếu phần tử lớn nhất của tập hợp ( )'A B A B∆ = ∩ U ( )'A B∩ thuộc về A, ký hiệu .AA B<  Ta có thể đạt được thứ tự từ điển ngược từ thứ tự từ điển. Giả sử { } { }1 2 1 2, ,..., , , ,..., ,k kA a a a B b b b= = trong đó 1 1, 1, 1i i i ia a b b i k+ +> > ∀ ∈ − . Đặt { }1 21 , 1 ,..., 1 ,kA n a n a n a= + − + − + − { }1 21 , 1 ,..., 1 kB n b n b n b= + − + − + − Rõ ràng .A LA B A B< ⇔ < Ví dụ 1.5. Theo thứ tự từ điển ngược, các tập con size 3 của { }1,2,3,4,5S = gồm có { } { } { } { } { } { } { } { }5,4,3 5,4,2 5,4,1 5,3,2 5,3,1 5,2,1 4,3,2 4,3,1A A A A A A A< < < < < < < { } { }4,2,1 3,2,1 .A A< <  Thứ tự mà ta sẽ dùng là đảo ngược vị trí các phần tử trong thứ tự từ điển ngược. 9 Định nghĩa 1.7. Cho { }1,2,...,S n= , A, B là tập con của S có cùng size k. Khi đó A được gọi là nhỏ hơn B theo thứ tự nén hay thứ tự dồn (Squashed order) nếu phần tử lớn nhất của tập hợp ( )'A B A B∆ = ∩ U ( )'A B∩ thuộc về B, ký hiệu .SA B<  Ví dụ 1.6. Từ ví dụ 1.5, các tập con size 3 của { }1,2,3,4,5S = theo thứ tự nén gồm { } { } { } { } { } { } { } { }1,2,3 1,2,4 1,3,4 2,3,4 1,2,5 1,3,5 2,3,5 1,4,5S S S S S S S< < < < < < < { } { }2,4,5 3,4,5S S< < .  Để thuận lợi khi sử dụng thứ tự nén, người ta biểu diễn các tập con bất kỳ của S thành các dãy nhị phân, tức là dãy chỉ có hai phần tử là 0 và 1. Ví dụ như, tập con { }1,3,4A = của { }1,2,3,4,5S = có biểu diễn là 10110, tập con { }1,2,4,7B = của { }1,2,3,4,5,6,7S = có biểu diễn là 1101001. Cơ số 1 sẽ ở vị trí thứ i nếu i xuất hiện trong tập hợp, cơ số 0 ở các vị trí còn lại. Ví dụ 1.7. Từ ví dụ 1.6, các tập con size 3 của { }1,2,3,4,5S = theo thứ tự nén được đại diện bởi hai cột sau (Ở cột thứ nhất, tập hợp được viết theo kiểu thông thường; ở cột thứ hai, nó được đại diện bằng chuỗi nhị phân tương ứng) 1 2 3 1 1 1 0 0 phần tử đầu tiên 1 2 4 1 1 0 1 0 phần tử thứ hai 1 3 4 1 0 1 1 0 phần tử thứ ba 2 3 4 0 1 1 1 0 phần tử thứ bốn 1 2 5 1 1 0 0 1 phần tử thứ năm 1 3 5 1 0 1 0 1 phần tử thứ sáu 2 3 5 0 1 1 0 1 phần tử thứ bảy 10 1 4 5 1 0 0 1 1 phần tử thứ tám 2 4 5 0 1 0 1 1 phần tử thứ chín 3 4 5 0 0 1 1 1 phần tử thứ mười  Ví dụ 1.8. Tìm vị trí của tập { }2,3,6,7A = trong thứ tự nén của mức hạng 4. Dãy nhị phân biểu diễn của A là 0110011 (A có bốn cơ số 1, ba cơ số 0) Số 1 cuối cùng nằm ở vị trí thứ 7 chứng tỏ A đứng sau tất cả các tập size 4 mà cơ số 0 ở vị trí thứ 7, số lượng những tập này là 46C . Những tập hợp đứng trước A và đứng sau 46C tập hợp đó đều có cơ số 1 ở vị trí thứ 7. Như vậy, ta chỉ cần tìm vị trí của 011001 trong thứ tự nén của mức hạng 3. Tương tự 011001 đứng sau 35C tập hợp có size 3 mà cơ số 0 ở vị trí thứ 6. Và ta chỉ cần tìm vị trí của 011 trong thứ tự nén của mức hạng 2. Tất nhiên nó là dãy cuối cùng trong tất cả các tập hợp size 2 của 3 phần tử tức nó đứng thứ 23C . Vậy A đứng thứ 4 3 26 5 3 15 10 3 28C C C+ + = + + = trong thứ tự nén của mức hạng 4.  Bây giờ, ta khẳng định tính k – poset của ( )SP tức chứng minh nó thỏa mãn hai điều kiện đã nêu trong định nghĩa 1.4. Nhưng ta sẽ cần kết quả sau: Định lý 1.1. Cho hai số nguyên dương m và k. Khi đó, tồn tại duy nhất một đại diện của m có dạng 1 1... 1 1 k k t ta a a am k k t t − +       = + + + +       − +        trong đó 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ . 11 Đại diện này còn được gọi là đại diện k – nhị thức của m. Chứng minh định lý 1.1. • Sự tồn tại. Một đại diện của m có thể dễ dàng tìm được bằng cách chọn ka là số nguyên dương lớn nhất thỏa mãn .k a m k   ≤    Nếu ,k a m k   <    chọn 1ka − là số nguyên dương lớn nhất thỏa mãn 1 1 k ka am k k −   ≤ −   −    . Nếu 1k ka a− ≥ thì 1 1 k ka am k k −   ≥ + ≥   −    1 1 k k ka a a k k k +      + =     −      , mâu thuẫn với cách chọn ka , hay 1k ka a− < . Nếu 1 1 k ka am k k −   < −   −    hay 10 1 k ka am k k −   < − −   −    , chọn 2ka − là số nguyên dương lớn nhất thỏa mãn 2 1 2 1 k k ka a am k k k − −     ≤ − −     − −      . Nếu 2 1k ka a− −≥ thì 1 1 k ka am k k −   ≥ +   −    2 1 1 1 1 2 1 2 1 k k k k k ka a a a a a k k k k k k − − − − +           + ≥ + + = +           − − − −            , mâu thuẫn với cách chọn 1ka − , hay 2 1k ka a− −< . Do m hữu hạn nên quá trình trên sẽ dừng sau hữu hạn bước và ta tìm được ta với 1t ≥ thỏa mãn 12 1 1... 1 1 t k k ta a a am t k k t − +       = − + + +       − +        hay 1 1... 1 1 k k t ta a a am k k t t − +       = + + + +       − +        , trong đó 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ . • Tính duy nhất Dùng quy nạp. Với 1k = , m có đúng một đại diện là 1 m m  =     . Nếu m có đúng một đại diện ( )1k − – nhị thức thì nó có đúng một đại diện k – nhị thức. Thật vậy, giả sử m có hai hình thức đại diện k – nhị thức. 1 1... ... 1 1 k k t k k ra a a b b bm k k t k k r − −           = + + + = + + +           − −            , 1, 1t r≥ ≥ Nếu k ka b= thì 1 1... ... 1 1 k t k ra a b b k t k r − −       + + = + +       − −        là đại diện ( )1k − – nhị thức của số tự nhiên 'm nào đó. Theo giả thiết quy nạp, , i it r a b= = với mọi { }, 1 , 1,..., 1i t k t t k∈ − = + − Do đó, chỉ cần xét k ka b≠ . Không mất tính tổng quát, giả sử k ka b< . Theo tính chất 1 1 n n n i i i +      + =     −      của hệ số nhị thức, rõ ràng 13 1 1 1 1 ... 1 1 2 1 0 n n n n n n n n n i i i i i i i i i + − − − −                  = + = + + = + + +                 − − − −                  Suy ra 1 1 1 ... 1 1 0 k k k k ka a a a k a k k k k + − − + −          = + + + +         −          . Ta có k ka b< kéo theo 1k ka b+ ≤ kéo theo 1k ka b m k k +    ≤ ≤        . Mặt khác, 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ suy ra 1 1 21 , 2 1 , ...,k k k k ka a a a a− − −− ≥ − ≥ − ≥ ( )k ta k t a− − ≥ . Điều này dẫn đến mâu thuẫn vì 1 ... 1 1 ... 1 1 1 ... ... 1 1 0 1 1 1 k k t k k k k k k k k k k a a a m k k t a a a k t k k t a a a k t a k a k k k t a a m k k −     = + + + ≤     −      − − +      ≤ + + + ≤     −      − − + − + −          ≤ + + + + + +         −          + +    ≤ − < ≤        hay !m m< Mâu thuẫn chứng tỏ không thể xảy ra k ka b≠ . Vậy, đại diện k – nhị thức của m là duy nhất.  Ví dụ 1.9 Lấy 26, 4,m k= = x lớn nhất để 26 4 x  ≤    là 6,x = 14 y lớn nhất để 6 26 11 3 4 y    ≤ − =        là 3y = Suy ra 6 5 6 5 2 26 1 4 3 4 3 2           = + + = + +                    .  Cái ta cần ở định lý 1.1 là xác định tập hợp thứ m theo thứ tự nén trong mức hạng k. Ví dụ 1.10. Cho { }1,2,3,4,5,6,7S = , ta xác định tập hợp size 4 đứng thứ 26 theo thứ tự nén trong mức hạng 4. Theo ví dụ 1.9, 6 5 2 26 4 3 2       = + +            Theo thứ tự nén của mức hạng 4, ta có 6 4       tập hợp đầu tiên là các tập con size 4 của { }1,2,3,4,5,6 5 3       tập hợp tiếp theo là các tập con size 3 của { }1,2,3,4,5 nhưng thêm vào phần tử 7 2 1 2   =    tập hợp tiếp theo là tập { }1,2,6,7 Vậy, tập hợp cần tìm là { }1,2,6,7 ứng với dãy 1100011  Tổng quát, ta có định lý sau: Định lý 1.2. Cho m là số nguyên dương bất kỳ có đại diện k – nhị thức là 15 1 1... 1 1 k k t ta a a am k k t t − +       = + + + +       − +        trong đó 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ . Khi đó, trong mức hạng k, tập hợp size k đứng thứ m theo thứ tự nén là { }1 11, 1,..., 1, , 1, 2,..., 2, 1k k t t t t t ta a a a a a a t a t− ++ + + − − − + − + Chứng minh định lý 1.2. Tương tự như ví dụ 1.10, theo thứ tự nén, trong mức hạng k có ka k       tập hợp đầu tiên là các tập con size k của { }1,2,..., ka 1 1 ka k −   −  tập hợp tiếp theo là các tập con size ( )1k − của { }11,2,..., ka − và thêm vào phần tử 1ka + 2 2 ka k −   −  tập hợp tiếp theo là các tập con size ( )2k − của { }21,2,..., ka − nhưng thêm vào hai phần tử { }11, 1k ka a −+ + … Cứ như thế cho đến 1 1 ta t +   +  các tập con size ( )1t + của { }11,2,..., ta + nhưng thêm vào các phần tử { }1 21, 1,..., 1k k ta a a− ++ + + ta t       tập hợp cuối cùng chính là các tập con size t của { }1,2,..., ta và thêm vào các phần tử { }1 11, 1,..., 1k k ta a a− ++ + + Nhưng tập con size t cuối cùng của { }1,2,..., ta là { }, 1, 2,..., 2, 1t t t t ta a a a t a t− − − + − + 16 Do đó tập hợp size k đứng thứ m là { }1 11, 1,..., 1, , 1, 2,..., 2, 1k k t t t t t ta a a a a a a t a t− ++ + + − − − + − +  Ví dụ 1.11. Năm 1964, Lehmer đưa ra bài toán: Cho { }1,2,3,...,20S = xác định vị trí của { }1,2,4,5,8,10,11,12,13,15,16,18A = theo thứ tự từ điển của mức hạng 12. Vị trí của A theo thứ tự từ điển là vị trí của tập hợp { }21 :B a a A= − ∈ = { }20,19,17,16,13,11,10,9,8,6,5,3 theo thứ tự từ điển ngược. Theo định lý 1.2, vị trí của B theo thứ tự nén là 19 18 16 15 12 10 9 12 11 10 9 8 7 6 r              = + + + + + + +                            8 7 5 4 3 96034 5 4 3 2 1           + + + + + =                    . Gọi m là vị trí của B theo thứ tự từ điển ngược Theo định nghĩa của thứ tự từ điển ngược và thứ tự nén, 20 1 1 125971 12 n m r k     + = + = + =        . Suy ra 125971 125971 96034 29937m r= − = − = Vậy vị trí của { }1,2,4,5,8,10,11,12,13,15,16,18A = theo thứ tự từ điển (của mức hạng 12) là 29937. 17  ( )SP thỏa mãn điều kiện thứ nhất của k – poset. Định lý 1.3. Cho A là bộ phận trong mức hạng k của ( )SP . Nếu A là đoạn đầu thì ∆A cũng là đoạn đầu. Chứng minh định lý 1.3. Theo định lý 1.1, A có đại diện k – nhị thức là 1 ... 1 k k ta a am k k t −     = + + +     −      trong đó 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ Theo định lý 1.2, vị trí thứ A theo thứ tự nén là của tập hợp { }1 11, 1,..., 1, , 1, 2,..., 2, 1k k t t t t t tA a a a a a a a t a t− += + + + − − − + − + . Do đó, nếu A là đoạn đầu thì A gồm tất cả các tập hợp size k mà vị trí của chúng không thể đứng sau A. Các tập hợp đó chính là m tập hợp được liệt kê ở định lý 1.2, cụ thể gồm ka k       tập hợp con đầu tiên có size k bằng cách lấy tất cả các tập size k của { }1,2,..., ka 1 1 ka k −   −  tập hợp con size k tiếp theo bằng cách lấy tất cả các tập size ( )1k − của { }11,2,..., ka − nhưng thêm vào phần tử 1ka + …, Như thế cho đến t a t       tập hợp con size k cuối cùng là lấy lấy tất cả các tập size t của { }1,2,..., ta nhưng thêm vào các phần tử { }1 11, 1,..., 1k k ta a a− ++ + + . 18 Khi đó, ∆A gồm các tập hợp sau: 1 ka k    −  tập hợp con size ( )1k − của { }1,2,..., ka 1 2 ka k −   −  tập hợp con size ( )2k − của { }11,2,..., ka − nhưng thêm vào phần tử { }1ka + 2 3 ka k −   −  tập hợp con size ( )3k − của { }21,2,..., ka − nhưng thêm vào phần tử { }11, 1k ka a −+ + , …, Cuối cùng là 1 ta t    −  tập hợp con size ( )1t − của { }1,2,..., ta nhưng thêm vào phần tử { }1 11, 1,..., 1k k ta a a− ++ + + . Rõ ràng, ∆A chứa đúng 1 ... 1 2 1 k k ta a a k k t −     + + +     − − −      tập hợp đầu tiên trong thứ tự nén của mức hạng 1k − . Vậy, ∆A là đoạn đầu.  Vấn đề còn lại là chứng minh bóng của đoạn đầu có size bé nhất trong tất cả các bộ phận trong mức hạng k có cùng lực lượng. Theo định lý 1.3, nếu đoạn đầu có size 1 ... 1 k k ta a am k k t −     = + + +     −      thì bóng của nó có size bằng 19 1 ... 1 2 1 k k ta a a k k t −     + + +     − − −      Do đó, điều cần chứng minh là 1 ... 1 2 1 k k ta a a k k t −     ∆ ≥ + + +     − − −      A nếuA là bộ phận tùy ý trong mức hạng k của ( )SP có size m. Định lý 1.4. (Kruskal 1963, Katona 1966a) Cho { }1,2,...,S n= , { }1 2, ,..., mA A A=A là bộ phận trong mức hạng k của ( )SP . Giả sử, đại diện k – nhị thức của m là 1 ... 1 k k ta a am k k t −     = + + +     −      trong đó 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ . Khi đó 1 ... 1 2 1 k k ta a a k k t −     ∆ ≥ + + +     − − −      A  Chứng minh định lý trên cần dùng đến toán tử treo. Toán tử này làm biến đổi các tập hợp từ một phần tử riêng của S, phần tử riêng được chọn ở đây là phần tử 1. Với A là bộ phận trong mức hạng k của ( )SP , 1 j n< ≤ . Khi đó, với mọi A∈A , định nghĩa: ( ) { }( ) { }\ 1jS A A j= U nếu { }( ) { }, 1 , \ 1j A A A j∉ ∈ ∉U A và ( )jS A A= đối các tập hợp còn lại. jS được gọi là toán tử treo (treo trên phần tử 1). Rõ ràng, ( ) ( ){ }:j jS S A A= ∈A A 20 cũng là bộ phận trong mức hạng k và lực lượng của nó bằng lực lượng của A . Nhưng, bóng của ( )jS A không lớn hơn bóng của A . Định lý 1.5. Cho A là bộ phận trong mức hạng k của ( )SP và 1 j n< ≤ . Khi đó, ( )jS∆ ≤ ∆A A . Chứng minh định lý 1.5. Ta có ( )jS∆ ≤ ∆A A khi và chỉ khi ( ) ( )\ \j jS S∆ ∆ ≤ ∆ ∆A A A A khi và chỉ khi tồn tại đơn ánh ( ) ( ): \ \j jS Sϕ ∆ ∆ ∆ ∆aA A A A . Đơn ánh ϕ xác định như sau: Với mọi ( ) \ ,jX S∈∆ ∆A A Ta có ( ) ,jX S X∈∆ ∉∆A A kéo theo tồn tại A∈A để ( ) ,jX S A X A⊂ ⊄ kéo theo ( )jS A A≠ hay ( ) { }( ) { }\ 1jS A A j= U kéo theo ( ) { }( ) { }\ 1jX S A A j⊂ = U kéo theo .j X∉ Nếu 1 X∉ thì { }\ !X A j A⊂ ⊂ vô lý. Do đó 1 X∈ và { }{ } { } { }{ } { }\ 1 \Y X j A j j A= ⊂ = ∈U U A hay Y ∈∆A Ta chứng minh không xảy ra trường hợp ( )jY S∈∆ A . 21 Phản chứng, giả sử ( )jY S∈∆ A tức tồn tại B∈A sao cho ( )jY S B⊂ . Trong trường hợp này, ta chứng minh ( ) { }( ) { }\ 1jS B B j= U . Thật vậy, giả sử điều đó không đúng tức ( )jS B B= hay ( )jj Y S B B∈ ⊂ = kéo theo .j B∈ Nếu 1 B∈ thì { }{ } { } { }\ 1 1X Y j B B= ⊂ = ∈U U A hay !X ∈∆A vô lý. Do đó, , 1 , j B B∉ ∈ ( )jS B B= . Theo cách xác định toán tử treo, { }( ) { }\ 1B j ∈U A kéo theo { }{ } { } { }{ } { }\ 1 \ 1X Y j B j= ⊂ ∈U U A kéo theo !X ∈∆A vô lý. Mâu thuẫn này chứng tỏ ( ) { }( ) { }\ 1jS B B j= U Khi đó, ( ) { }( ) { }\ 1jj Y S B B j∈ ⊂ = U cũng là điều vô lý! Vậy ( )jY S∉∆ A tức ( )\ jY S∈∆ ∆A A . Đặt ( )X Yϕ = , tất nhiên ϕ là ánh xạ. Ngoài ra, ϕ còn là đơn ánh bởi vì nếu tồn tại ( )1 2, \ jX X S∈∆ ∆A A thỏa mãn ( ) ( )1 2X Xϕ ϕ= thì 22 { }{ } { } { }{ } { }1 2\ 1 \ 1X j X j=U U hay 1 2X X= (vì 1 2, X X đều chứa 1 và không chứa j).  Lưu ý rằng: jS chỉ có thể làm biến đổi các tập A∈A mà 1 A∉ . Nếu ( ) { }( ) { }\ 1jS A A j= U thì ( )jS A chứa phần tử 1 suy ra ( )( ) ( )i j jS S A S A= với mọi 1i > . Vì vậy, đặt ( ) ( )1 2 2 1 1 1, , ..., * n n nS S − −= = = =A A A A A A A , ta có ( )* *jS =A A với mọi 2,3,...,j n= . Tất nhiên *=A A . Theo định lý 1.5, ( )1 1 1 1* ... .n n n nS − − −∆ = ∆ = ∆ ≤ ∆ ≤ ≤ ∆ = ∆A A A A A A Do đó, chỉ cần chứng minh định lý 1.4 đối với *A thay vì A . Nhưng, ta sẽ cần đến kết quả sau: Định lý 1.6. Cho A là bộ phận trong mức hạng k của ( )SP sao cho ( )jS =A A với mọi 1 j n< ≤ . Đặt { } { }0 1:1 , :1A A A A= ∈ ∉ = ∈ ∈A A A A { }{ }1 1\ 1 :A A= ∈B A Khi đó 1 0⊃ ∆B A và 1 1∆ = + ∆A B B . Chứng minh định lý 1.6. Trước hết, ta chứng minh 1 0⊃ ∆B A . 23 Lấy 0E∈∆A , ta có 1 E∉ kéo theo tồn tại , 1 i S i∈ > sao cho { } 0E i ∈ ⊂U A A . Vì ( )jS =A A với mọi 1 j n< ≤ nên áp dụng j i= ta được { }( ) { }iS E i E i=U U kéo theo { }1E =U { }( ) { } { }\ 1E i i ∈U U A kéo theo { } 11E ∈U A kéo theo 1E∈B . Vậy 1 0⊃ ∆B A . Bây giờ, ta chứng minh 1 1∆ = + ∆A B B . Theo định nghĩa 1 1, A B ta có 1 1 0∆ ⊃ ⊃ ∆A B A suy ra ( )0 1 0 1 1∆ = ∆ = ∆ ∆ = ∆U UA A A A A A Đặt { }1 1 :1A A= ∈∆ ∈C A . Vì { }{ } { }1 1 1\ 1 : :1A A A A= ∈ = ∈∆ ∉B A A nên 1 1 = ∅IB C mà 1 1 1∆ = UA B C kéo theo 1 1 1∆ = +A B C . Đặt { }{ } { }1 1 1\ 1 : :1A A A A= ∈ = ∈∆ ∉D C C , ta chứng minh 1 1= ∆D B Với mọi 1A∈D , Ta có { } 11A ∈U C kéo theo tồn tại 1l > sao cho { } { }1A l ∈U U A hay { } 1A l ∈U B kéo theo 1A∈∆B . 24 Ngược lại, với mọi 1A∈∆B , tồn tại 1t > sao cho { }A tU 1∈B kéo theo { } { } 11A t ∈U U A kéo theo { } 11A ∈U C kéo theo 1A∈D . Vậy 1D 1= ∆B suy ra 1 1 1= = ∆C D B suy ra 1 1 1 1 1∆ = ∆ = + = + ∆A A B C B B .  Chứng minh định lý 1.4. (Frank 1984) Không mất tính tổng quát, giả sử ( )jS =A A với mọi 2j ≥ . Gọi 0 1 1, , A A B là các bộ phận của ( )SP được xác định như trong định lý 1.6. Dùng quy nạp theo , S n k= và m=A . Định lý đúng với 1S = (trong trường hợp này, m và k chỉ có thể bằng 1). Giả sử nó đúng với 1,2,..., 1S n= − , ta chứng minh nó đúng với S n= . Nếu 1 = ∅A thì A trở thành hệ gồm các tập con của tập { }\ 1S với { } { }\ 1 2,3,..., 1S n n= = − . Theo giả thiết quy nạp, tất nhiên định lý đúng. Vậy, chỉ cần xét 1 ≠ ∅A hay 1 0>A . Lúc này, quy nạp theo k Tất nhiên định lý đúng với 1k = . Giả sử nó đúng với 1,2,..., 1k − , ta phải chứng minh nó đúng với k . Sau đó, quy nạp theo m. Hiển nhiên định lý đúng với 1m = . Giả sử nó đúng với 1,2,..., 1m= −A , ta chứng minh nó đúng với m. Bây giờ, ta chứng minh 1 1 1 ... 1 1 k ta a k t − −    ≥ + +   − −    A , 25 trong đó 1 ... 1 k k ta a am k k t −     = = + + +     −      A và 1 1... 1k k t ta a a a t− +> > > > ≥ ≥ . Thật vậy, giả sử điều đó là không đúng tức 1 1 1 0 ... 1 1 k ta a k t − −    < < + +   − −    A . Vì 0 1= +A A A hay 0 1= −A A A nên 0 1 1 ... 1 1 1 1 ... k k t t k t a a a a m k k t t a a k t    − −        > > − + + −          − −           − −    = + +        A Theo định lý 1.6, 1 0⊃ ∆B A Suy ra 1 1 0= ≥ ∆A B A . Theo giả thiết quy nạp (của m), 0 1 1 1 ... 1 1 k ta a k t − −    ∆ ≥ + + >   − −    A A ! mâu thuẫn. Do đó, 1 1 1 1 ... 1 1 k ta a k t − −    = ≥ + +   − −    B A . Giả thiết quy nạp (của k) khẳng định 1∆ ≥B 1 1 ... 2 2 k ta a k t − −    + +   − −    . Theo định lý 1.6, 1 1 1 1 1 1 ... 1 2 1 2 k k t ta a a a k k t t    − − − −        ∆ = + ∆ ≥ + + + +          − − − −           A B B 26 ... 1 1 k ta a k t     ≥ + +   − −    . Định lý đã được chứng minh.  Vậy, ( )SP là k – poset. 27 Chương II TÍNH K – POSET CÁC TẬP CON CỦA TẬP ĐA BỘI Chương II của luận văn trình bày về tính k – poset các tập con của tập đa bội. Trước hết ta tìm hiểu khái niệm tập đa bội. §1. Khái niệm tập đa bội Tập hữu hạn n phần tử { }1,2,...,S n= đôi khi còn được gọi là tập đơn bội. Tập đa bội được hiểu một cách nôm na là tập hợp mà các phần tử được lập lại nhiều lần. Chẳng hạn như tập hợp 1 2 1,1,...,1,2,2,...,2,..., , ,..., nk k k M n n n   =      1 2 3 14 2 43 14 2 43 28 có phần tử 1 được lập lại 1k lần, phần tử 2 được lập lại 2k lần, …, phần tử n được lập lại nk lần. Để tường minh, ta sẽ nhìn nhận tập hợp theo một mô hình khác. Cho { }1,2,3,...,S n= , gọi 1 2, ,..., np p p là các số nguyên tố đôi một khác nhau. Đặt 1 2... n i n i m p p p p= =∏ , Khi đó, mọi ước số tự nhiên của m có dạng 1 2 1 2 ... n tt t nl p p p= với { }0,1it ∈ . Như vậy ước số l của m có thể được đại diện bằng chuỗi nhị phân 1 2 ... nt t t , chuỗi này ứng với một tập hợp con của S. Điều đó có thể tóm gọn như sau: { } 1 21 21,2,3,..., ... ntt tA nA S n l p p p⊂ = ↔ = trong đó i A∈ nếu 1it = . Rõ ràng, A B⊂ khi và chỉ khi Al là ước của Bl , quan hệ bao hàm trong tập hợp tương ứng với quan hệ chia hết của vành các số tự nhiên. Ví dụ 2.1.1. Với 3n = , các tập hợp con của S là { } { } { } { } { }, 1 , 2 , 3 , 1,2 , 1,3 ,∅ { } { }2,3 , 1,2,3 tương ứng với các ước số của 1 2 3p p p là 1 2 3 1 2 1 31, , , , , ,p p p p p p p 2 3 1 2 3,p p p p p .  Ta có thể đồng nhất họ tất cả các tập con của S với tập tất cả các ước số của một số tự nhiên m nào đó, đồng nhất quan hệ bao hàm của tập hợp với quan hệ chia hết của 29 số tự nhiên. Lưu ý rằng, m trong trường hợp này không có ước là số chính phương khác 1. Bây giờ, giả sử m là một số tự nhiên bất kỳ mà 1 2 1 2 ... n kk k nm p p p= , trong đó ik là các số nguyên dương, 1 2, ,..., np p p là các số nguyên tố đôi một khác nhau. Khi đó, ước số tự nhiên của m có dạng 1 2 1 2 ... n xx x nl p p p= với { }0,1,...,i ix k∈ , 1 i n≤ ≤ . Rõ ràng, số tự nhiên m tương ứng với tập 1 2 1 1 1 2 2 2, ,..., , , ,..., ,..., , ,..., n n n n k k k p p p p p p p p p         1 4 2 4 3 1 4 2 4 3 1 4 2 4 3 còn ước s._.