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ử  ngang với  và ứng cử  ngang với  thì vẫn tồn tại trường hợp ứng cử  hơn hẳn so với ứng cử  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  là quan hệ hai ngôi thuần nhất trên tập hợp  (tức là,  là tập con của ) và theo thông thường, được viết là  và nói rằng  hoặc  khi và chỉ khi

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ử  và  trên  được gọi là  tương ứng với  nếu cả hai  đều không đúng. 
Tính không so sánh được tương ứng với  chính nó là quan hệ đối xứng và thuần nhất trên , quan hệ này có tính phản xạ khi và chỉ khi  hoàn toàn không phản xạ (nghĩa là  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  trên  bằng cách định nghĩa 
 
có một điểm quan trọng là, định nghĩa này  nhất thiết phải giống với:  khi và chỉ khi  
Hai phần tử  không so sánh được với nhau tương ứng với  khi và chỉ khi   tương ứng với quan hệ  (nếu muốn ngắn dòng hơn, ), thì theo định nghĩa, tức là cả hai  đều đúng. 
Quan hệ "không so sánh được với nhau tương ứng với " do đó giống hệt với (tức bằng với) quan hệ "-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  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ệ "-tương đương với nhau" tạo thành quan hệ tương đương trên  
Nếu nó quả thật đúng, thì nó cho phép biến bất kỳ hai phần tử  thoả mãn  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  là quan hệ thứ tự riêng phần nghiêm ngặt  trên  trong đó  cảm sinh trên  bởi  là quan hệ bắc cầu. 
Cụ thể, thứ tự yếu nghiêm ngặt trên  là quan hệ thuần nhất  trên  thoả mãn bốn tính chất sau:

 : Với mọi   luôn sai.
 Điều kiện này chỉ thoả mãn khi quan hệ cảm sinh  trên  có tính phản xạ, trong đó  được định nghĩa  đúng khi và chỉ khi  .
 : Với mọi  nếu  thì 
 : Với mọi  nếu  đúng thì  sai.
 : Với mọi  nếu  không so sánh được với  (tức là cả  và  đều sai) và nếu  không so sánh được với  thì  cũng không so sánh được với 
 Hai phần tử  không so sánh được với nhau tương ứng với  khi và chỉ khi chúng tương đương với nhau tương ứng với quan hệ cảm sinh  (theo định nghĩa, tức là cả  đều đúng), trong khi ngay trước đó,  đúng khi và chỉ khi  sai. Do đó điều kiện này chỉ thoả mãn khi quan hệ đối xứng trên  định nghĩa bởi " tương đương với nhau tương ứng với " có tính bắc cầu, nghĩa là mỗi khi cặp  -tương đương với nhau và cặp  -tương đương với nhau thì phải  -tương đương với nhau. Ta cũng có thể phát biểu lại thành: Nếu  và đồng thời  thì phải 

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  là quan hệ hoàn toàn không phản xạ. 
Do đó, thứ tự riêng phần nghiêm ngặt  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  và hơn nữa, tập  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  được định nghĩa cho mọi  như sau: 

  với một số (hoặc tương đương, tất cả)  đại diện 

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

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  được nghĩa bởi  Các cặp  không so sánh được với nhau nhưng  và  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  thì với mọi  hoặc  hoặc cả hai.
 Nếu  không so sánh được với  thì với mọi , hoặc () hoặc () hoặc ( không so sánh được với  và  không so sánh được với ).

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  thoả mãn các tính chất sau:

 : Với mọi  nếu  thì 
 : Với mọi  
 Suy ra : với mọi  

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  định nghĩa tiền thứ tự toàn phần  bằng cách đặt  mỗi khi không  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  đặt  mỗi khi không 

Trong bất kỳ tiền thứ tự, có quan hệ tương đương tương ứng trong đó mỗi hai phần tử  và  được gọi là tương đương với nhau nếu  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  là họ các tập con không giao nhau của  có  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  là

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  là một tập hợp bất kỳ và ta có hàm thực  trên  cảm sinh thứ tự yếu trên  bằng cách đặt 
 
Tiền thứ tự toàn phần được định nghĩa bằng cách đặt 
 
còn quan hệ tương đương tương ứng được định nghĩa bằng cách đặt  

Các quan hệ không đổi khi  được thay bằng  (hợp của hai hàm), trong đó  là hàm thực tăng đơn điệu được định nghĩa trên miền giá trị của  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  hữu hạn hoặc đếm được, thì mọi thứ tự yếu trên  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  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  là tập hợp,  là tập đi kèm thứ tự yếu nghiêm ngặt  và  là hàm số, thì  cảm sinh thứ tự yếu trên  bằng cách đặt 

Như bên trên, ta sẽ có tiền thứ tự toàn phần định nghĩa bởi 
 
và quan hệ tương đương tương ứng bằng cách đặt 
 
Vì không giả định rằng  là đơn ánh, nên một lớp chứa hai phần tương đương nhau trên  có thể cảm sinh lớp lớn hơn trên  Bên cạnh đó,  cũng không nhất thiết phải là toàn ánh, nên một lớp của  có thể có lớp nhỏ hơn hoặc rỗng trên  Tuy nhiên,  cảm sinh hàm đơn ánh ánh xạ các phân hoạch trên  sang trên Do đó, trong trường hợp số phân hoạch hữu hạn, số các lớp trong  nhỏ hơn hoặc bằng với số các lớp trên

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 , 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  Hai quan hệ phản xạ tương ứng chỉ khác nhau ở một chỗ khi xét hai phần tử  và  phân biệt: trong tiền thứ tự toàn phần ta có cả  và  đều đúng, còn trong thứ tự riêng phần cho bởi bao đóng phản xạ ta có cả  và  đề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ó  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.

Xem thêm

Tham khảo 

Quan hệ hai ngôi
Lý thuyết thứ tự