Thứ tự yếu

Trong toán học, đặc biệt là trong lý thuyết thứ tự, thứ tự yếu (hay quan hệ thứ tự yếu) là một hình thức hóa khái niệm hạng của một tập hợp, trong đó một số phần tử ngang hàng với nhau. Thứ tự yếu là dạng tổng quát của tập sắp thứ tự toàn phần (không có cặp phần tử nào ngang nhau) còn dạng tổng quát của nó là tập hợp sắp thứ tự một phần (nghiêm ngặt) và tiền thứ tự. 

Có nhiều cách khác nhau dùng để hình thức hóa thứ tự yếu, và đặc biệt là mỗi cách này đều có thể biến đổi thành cách khác khác mà không làm mất thông tin: chúng có thể coi là các thứ tự yếu nghiêm ngặt (tập sắp thứ tự một phần trong đó tính không so sánh được là quan hệ bắc cầu), hoặc là tiền thứ tự toàn phần (quan hệ hai ngôi có tính bắc cầu sao cho tồn tại ít nhất một trong hai quan hệ khả thi cho mọi cặp phần tử) hoặc là các phân hoạch được sắp (phân hoạch các phần tử thành các tập con không giao nhau đôi một, cùng với thứ tự toàn phần trên các tập con đó). Ngoài ra trong nhiều trường hợp còn có biểu diễn khác gọi là sắp xếp ưu tiên dựa trên hàm thỏa dụng.

Số thứ tự yếu được đếm theo số Bell được sắp. Trong khoa học máy tính, chúng là một phần của các thuật toán mịn hoá phân hoạch và trong thư viện chuẩn C++.

== Các ví dụ ==
Trong đua ngựa, dùng biện pháp chụp ảnh khi chạm đích có thể loại trừ đi một số nhưng không phải tất cả các trường hợp hoà nhau. Lấy ví dụ từ giải Maryland Hunt Cup trong 2007, con Bruce chạm đích đầu tiên, nhưng hai con sau Bug River và Lear Charm hoà nhau ở vị trí thứ hai, và trong đám ngựa còn lại có ba con không chạm vạch đích. Sử dụng thứ tự yếu để mô tả kết quả này, con Bruce sẽ đứng đầu, Bug River và Lear Charm sẽ đứng đằng sau Bruce nhưng trước các con ngựa còn lại, còn ba con ngựa chưa chạm đích sẽ nằm ở vị trí cuối bảng và hoà với nhau.

Các điểm trong mặt phẳng Euclid có thể sắp được thứ tự theo khoảng cách Euclid từ điểm đó đến gốc, đưa ra một ví dụ về thứ tự yếu của vô số các phần tử, vô số các tập con có các phần tử ngang nhau (tập các phần tử nằm chung một đường tròn có tâm ở gốc toạ độ) và vô số điểm nằm trong các tập con đó. Mặc dù thứ tự yếu này có phần tử nhỏ nhất (chính là gốc toạ độ), nó không có phần tử nhỏ thứ nhì hay phần tử lớn nhất.

Thăm dò ý kiến trong các cuộc bầu cử là một ví dụ khác về loại thứ tự trông giống với thứ tự yếu, nhưng nên được mô hình hoá theo cách khác. Trong kết quả của một cuộc thăm dò, ứng cử này có thể hơn hẳn một ứng cử kia hoặc có thể có hai ứng cử ngang nhau theo thống kê (tức là chúng có thể không bằng nhau nhưng chúng nằm trong giới hạn sai số của nhau). Tuy nhiên, nếu theo thống kê, ứng cử formula_1 ngang với formula_2 và ứng cử formula_3 ngang với formula_4 thì vẫn tồn tại trường hợp ứng cử formula_1 hơn hẳn so với ứng cử formula_4 do vậy ngang nhau theo thống kê không phải quan hệ bắc cầu. Do đó, khi xếp hạng các mô hình như thế, ta nên dùng nửa thứ tự thay vì thứ tự yếu.

== Tiên đề hoá ==
Giả sử rằng formula_7 là quan hệ hai ngôi thuần nhất trên tập hợp formula_8 (tức là, formula_7 là tập con của formula_10) và theo thông thường, được viết là formula_11 và nói rằng hoặc khi và chỉ khi formula_12 

=== Thứ tự yếu nghiêm ngặt ===
Nhắc lại về tính không so sánh được và tính chất bắc cầu của tính không so sánh được

Hai phần tử formula_1 và formula_3 trên formula_8 được gọi là tương ứng với formula_7 nếu cả hai formula_17 đều không đúng. 
Tính không so sánh được tương ứng với formula_7 chính nó là quan hệ đối xứng và thuần nhất trên formula_8, quan hệ này có tính phản xạ khi và chỉ khi formula_7 hoàn toàn không phản xạ (nghĩa là formula_21 luôn sai), ta có thể giả định ý này sao cho tính chất bắt cầu là tính chất còn lại "quan hệ không so sánh được" cần có để trở thành quan hệ tương đương. 
Bên cạnh đó, định nghĩa quan hệ thuần nhất được cảm sinh formula_22 trên formula_8 bằng cách định nghĩa 
formula_24 
có một điểm quan trọng là, định nghĩa này nhất thiết phải giống với: formula_25 khi và chỉ khi formula_26 
Hai phần tử formula_27 không so sánh được với nhau tương ứng với formula_7 khi và chỉ khi formula_29 tương ứng với quan hệ formula_22 (nếu muốn ngắn dòng hơn, ), thì theo định nghĩa, tức là cả hai formula_31 đều đúng. 
Quan hệ "không so sánh được với nhau tương ứng với formula_32" do đó giống hệt với (tức bằng với) quan hệ "formula_33-tương đương với nhau" (do đó, quan hệ trước có tính bắc cầu khi và chỉ khi quan hệ sau có tính bắc cầu) 
Khi formula_7 hoàn toàn không phản xạ thì "tính chất bắc cầu của tính không so sánh được" (định nghĩa bên dưới) là điều kiện cần và đủ để đảm bảo quan hệ "formula_33-tương đương với nhau" tạo thành quan hệ tương đương trên formula_36 
Nếu nó quả thật đúng, thì nó cho phép biến bất kỳ hai phần tử formula_27 thoả mãn formula_31 về một (tức là chúng đồng nhất với nhau trong lớp tương đương của chúng).

Định nghĩa

Thứ tự yếu nghiêm ngặt trên tập hợp formula_8 là quan hệ thứ tự riêng phần nghiêm ngặt formula_7 trên formula_8 trong đó cảm sinh trên formula_8 bởi formula_7 là quan hệ bắc cầu. 
Cụ thể, thứ tự yếu nghiêm ngặt trên formula_8 là quan hệ thuần nhất formula_7 trên formula_8 thoả mãn bốn tính chất sau:

1. : Với mọi formula_47 formula_21 luôn sai.
- Điều kiện này chỉ thoả mãn khi quan hệ cảm sinh formula_22 trên formula_8 có tính phản xạ, trong đó formula_22 được định nghĩa formula_25 đúng khi và chỉ khi formula_53 .
- : Với mọi formula_54 nếu formula_55 thì formula_56
- : Với mọi formula_57 nếu formula_11 đúng thì formula_53 sai.
- : Với mọi formula_54 nếu formula_1 không so sánh được với formula_3 (tức là cả formula_11 và formula_53 đều sai) và nếu formula_3 không so sánh được với formula_4 thì formula_1 cũng không so sánh được với formula_68
- Hai phần tử formula_29 không so sánh được với nhau tương ứng với formula_7 khi và chỉ khi chúng tương đương với nhau tương ứng với quan hệ cảm sinh formula_22 (theo định nghĩa, tức là cả formula_31 đều đúng), trong khi ngay trước đó, formula_25 đúng khi và chỉ khi formula_53 sai. Do đó điều kiện này chỉ thoả mãn khi quan hệ đối xứng trên formula_8 định nghĩa bởi "formula_29 tương đương với nhau tương ứng với formula_22" có tính bắc cầu, nghĩa là mỗi khi cặp formula_29 formula_33-tương đương với nhau và cặp formula_80 formula_33-tương đương với nhau thì phải formula_82 formula_33-tương đương với nhau. Ta cũng có thể phát biểu lại thành: Nếu formula_31 và đồng thời formula_85 thì phải formula_86

Tính chất (1), (2), và (3) là các tính chất định nghĩa của thứ tự riêng phần nghiêm ngặt, mặc dù có một số phần thừa trong danh sách này là vì tính bất đối xứng (3) sẽ suy ra tính hoàn toàn không phản xạ (1), và cũng vì tính hoàn toàn không phản xạ (1) và tính bắc cầu (2) sẽ cùng suy ra tính bất đối xứng (3). Quan hệ không so sánh được luôn luôn đối xứng và nó thêm tính phản xạ khi và chỉ khi formula_7 là quan hệ hoàn toàn không phản xạ. 
Do đó, thứ tự riêng phần nghiêm ngặt formula_7 là thứ tự yếu nghiêm ngặt khi chỉ khi quan hệ không so sánh được cảm sinh của nó là quan hệ tương đương.
Trong trường hợp này, các lớp tương đương của nó phân hoạch tập formula_8 và hơn nữa, tập formula_90 của các lớp tương đương này có thể sắp thứ tự toàn phần theo một quan hệ hai ngôi, cũng được ký hiệu formula_91 được định nghĩa cho mọi formula_92 như sau: 

Ngược lại, bất kỳ thứ tự toàn phần nghiêm ngặt trên phân hoạch formula_90 của formula_8 cảm sinh thứ tự yếu nghiêm ngặtformula_7 trên formula_8 định nghĩa bởi formula_99 khi và chỉ khi tồn tại các tập hợp formula_92 trong phân hoạch sao cho formula_101 

Không phải mọi quan hệ thứ tự riêng phần nghiêm ngặt đều thoả mãn tính bắc cầu của tính không so sánh được. Ví dụ chẳng hạn, xét quan hệ thứ tự riêng phần trên formula_102 được nghĩa bởi formula_103 Các cặp formula_104 không so sánh được với nhau nhưng formula_105 và formula_106 thì có quan hệ với nhau, do đó tính không so sánh được không phải quan hệ tương đương và ví dụ này không phải thứ tự yếu nghiêm ngặt.

Đối với tính bắc cầu của không so sánh được, các điều kiện sau là điều kiện cần, còn đối với quan hệ thứ tự một phần nghiêm ngặt thì chúng là điều kiện đủ:

- Nếu formula_11 thì với mọi formula_4 hoặc formula_109 hoặc cả hai.
- Nếu formula_1 không so sánh được với formula_3 thì với mọi formula_112, hoặc (formula_113) hoặc (formula_114) hoặc (formula_112 không so sánh được với formula_1 và formula_112 không so sánh được với formula_3).

=== Tiền thứ tự toàn phần ===
Thứ tự yếu nghiêm ngặt có quan hệ rất gần gũi với tiền thứ tự toàn phần hay thứ tự yếu không nghiêm ngặt, và các khái niệm toán học có thể mô hình hoá bằng thứ tự yếu cũng có thể mô hình hoá bằng tiền thứ tự toàn phần. Tiền thứ tự toàn phần hay thứ tự yếu toàn phần là tiền thứ tự mà mọi cặp phần tử đều so sánh được với nhau. Tiền thứ tự toàn phần formula_22 thoả mãn các tính chất sau:

- : Với mọi formula_120 nếu formula_121 thì formula_122
- : Với mọi formula_123 formula_124
- Suy ra : với mọi formula_125 formula_126

Thứ tự toàn phần là tiền thứ tự có tính bất đối xứng, nói cách khác, nó là thứ tự riêng phần. Tiền thứ tự toàn phần đôi khi được gọi là quan hệ ưu tiên.

Bù của thứ tự yếu nghiêm ngặt là tiền thứ tự toàn phần và ngược lại, nhưng thường thì tự nhiên hơn khi liên hệ các thứ tự yếu nghiêm ngặt và tiền thứ tự toàn phần theo cách bảo toàn thứ tự các phần tử thay vì đổi hướng chúng. Do vậy, ta sẽ lấy ngược của phần bù: cho thứ tự yếu nghiêm ngặt formula_91 định nghĩa tiền thứ tự toàn phần formula_22 bằng cách đặt formula_25 mỗi khi không formula_130 Trong hướng ngược lại, để định nghĩa thứ tự yếu nghiêm ngặt < từ tiền thứ tự toàn phần formula_131 đặt formula_11 mỗi khi không formula_133

Trong bất kỳ tiền thứ tự, có quan hệ tương đương tương ứng trong đó mỗi hai phần tử formula_1 và formula_3 được gọi là tương đương với nhau nếu formula_136 Trong trường hợp của tiền thứ tự toàn phần, quan hệ thứ tự riêng phần tương ứng trên tập các lớp tương đương là quan hệ thứ tự toàn phần. Hai phần tử tương đương với nhau trong tiền thứ tự toàn phần khi và chỉ khi chúng không so sánh được với nhau trong thứ tự yếu tương ứng.

=== Phân hoạch được sắp ===
Phân hoạch của tập hợp formula_8 là họ các tập con không giao nhau của formula_8 có formula_8 làm hợp của chúng. Một phân hoạch, khi đi kèm với thứ tự toàn phần thì sẽ hình thành nên một cấu trúc, tên gọi cấu trúc đó là phân hoạch được sắp được đưa bởi nhà toán học Richard P. Stanley, còn tên danh sách tập hợp được đưa bởi Theodore Motzkin. Phân hoạch được sắp của một tập hữu hạn có thể viết thành dãy hữu hạn của các tập của phần hoạch, ví dụ chẳng hạn, ba phân hoạch được sắp của tập formula_140 là
formula_141
formula_142
formula_143

Trong thứ tự yếu nghiêm ngặt, các lớp tương đương của quan hệ không so sánh được sinh ra phân hoạch tập hợp, trong đó các tập hợp này thừa hưởng thứ tự toàn phần từ các phần tử của chúng, từ đó sinh ra phân hoạch được sắp. Theo hướng ngược lại cũng tương tự như vậy, bất kỳ phân hoach được sắp sẽ cảm sinh thứ tự yếu nghiêm ngặt trong đó hai phần tử không so sánh được với nhau khi chúng nằm trong cùng một tập của phân hoạch còn nếu không thì theo thứ tự của các tập chứa nó.

=== Biểu diễn bằng hàm số ===
Đối với các tập có số lực lượng đủ nhỏ, có cách hình thức hoá thứ ba dựa trên các hàm thực. Nếu formula_144 là một tập hợp bất kỳ và ta có hàm thực formula_145 trên formula_144 cảm sinh thứ tự yếu trên formula_144 bằng cách đặt 
formula_148 
Tiền thứ tự toàn phần được định nghĩa bằng cách đặt 
formula_149 
còn quan hệ tương đương tương ứng được định nghĩa bằng cách đặt 
formula_150

Các quan hệ không đổi khi formula_151 được thay bằng formula_152 (hợp của hai hàm), trong đó formula_153 là hàm thực tăng đơn điệu được định nghĩa trên miền giá trị của formula_154 Do đó, từ hàm thoả dụng sẽ định nghĩa ra quan hệ ưu tiên. Trong ngữ cảnh đó, tiền thứ tự yếu còn được gọi là sắp xếp ưu tiên.

Nếu formula_144 hữu hạn hoặc đếm được, thì mọi thứ tự yếu trên formula_144 có thể biểu diễn theo hàm số bằng cách này. Tuy nhiên, tồn tại các thứ tự yếu nghiêm ngặt không có hàm thực tương ứng. Ví dụ chẳng hạn, không có hàm nào cho thứ tự từ điển trên formula_157 Do đó, mặc dù hầu như mọi quan hệ ưu tiên mô hình quan hệ đều định nghĩa hàm thoả dụng xê xích các phép biến đổi bảo toàn thứ tự, không có hàm nào cho ưu tiên thứ tự từ điển.

Tổng quát hơn, nếu formula_144 là tập hợp, formula_159 là tập đi kèm thứ tự yếu nghiêm ngặt formula_160 và formula_161 là hàm số, thì formula_151 cảm sinh thứ tự yếu trên formula_144 bằng cách đặt 
formula_148
Như bên trên, ta sẽ có tiền thứ tự toàn phần định nghĩa bởi 
formula_165 
và quan hệ tương đương tương ứng bằng cách đặt 
formula_166 
Vì không giả định rằng formula_151 là đơn ánh, nên một lớp chứa hai phần tương đương nhau trên formula_159 có thể cảm sinh lớp lớn hơn trên formula_169 Bên cạnh đó, formula_151 cũng không nhất thiết phải là toàn ánh, nên một lớp của formula_159 có thể có lớp nhỏ hơn hoặc rỗng trên formula_169 Tuy nhiên, formula_151 cảm sinh hàm đơn ánh ánh xạ các phân hoạch trên formula_144 sang trên formula_175Do đó, trong trường hợp số phân hoạch hữu hạn, số các lớp trong formula_144 nhỏ hơn hoặc bằng với số các lớp trên formula_175

== Các quan hệ thứ tự khác ==
Nửa thứ tự tổng quát hoá thứ tự yếu, không yêu cầu tính bắc cầu của quan hệ không so sánh được. Thứ tự yếu nghiêm ngặt thoả mãn luật phân tam được gọi là thứ tự toàn phần nghiêm ngặt. Tiền thứ tự toàn phần mà là nghịch đảo (ngược) của phần bù của nó thì chính nó là quan hệ thứ tự toàn phần.

Cho thứ tự yếu nghiêm ngặt formula_7, một loại thứ tự phản xạ tương ứng khác là bao đóng phản xạ của nó, tức thứ tự riêng phần không nghiêm ngặt formula_179 Hai quan hệ phản xạ tương ứng chỉ khác nhau ở một chỗ khi xét hai phần tử formula_180 và formula_105 phân biệt: trong tiền thứ tự toàn phần ta có cả formula_182 và formula_183 đều "đúng", còn trong thứ tự riêng phần cho bởi bao đóng phản xạ ta có cả formula_184 và formula_185 đều "sai". Đối với thứ tự toàn phần nghiêm ngặt, cả hai quan hệ phản xạ này đều là một: thứ tự toàn phần không nghiêm ngặt tương ứng. 

== Thứ tự yếu trên tập hữu hạn ==
=== Liệt kê tổ hợp ===
Số thứ tự yếu phân biệt (hoặc là nghiêm ngặt hoặc là tiền thứ tự toàn phần) trên tập có formula_186 phần tử nằm có công thức sau :

Các số này còn được gọi là số Fubini hay số Bell được sắp.

Lấy ví dụ, xét tập chứa ba phần tử khác nhau, có một thứ tự yếu trong đó ba phần tử này ngang nhau. Có ba cách để lấy một tập có một phần tử và một tập chứa hai phần tử còn lại, mỗi trong cách phân hoạch đó sẽ sinh hai thứ tự yếu dựa trên vị trí của tập một phần tử so với tập hai phần tử kia), do đó nhân lại với nhau sinh ra 6 thứ tự yếu dưới dạng đó. Có đúng 1 cách để phân hoạch tập hợp thành ba tập một phần tử, và các tập đó có thể sắp xếp theo 6 cách khác nhau. Do vậy, khi cộng lại sẽ ra 13 thứ tự yếu trên tập ba phần tử khác nhau.

== Các ứng dụng ==
Như đã nhắc ở trên, thứ tự yếu có ứng dụng trong lý thuyết thoả dụng, được dùng để mô hình hóa một số lựa chọn của người tiêu dùng khi lựa chọn hàng hóa dựa trên ngân sách của mình. Trong các bài quy hoạch tuyến tính và các dạng tối ưu hoá tổ hợp, độ ưu tiên của nghiệm hay của cơ số thường được lấy từ thứ tự yếu, được xác định bởi hàm tổn thất; hiện tượng hoà nhau hay ngang nhau trong cách xếp thứ tự này được gọi "suy biến", và có nhiều luật giải trường hợp ngang nhau để biến thứ tự yếu này thành thứ tự toàn phần để ngăn ngừa các vấn đề xảy ra do suy biến.

Thứ tự yếu còn được dùng trong khoa học máy tính, được biệt là trong các toán dựa trên mịn hoá phân hoạch cho tìm kiếm từ điển theo chiều rộng và thứ tự từ điển tôpô. Trong các thuật toán này, thứ tự yếu trên các đỉnh của đồ thị (được biểu diễn là họ các tập hợp phân hoạch các đỉnh, cùng với danh sách liên kết đôi cho thứ tự toàn phần trên các tập hợp) sẽ được mịn hoá dần trong thuật toán, cuối cùng tạo ra thứ tự toàn phần ở đầu ra.

Trong các thư viện chuẩn dành cho ngôn ngữ lập trình C++, các kiểu dữ liệu set và multiset sắp xếp đầu vào bằng hàm so sánh được xác định tại thời điểm khởi tạo khuôn mẫu, và được giả định là dùng thứ tự yếu nghiêm ngặt.