Tập hợp sắp thứ tự một phần

Trong toán học, đặc biệt là trong lý thuyết thứ tự, một tập hợp sắp thứ tự một phần (hay còn gọi là tập hợp sắp thứ tự bộ phận, hay tập hợp sắp thứ tự riêng phần, hoặc được gọi ngắn đi là poset) bao gồm một tập hợp cùng với một quan hệ hai ngôi có tính phản xạ (mỗi phần tử được so sánh với chính nó), tính phản đối xứng (giữa hai phần tử có nhiều nhất một cách so sánh) và tính bắc cầu (ta có thể so sánh theo kiểu bắc cầu). 
Từ "một phần" hay "bộ phận" trong tên quan hệ ý chỉ rằng không phải mọi cặp phần tử đều so sánh được với nhau. Nghĩa là, có một số cặp phần tử ta không biết phần tử nào đứng trước trong tập sắp thứ tự một phần. Do đó, quan hệ thứ tự riêng phần là dạng tổng quát của quan hệ thứ tự toàn phần, quan hệ mà mọi cặp trong tập hợp đều so sánh được với nhau.
Định nghĩa không hình thức.
Quan hệ thứ tự một phần là một khái niệm trong so sánh trong đó hai phần tử "x" và "y" chỉ nằm duy nhất một trong bốn quan hệ sau: hoặc "x" &lt; "y", hoặc "x" = "y", hoặc "x" &gt; "y", hoặc "x và y không so sánh được với nhau".
Tập hợp đi cùng quan hệ thứ tự một phần được gọi là tập hợp sắp thứ tự một phần. Tập hợp sắp thứ tự một phần thường được vẽ qua biểu đồ Hasse.
Quan hệ thứ tự một phần.
Quan hệ thứ tự một phần là quan hệ thuần nhất có tính bắc cầu và phản đối xứng. Có hai định nghĩa thường gặp cho quan hệ thứ tự một phần phản xạ và không phản xạ, được gọi là "không nghiêm ngặt" và "nghiêm ngặt" tương ứng. Hai định nghĩa này có thể đặt trong ương ứng một-một, trong đó mỗi quan hệ thứ tự một phần nghiêm ngặt có duy nhất một quan hệ thứ tự một phần không nghiêm ngặt tương ứng và ngược lại cũng thế. Thuật ngữ quan hệ thứ tự một phần thường là chỉ đến nhất quan hệ thứ một phần không nghiêm ngặt.
Quan hệ thứ tự một phần không nghiêm ngặt.
Quan hệ thứ tự một phần không nghiêm ngặt (hoặc quan hệ thứ tự một phần yếu) là quan hệ thuần nhất ≤ có tính phản xạ, phản đối xứng và bắc cầu trên tập hợp formula_1, nghĩa là với mọi formula_2 nó phải thỏa mãn:
Quan hệ thứ tự một phần không nghiêm ngặt còn là tiền thứ tự phản đối xứng.
Quan hệ thứ tự một phần nghiêm ngặt.
Quan hệ thứ tự một phần nghiêm ngặt (hoặc quan hệ thứ tự một phần mạnh) là quan hệ thuần nhất &lt; có tính hoàn toàn không phản xạ, bất đối xứng và bắc cầu trên tập hợp P; nghĩa là nó phải thỏa mãn các điều kiện sau với mọi formula_10
Tính hoàn toàn không phản xạ và tính bắt cầu suy ra tính bất đối xứng. Tính bất đối xứng thì sẽ suy ra tính hoàn toàn không phản xạ. Nói cách khác, quan hệ bắc cầu có tính bất đối xứng khi và chỉ khi nó hoàn toàn không phản xạ. Do vậy, định nghĩa giữ nguyên kể cả khi nó bỏ đi điều kiện hoàn toàn không phản xạ hoặc điều kiện bất đối xứng (nhưng không thể bỏ cả hai).
Quan hệ thứ tự một phần nghiêm ngặt còn được gọi là tiền thứ tự nghiêm ngặt.
Mối liên hệ giữa quan hệ thứ tự một phần nghiêm ngặt và không nghiêm ngặt.
Quan hệ một phần nghiêm ngặt và không nghiêm ngặt trên cùng tập hợp formula_1 có quan hệ gần gũi với nhau. Quan hệ thứ tự một phần không nghiêm ngặt formula_18 có thể biến đổi sang dạng nghiêm ngặt bằng cách loại bỏ tất cả quan hệ dưới dạng formula_19 tức quan hệ nghiêm ngặt là tập hợp formula_20 trong đó formula_21 là quan hệ đơn vị trên formula_22 và formula_23 ký hiệu hiệu tập hợp. Ngược lại, quan hệ thứ tự một phần nghiêm ngặt &lt; trên formula_1 có thể đổi sang dạng không nghiêm ngặt bằng cách hợp thêm các quan hệ dưới dạng đó; tức là, formula_25 là quan hệ thứ tự một phần không nghiêm ngặt . Do đó, nếu formula_18 là quan hệ thứ tự một phần, thì quan hệ thứ tự một phần nghiêm ngặt &lt; là hạt nhân không phản xạ được cho bởi
formula_27Ngược lại, nếu &lt; là quan hệ thứ tự một phần nghiêm ngặt thì quan hệ thứ tự một không phần nghiêm ngặt formula_18 là bao đóng phản xạ được đưa bởi
formula_29
Quan hệ đối ngẫu.
"Đối ngẫu" (hoặc "đối ngược") formula_30 của quan hệ thứ tự một phần formula_31 được định nghĩa bằng cách đặt formula_30 là quan hệ ngược của formula_31, tức. formula_34 khi và chỉ khi formula_35. Đối ngẫu của quan hệ thứ tự một phần không nghiêm ngặt là quan hệ thứ tự một phần không nghiêm ngặt, tương tự như vậy đối với đối ngẫu của quan hệ thứ tự một phần nghiêm ngặt. 
Thuật ngữ.
Ta có thể coi tập hợp sắp thứ tự một là bộ ba formula_36, trong đó formula_18 là quan hệ thứ tự một phần không nghiêm ngặt trên formula_1, formula_39 là quan hệ một phần nghiêm ngặt tương ứng trên formula_1 (hạt nhân không phản xạ của của formula_18), formula_42 là đối ngẫu của formula_18, và formula_44 là đối ngẫu của formula_39.
Bất kỳ một trong bốn quan hệ thứ tự một phần formula_46 trên cùng một tập cho trước sẽ xác định duy nhất ba quan hệ còn lại. Do đó khi ký hiệu,ta có thể viết formula_47 hoặc formula_48 và giả định rằng các quan hệ còn lại được định nghĩa tương tự. Các nhà toán học thường định nghĩa bằng quan hệ thứ tự một phần không nghiêm ngặt formula_18. Một số tác giả dùng ký hiệu khác thay vì formula_18 ví dụ như formula_51 hoặt formula_52 để phân biệt quan hệ thứ tự một phần với toàn phần.
Khi nhắc đến thứ tự một phần, formula_18 không nên được coi là phần bù của formula_44. Quan hệ formula_44 là quan hệ ngược của hạt nhân không phản xạ của formula_18, hạt nhân này luôn là tập con của phần bù của formula_18, nhưng formula_44 chỉ bằng với phần bù của formula_18 khi và chỉ khi formula_18 là quan hệ toàn phần.
Các ví dụ.
Các ví dụ của tập hợp sắp thứ tự một phần trong toán học bao gồm
Một ví dụ khác thường gặp trong ngoài đời là tập các con người sắp xếp theo thứ tự phả hệ. Một số cặp người có thể có quan hệ tổ tiên-con cháu nhưng cũng có một số cặp người không so sánh với nhau vì không ai trong cặp là con cháu của người kia.
Thứ tự trên tích Descartes của tập sắp thứ tự một phần.
Đây là ba trong nhiều quan hệ thứ tự một phần được định nghĩa trên tích đề các của hai tập hợp sắp thứ tự một phần, xếp thứ tự từ yếu đến mạnh (xem hình 4):
Cả ba đều có thể định nghĩa tương tự cho tích Descartes của nhiều hơn hai tập hợp.
Khi áp dụng cho các không gian vectơ có thứ tự trên cùng một trường, kết quả thu được trong mỗi trường hợp cũng là không gian vectơ có thứ tự.
Xem thêm Quan hệ thứ tự trên tích Descartes của tập sắp thứ tự toàn phần
Tổng của tập sắp tự thứ tự một phần.
Một cách khác để hợp hai tập sắp thứ tự một phần (không giao nhau) là tổng thứ tự (hay còn gọi là tổng tuyến tính), "Z" = "X" ⊕ "Y", được định nghĩa trên hợp của hai tập "X" và "Y" theo quan hệ "a" ≤"Z" "b" khi và chỉ khi:
Nếu hai tập sắp thứ tự một phần đó có thứ tự tốt, thì tổng thứ tự của nó cũng vậy.
Các thuật ngữ liên quan.
Các ví dụ sau sử dụng tập hợp sắp thứ tự một phần formula_67 bao gồm tập các tập con của formula_68 được xếp theo quan hệ bao hàm (xem hình 1).
Cực trị.
Có một số khái niệm cho phần tử "lớn nhất" và "nhỏ nhất" trong tập sắp thứ tự một phần formula_85 nhất là:
Giống với ví dụ trên, xét tập số các số nguyên dương được sắp theo tính chia hết:: 1 là phần tử nhỏ nhất, bởi nó là ước của mọi số còn lại, tập này không có phần tử lớn nhất (tuy nhiên nếu ta cho số 0 vào thì số 0 trở thành phần tử lớn nhất vì nó là bội của bất kỳ số nguyên, xem hình 6). Tập sắp thứ tự một phần này không có phần tử tối đại nào vì bất kỳ "g" đều sẽ là ước của số khác (chẳng hạn như 2"g)", phân biệt với nó, do đó "g" không tối đại. Nếu số 1 được bỏ đi mà vẫn giữa tính chia hết cũng như thứ tự của các số lớn hơn một, thì tập sắp thứ tự một phần thu được không có phần tử nhỏ nhất nhưng bất kỳ số nguyên tố là phần tử tối tiểu của nó. Trong tập sắp thứ tự một phần này, 60 là cận trên (nhưng chưa phải cận trên nhỏ nhất) của tập con formula_102 tập con này không có cận dưới (vì số 1 không còn trong tập khác); mặt khác, số 2 là cận dưới của tập con chứa các lũy thừa của 2, tập con này không có cận trên.
Ánh xạ giữa hai tập sắp thứ tự một phần.
Cho hai tập hợp sắp thứ tự một phần ("S", ≤) và ("T", ≼), hàm formula_103 được gọi là bảo toàn thứ tự, đơn điệu, hoặc đẳng điệu, nếu với mọi formula_104 formula_105 suy ra "f"("x") ≼ "f"("y").
Nếu ("U", ≲) cũng là tập sắp thứ tự một phần và cả hai hàm formula_103 và formula_107 đều bảo toàn thứ tự thì hàm hợp formula_108 cũng bảo toàn thứ tự.
Hàm formula_103 được gọi là phản xạ thứ tự nếu với mọi formula_104 "f"("x") ≼ "f"("y") suy ra formula_111
Nếu formula_112 vừa bảo toàn thứ tự vừa phản xạ thứ tự thì nó được gọi là phép nhúng thứ tự của ("S", ≤) vào ("T", ≼).
Trong trường hợp này, formula_112 phải là đơn ánh, vì formula_114 suy ra formula_115 và do vậy formula_116 theo tính phản đối xứng của formula_117 Nếu tồn tại phép nhúng thứ tự giữa hai tập sắp thứ tự một phần "S" và "T", ta có thể nói "S" được nhúng vào "T". Nếu phép nhúng thứ tự formula_103 là song ánh. thì nó được gọi là đẳng cấu thứ tự và hai thứ tự một phần ("S", ≤) và ("T", ≼) được gọi là đẳng cấu với nhau. Quan hệ thứ tự đẳng cấu với nhau có cấu trúc biểu đồ Hasse tương tự với nhau (xem hình 7a). Ta có thể chứng minh nếu tồn tại hai ánh xạ bảo toàn thứ tự formula_103 và formula_107 sao cho cả hai formula_121 và formula_122 đều là hàm đồng nhất trên "S" và "T", tương ứng, thì "S" và "T" đẳng cấu thứ tự với nhau.
Ví dụ, xét hàm formula_123 từ tập hợp các số tự nhiên (xếp theo tính chia hết) tới tập lũy thừa của các số tự nhiên (xếp theo quan hệ bao hàm) có thể được định nghĩa bằng cách ánh xạ mỗi số sang tập các ước nguyên tố của số đó. Nó bảo toàn thứ tự vì nếu formula_124 là ước của formula_125 thì mỗi ước nguyên tố của formula_124 cũng là ước nguyên tố của formula_127 Tuy nhiên, nó không phải đơn ánh (vì nó ánh xạ cả 12 và 6 sang formula_128) và cũng không phản xạ thứ tự (vì 12 không phải là ước của của 6). Nếu thay vì đó, định nghĩa ánh xạ mỗi số sang tập các ước lũy thừa nguyên tố của nó qua formula_129 ánh xạ này bảo toàn thứ tự, phản xạ thứ tự và do đó là phép nhúng thứ tự. Song, nó không phải đẳng cấu thứ tự (Bởi vì , ví dụ chẳng hạn nó không ánh xạ số nào sang tập formula_130), tuy nhiên nó có thể trở thành một bằng cách giới hạn miền giá trị thành formula_131 Hình 7b minh họa một tập hợp con của formula_132 và ảnh dưới phép đẳng cấu formula_133 Cách xây dựng đẳng cấu thứ tự vào tập lũy thừa này có thể tổng quát hóa cho một lớp rộng rãi các quan hệ thứ tự một phần, được gọi là dàn phân phối, xem "định lý biểu diễn Birkhoff".
Số các quan hệ thứ tự một phần trong tập hợp.
Dãy [ A001035] trong OEIS cho số quan hệ thứ tự một phần trên tập hợp chứa "n" phần tử được dán nhãn:
Số quan hệ thứ tự một phần nghiêm ngặt bằng với số quan hệ thứ tự một phần.
Nếu đếm xê xích đẳng cấu, thì ta thu được dãy 1, 1, 2, 5, 16, 63, 318, ... .
Mở rộng tuyến tính.
Quan hệ thứ tự một phần formula_134 trên tập hợp formula_135 được gọi là mở rộng của thứ tự một phần khác formula_18 trên formula_135 nếu với mọi phần tử formula_138 nếu formula_139 thì cũng formula_140 Mở rộng tuyến tính là mở rộng đồng thời là quan hệ tuyến tính (tức toàn phần). Ví dụ chẳng hạn, thứ tự từ điển của tập sắp thứ tự toàn phần là mở rộng tuyến tính của thứ tự tích của nó. Mọi thứ tự một phần đều có thể mở rộng thành quan hệ thứ tự toàn phần (theo nguyên lý mở rộng thứ tự).
Trong khoa học máy tính, các thuật toán tìm mở rộng tuyến tính của quan hệ thứ tự một phần (được biểu diễn bằng quan hệ chạm tới được của các đồ thị có hướng không chu trình) được gọi là sắp xếp tô pô.
Đồ thị có hướng không chu trình.
Các quan hệ thứ một phần nghiêm ngặt có mối liên hệ chặt chẽ với các đồ thị có hướng không chu trình (hay còn gọi là DAG). Nếu một đồ thị được xây bằng cách lấy mỗi phần tử thuộc formula_1 làm nútt và mỗi phần tử của formula_18 làm cạnh, thì mọi thứ tự một nghiêm ngặt đều là DAG, và bao đóng bắc cầu của DAG vừa là quan hệ thứ tự một phần nghiêm ngặt cũng vừa là DAG. Ngược lại, bởi trong quan hệ không nghiêm ngặt, mỗi nút sẽ có cạnh vòng lại nên nó không thể là DAG. 
Trong lý thuyết phạm trù.
Mọi tập sắp thứ tự một phần (và mọi tập sắp tiền thứ tự) có thể được coi là phạm trù mà, cho vật formula_124 và formula_125 có tối đa một cấu xạ từ formula_124 đến formula_127 Cụ thể hơn, gọi hom("x", "y") = {("x", "y")} nếu "x" ≤ "y" (còn không thì là tập rỗng) và formula_147 Các phạm trù như vậy đôi khi được gọi là "posetal".
Các tập sắp thứ tự một phần tương đương với nhau khi và chỉ khi chúng đẳng cấu với nhau. Trong tập sắp thứ tự một phần, phần tử nhỏ nhất nếu tồn tại là vật khởi tạo, và phần tử lớn nhất lớn nhất nếu tồn tại thì là vật kết thúc. Bên cạnh đó, mọi tập sắp tiền thứ tự đều tương đương với một tập sắp tự một phần.
Quan hệ thứ tự một phần trong không gian tô pô.
Nếu formula_1 là tập hợp sắp thứ tự một phần và đồng thời có cấu trúc của không gian tô pô, thì theo lệ, ta có thể giả định rằng formula_149 đóng dưới không gian tích tô pô formula_150 Dưới giả định này, các quan hệ thứ tự một phần vẫn hoạt động tại các giới hạn theo nghĩa sau: nếu formula_151 và formula_152 và với mọi formula_153 formula_154 thì formula_155
Khoảng.
"Khoảng" trong tập hợp sắp thứ tự một phần "P" là tập con của "P" cùng với tính chất sau: cho bất kỳ "x" và "y" thuộc và bất kỳ "z" thuộc "P", nếu "x" ≤ "z" ≤ "y", thì "z" cũng thuộc . (Định nghĩa này tổng quát hoá khái niệm "khoảng" thưởng gặp ở số thực.)
Khi "a" ≤ "b", "khoảng đóng" ["a", "b"] là tập các phần tử "x" thoả mãn "a" ≤ "x" ≤ "b" (tưc là, "a" ≤ "x" và "x" ≤ "b"). Nó chứa cả hai phần tử "a" và "b".
Sử dụng quan hệ ngặt tương ứng "&lt;", "khoảng mở" ("a", "b") là tập các phần tử thoả mãn "x" thoả mãn "a" &lt; "x" &lt; "b" (tức "a" &lt; "x" và "x" &lt; "b"). Khoảng mở có thể rỗng kể cả khi "a" &lt; "b". Ví dụ chẳng hạn, khoảng mở (0, 1) trên các số nguyên bị rỗng là bởi không có số nguyên sao cho .
"Khoảng nửa mở" (hay "nửa đóng") ["a", "b") và ("a", "b"] được định nghĩa tương tự như trên.
Đôi khi định nghĩa khoảng được mở rộng cho cả "a" &gt; "b", và khi đó thì khoảng đó là khoảng rỗng.
Khoảng được gọi là bị chặn nếu tồn tại các phần tử formula_156 sao cho . Dễ thấy mọi khoảng có thể biểu diễn bằng ký hiệu khoảng thì bị chặn, song ngược lại chưa chắc đã đúng. Ví dụ chẳng hạn, gọi là tập con sắp thứ tự một phần của tập các số thực. Tập con (1, 2) là khoảng bị chặn, nhưng nó không có cận trên đúng hay cận dưới đúng thuộc "P", nên nó không thể viết theo ký hiệu khoảng sử dụng các phần tử thuộc "P".
Tập sắp thứ tư một phần được gọi là poset hữu hạn địa phương nếu mọi khoảng bị chặn của nó hữu hạn. Ví dụ, các số nguyên hữu hạn địa phương dưới thứ tự tự nhiên của chúng. Thứ tự từ điển trên tích Đề-các formula_157 không hữu hạn địa phương, bởi vì .
Sử dụng ký hiệu khoảng, tính chất ""a" phủ bởi "b"" có thể viết lại thành formula_158
Không nên nhầm lẫn khái niệm khoảng trong thứ tự một phần với lớp các thứ tự một phần đặc biệt được gọi là thứ tự khoảng.