✨Thứ tự yếu

nhỏ|Thứ tự yếu trên $\{a,\; b,\; c,\; d\}$ trong đó hạng của $a$ nằm dưới $b$ và $c,\; b$ và $c$ có cùng hạng, và $d$ nằm trên $b$ và $c$
I) Thứ tự yếu nghiêm ngặt trong đó được biểu diễn bởi mũi tên $x$ từ $y$;
II) Tiền thứ tự toàn phần $\backslash ,\backslash 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. nhỏ|13 thứ tự yếu khả thi trên tập ba phần tử $\{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ự.

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

Tiên đề hoá

Giả sử rằng là quan hệ hai ngôi thuần nhất trên tập hợp $S$ (tức là, là tập con của $S\; \backslash times\; S$) 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ử $x$ và $y$ trên $S$ được gọi là **** tương ứng với nếu cả hai đều không đúng. 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 $S$ và hơn nữa, tập $\backslash 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 được định nghĩa cho mọi $A,\; B\; \backslash in\; \backslash mathcal\{P\}$ như sau:

: với một số (hoặc tương đương, tất cả) đại diện $a\; \backslash in\; A\; \backslash text\{\; và\; \}\; b\; \backslash 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 $\backslash mathcal\{P\}$ của $S$ cảm sinh thứ tự yếu nghiêm ngặt trên $S$ định nghĩa bởi khi và chỉ khi tồn tại các tập hợp $A,\; B\; \backslash in\; \backslash mathcal\{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 $\{\; a,\; b\; ,c\; \}$ được nghĩa bởi Các cặp $a,\; b\; \backslash text\{\; và\; \}\; a,\; c$ không so sánh được với nhau nhưng $b$ và $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 thì với mọi $z,$ hoặc hoặc cả hai.
• Nếu $x$ không so sánh được với $y$ thì với mọi $z$, hoặc () hoặc () hoặc ($z$ không so sánh được với $x$ và $z$ không so sánh được với $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. Tiền thứ tự toàn phần $\backslash ,\backslash lesssim\backslash ,$ thoả mãn các tính chất sau:

• : Với mọi $x,\; y,\; \backslash text\{\; và\; \}\; z,$ nếu $x\; \backslash lesssim\; y\; \backslash text\{\; và\; \}\; y\; \backslash lesssim\; z$ thì $x\; \backslash lesssim\; z.$
• : Với mọi $x\; \backslash text\{\; và\; \}\; y,$ $x\; \backslash lesssim\; y\; \backslash text\{\; hoặc\; \}\; y\; \backslash lesssim\; x.$ ** Suy ra : với mọi $x,$ $x\; \backslash 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 định nghĩa tiền thứ tự toàn phần $\backslash ,\backslash lesssim\backslash ,$ bằng cách đặt $x\; \backslash lesssim\; y$ 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 $\backslash ,\backslash lesssim,$ đặt mỗi khi không $y\; \backslash lesssim\; x.$

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

$$\backslash \{a\backslash \},\; \backslash \{b\backslash \},$$ $$\backslash \{b\backslash \},\; \backslash \{a\backslash \},\; \backslash ;\; \backslash text\{\; và\; \}$$ $$\backslash \{a,\; b\backslash \}.$$

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 $X$ là một tập hợp bất kỳ và ta có hàm thực $f\; :\; X\; \backslash to\; \backslash R$ trên $X$ cảm sinh thứ tự yếu trên $X$ bằng cách đặt

Tiền thứ tự toàn phần được định nghĩa bằng cách đặt $a\; \{\}\backslash lesssim\{\}\; b\; \backslash text\{\; khi\; và\; chỉ\; khi\; \}\; f(a)\; \backslash leq\; f(b)$ còn quan hệ tương đương tương ứng được định nghĩa bằng cách đặt $a\; \{\}\backslash sim\{\}\; b\; \backslash text\{\; khi\; và\; chỉ\; khi\; \}\; f(a)\; =\; f(b).$

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

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