Thứ tự yếu

Đừng nhầm lẫn với Thứ tự yếu của các hoán vị.

Quan hệ hai ngôi
Đối xứng Phản đối xứng Toàn phần Lập tốt Có nối Có gặp Quan hệ tương đương ✓ ✗ ✗ ✗ ✗ ✗ Tiền thứ tự (giả thứ tự) ✗ ✗ ✗ ✗ ✗ ✗ Thứ tự riêng phần ✗ ✓ ✗ ✗ ✗ ✗ Tiền thứ tự toàn phần ✗ ✗ ✓ ✗ ✗ ✗ Thứ tự toàn phần ✗ ✓ ✓ ✗ ✗ ✗ Tiền thứ tự tốt ✗ ✗ ✓ ✓ ✗ ✗ Giả thứ tự tốt ✗ ✗ ✗ ✓ ✗ ✗ Thứ tự tốt ✗ ✓ ✓ ✓ ✗ ✗ Dàn ✗ ✓ ✗ ✗ ✓ ✓ Nửa dàn có nối ✗ ✓ ✗ ✗ ✓ ✗ Nửa dàn có gặp ✗ ✓ ✗ ✗ ✗ ✓
Dấu "✓" chỉ tính chất trong cột đó cần phải có trong định nghĩa của hàng đó. Ví dụ, định nghĩa của quan hệ tương đương buộc nó phải có tính đối xứng. Tất cả định nghĩa đều yêu cầu tính bắc cầu và tính phản xạ.

Thứ tự yếu trên ${\displaystyle \{a,b,c,d\}}$ trong đó hạng của ${\displaystyle a}$ nằm dưới ${\displaystyle b}$ và ${\displaystyle c,b}$ và ${\displaystyle c}$ có cùng hạng, và ${\displaystyle d}$ nằm trên ${\displaystyle b}$ và ${\displaystyle c}$
I) Thứ tự yếu nghiêm ngặt ${\displaystyle \,<\,}$ trong đó ${\displaystyle x<y}$ được biểu diễn bởi mũi tên ${\displaystyle x}$ từ ${\displaystyle y}$;
II) Tiền thứ tự toàn phần ${\displaystyle \,\leq }$
III) Các phân hoạch được sắp, trong đó tập các phân hoạch nằm trong hình elip nét đứt, còn thứ tự toàn phần được biểu diễn bằng mũi tên.

13 thứ tự yếu khả thi trên tập ba phần tử ${\displaystyle \{a,b,c\}.}$ Thứ tự toàn phần duy nhất được tô màu đen, hai thứ tự được nối với nhau bằng cạnh nếu chúng chỉ sai khác nhau duy nhất một lưỡng phân

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ự.[1]

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.[2]

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++.[3]

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.[4] 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.[5] 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ử ${\displaystyle x}$ ngang với ${\displaystyle y,}$ và ứng cử ${\displaystyle y}$ ngang với ${\displaystyle z,}$ thì vẫn tồn tại trường hợp ứng cử ${\displaystyle x}$ hơn hẳn so với ứng cử ${\displaystyle z,}$ 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.[6]

Tiên đề hoá

Giả sử rằng ${\displaystyle \,<\,}$ là quan hệ hai ngôi thuần nhất trên tập hợp ${\displaystyle S}$ (tức là, ${\displaystyle \,<\,}$ là tập con của ${\displaystyle S\times S}$) và theo thông thường, được viết là ${\displaystyle x<y}$ và nói rằng ${\displaystyle x<y}$ được thoả mãn hoặc là đúng khi và chỉ khi ${\displaystyle (x,y)\in \,<.\,}$

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

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

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

${\displaystyle A<B{\text{ khi và chỉ khi }}a<b}$ với một số (hoặc tương đương, tất cả) đại diện ${\displaystyle a\in A{\text{ và }}b\in B.}$

Ngược lại, bất kỳ thứ tự toàn phần nghiêm ngặt trên phân hoạch ${\displaystyle {\mathcal {P}}}$ của ${\displaystyle S}$ cảm sinh thứ tự yếu nghiêm ngặt${\displaystyle \,<\,}$ trên ${\displaystyle S}$ định nghĩa bởi ${\displaystyle a<b}$ khi và chỉ khi tồn tại các tập hợp ${\displaystyle A,B\in {\mathcal {P}}}$ trong phân hoạch sao cho ${\displaystyle a\in A,b\in B,{\text{ và }}A<B.}$

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

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.[8] Tiền thứ tự toàn phần ${\displaystyle \,\lesssim \,}$ thoả mãn các tính chất sau:

• Tính bắc cầu: Với mọi ${\displaystyle x,y,{\text{ và }}z,}$ nếu ${\displaystyle x\lesssim y{\text{ và }}y\lesssim z}$ thì ${\displaystyle x\lesssim z.}$
• Tính liên thông mạnh: Với mọi ${\displaystyle x{\text{ và }}y,}$ ${\displaystyle x\lesssim y{\text{ hoặc }}y\lesssim x.}$
  • Suy ra tính phản xạ: với mọi ${\displaystyle x,}$ ${\displaystyle x\lesssim x.}$

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 ${\displaystyle \,<,}$ định nghĩa tiền thứ tự toàn phần ${\displaystyle \,\lesssim \,}$ bằng cách đặt ${\displaystyle x\lesssim y}$ mỗi khi không ${\displaystyle y<x.}$ 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 ${\displaystyle \,\lesssim ,}$ đặt ${\displaystyle x<y}$ mỗi khi không ${\displaystyle y\lesssim x.}$[9]

Trong bất kỳ tiền thứ tự, có quan hệ tương đương tương ứng trong đó mỗi hai phần tử ${\displaystyle x}$ và ${\displaystyle y}$ được gọi là tương đương với nhau nếu ${\displaystyle x\lesssim y{\text{ và }}y\lesssim x.}$ 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 ${\displaystyle S}$ là họ các tập con không giao nhau của ${\displaystyle S}$ có ${\displaystyle S}$ 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[10], còn tên danh sách tập hợp được đưa bởi Theodore Motzkin.[11] 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 ${\displaystyle \{a,b\}}$ là $${\displaystyle \{a\},\{b\},}$$ $${\displaystyle \{b\},\{a\},\;{\text{ và }}}$$ $${\displaystyle \{a,b\}.}$$

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 ${\displaystyle X}$ là một tập hợp bất kỳ và ta có hàm thực ${\displaystyle f:X\to \mathbb {R} }$ trên ${\displaystyle X}$ cảm sinh thứ tự yếu trên ${\displaystyle X}$ bằng cách đặt $${\displaystyle a<b{\text{ khi và chỉ khi }}f(a)<f(b).}$$ Tiền thứ tự toàn phần được định nghĩa bằng cách đặt ${\displaystyle a{}\lesssim {}b{\text{ khi và chỉ khi }}f(a)\leq f(b)}$ còn quan hệ tương đương tương ứng được định nghĩa bằng cách đặt ${\displaystyle a{}\sim {}b{\text{ khi và chỉ khi }}f(a)=f(b).}$

Các quan hệ không đổi khi ${\displaystyle f}$ được thay bằng ${\displaystyle g\circ f}$ (hợp của hai hàm), trong đó ${\displaystyle g}$ là hàm thực tăng đơn điệu được định nghĩa trên miền giá trị của ${\displaystyle f.}$ 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.[12]

Nếu ${\displaystyle X}$ hữu hạn hoặc đếm được, thì mọi thứ tự yếu trên ${\displaystyle X}$ có thể biểu diễn theo hàm số bằng cách này.[13] 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 ${\displaystyle \mathbb {R} ^{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 ${\displaystyle X}$ là tập hợp, ${\displaystyle Y}$ là tập đi kèm thứ tự yếu nghiêm ngặt ${\displaystyle \,<,\,}$ và ${\displaystyle f:X\to Y}$ là hàm số, thì ${\displaystyle f}$ cảm sinh thứ tự yếu trên ${\displaystyle X}$ bằng cách đặt $${\displaystyle a<b{\text{ khi và chỉ khi }}f(a)<f(b).}$$ Như bên trên, ta sẽ có tiền thứ tự toàn phần định nghĩa bởi ${\displaystyle a{}\lesssim {}b{\text{ khi và chỉ khi }}f(a){}\lesssim {}f(b),}$ và quan hệ tương đương tương ứng bằng cách đặt ${\displaystyle a{}\sim {}b{\text{ khi và chỉ khi }}f(a){}\sim {}f(b).}$ Vì không giả định rằng ${\displaystyle f}$ là đơn ánh, nên một lớp chứa hai phần tương đương nhau trên ${\displaystyle Y}$ có thể cảm sinh lớp lớn hơn trên ${\displaystyle X.}$ Bên cạnh đó, ${\displaystyle f}$ cũng không nhất thiết phải là toàn ánh, nên một lớp của ${\displaystyle Y}$ có thể có lớp nhỏ hơn hoặc rỗng trên ${\displaystyle X.}$ Tuy nhiên, ${\displaystyle f}$ cảm sinh hàm đơn ánh ánh xạ các phân hoạch trên ${\displaystyle X}$ sang trên ${\displaystyle Y.}$Do đó, trong trường hợp số phân hoạch hữu hạn, số các lớp trong ${\displaystyle X}$ nhỏ hơn hoặc bằng với số các lớp trên ${\displaystyle Y.}$

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

Thứ tự yếu trên tập hữu hạn

Liệt kê tổ hợp

Bài chi tiết: số Bell được sắ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ó ${\displaystyle n}$ phần tử nằm có công thức sau (dãy số A000670 trong bảng OEIS):

Số các quan hệ từng loại của tập hợp có n phần tử

Số phần tử	Bất kì	Bắc cầu	Phản xạ	Đối xứng	Tiền thứ tự	Thứ tự bộ phận	Tiền thứ tự toàn phần	Thứ tự toàn phần	Quan hệ tương đương
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65536	3994	4096	1024	355	219	75	24	15
n	2^n2		2^n2−n	2^n(n+1)/2			${\textstyle \sum _{k=0}^{n}k!S(n,k)}$	n!	${\textstyle \sum _{k=0}^{n}S(n,k)}$
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

Trong đó S(n, k) là số Stirling loại thứ hai.

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,[13] đượ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.[16] 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.[17]

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.[18]

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.[3]

Xem thêm

• Tính so sánh được – Tính chất của các phần tử trong bất đẳng thức
• Tiền thứ tự – Quan hệ phản xạ và bắc cầu
• Thành phần yếu

Tham khảo

1. ^ Roberts, Fred; Tesman, Barry (2011), Applied Combinatorics (ấn bản thứ 2), CRC Press, Section 4.2.4 Weak Orders, pp. 254–256, ISBN 9781420099836.
2. Arrow, Kenneth J. (1959). “Rational Choice Functions and Orderings”. Economica. 26 (102): 121–127. doi:10.2307/2550390. ISSN 0013-0427.
3. ^ Josuttis, Nicolai M. (2012), The C++ Standard Library: A Tutorial and Reference, Addison-Wesley, tr. 469, ISBN 9780132977739.
4. Schneider, Florian; Schonger, Martin (tháng 5 năm 2017). “An experimental test of the Anscombe-Aumann Monotonicity axiom” (PDF). Department of Economics. Working paper series. Đại học Zürich (207). doi:10.5167/uzh-113552. ISSN 1664-7041.
5. Baker, Kent (29 tháng 4 năm 2007), “The Bruce hangs on for Hunt Cup victory: Bug River, Lear Charm finish in dead heat for second”, The Baltimore Sun, Bản gốc lưu trữ ngày 29 tháng 3 năm 2015.
6. Regenwetter, Michel (2006), Behavioral Social Choice: Probabilistic Models, Statistical Inference, and Applications, Cambridge University Press, tr. 113ff, ISBN 9780521536660.
7. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007), Transitive Closures of Binary Relations I (PDF), Prague: School of Mathematics - Physics Charles University, tr. 1, S2CID 47676001, Bản gốc (PDF) lưu trữ ngày 6 tháng 4 năm 2018, Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".
8. Quan hệ đó còn được gọi là có tính liên thông mạnh
9. Ehrgott, Matthias (2005), Multicriteria Optimization, Springer, Proposition 1.9, p. 10, ISBN 9783540276593.
10. Stanley, Richard P. (1997), Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, tr. 297.
11. Motzkin, Theodore S. (1971), “Sorting numbers for cylinders and other classification numbers”, Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), Providence, R.I.: Amer. Math. Soc., tr. 167–176, MR 0332508.
12. Gross, O. A. (1962), “Preferential arrangements”, The American Mathematical Monthly, 69 (1): 4–8, doi:10.2307/2312725, JSTOR 2312725, MR 0130837.
13. ^ Roberts, Fred S. (1979), Measurement Theory, with Applications to Decisionmaking, Utility, and the Social Sciences, Encyclopedia of Mathematics and its Applications, 7, Addison-Wesley, Theorem 3.1, ISBN 978-0-201-13506-0.
14. Luce, R. Duncan (1956), “Semiorders and a theory of utility discrimination” (PDF), Econometrica, 24 (2): 178–191, doi:10.2307/1905751, JSTOR 1905751, MR 0078632.
15. ^ Velleman, Daniel J. (2006), How to Prove It: A Structured Approach, Cambridge University Press, tr. 204, ISBN 9780521675994.
16. Arrow, Kenneth J. (1959). “Rational Choice Functions and Orderings”. Economica. 26 (102): 121–127. doi:10.2307/2550390. ISSN 0013-0427.
17. Chvátal, Vašek (1983), Linear Programming, Macmillan, tr. 29–38, ISBN 9780716715870.
18. Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), “Partition refinement techniques: an interesting algorithmic tool kit”, International Journal of Foundations of Computer Science, 10 (2): 147–170, doi:10.1142/S0129054199000125, MR 1759929.