Xem mã nguồn của Tập hợp sắp thứ tự một phần

{{Short description|Quan hệ hai ngôi trong toán học}}
{{Quan hệ hai ngôi}}
[[Hình:Hasse diagram of powerset of 3.svg|right|thumb|upright=1.15|'''Hình 1.'''  [[Hasse diagram|Biểu đố Hasse]] của [[Tập lũy thừa|tập hợp các tập con]] của tập ba phần tử <math>\{x, y, z\},</math> dưới thứ tự là [[Tập hợp con|tập con của]]. Các tập hợp nối với nhau theo đường đi lên khi chúng so sánh được với nhau, ví dụ như <math>\emptyset</math> và <math>\{x,y\}</math>, trong khi <math>\{x\}</math> và <math>\{y\}</math> thì không.]]

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à [[Quan hệ bắc cầu|tính bắc cầu]] (ta có thể so sánh theo kiểu bắc cầu).<ref>Hoàng Xuân Sính (1972), tr. 26

</ref> 

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''&nbsp;<&nbsp;''y'', hoặc ''x''&nbsp;=&nbsp;''y'', hoặc ''x''&nbsp;>&nbsp;''y'', hoặc ''x và y không so sánh được với nhau''.<ref>{{chú thích web |title=Finite posets |url=http://match.stanford.edu/reference/combinat/sage/combinat/posets/posets.html#sage.combinat.posets.posets.FinitePoset.compare_elements |website=Sage 9.2.beta2 Reference Manual: Combinatorics |access-date=5 January 2022|quote=compare_elements(x, y): Compare x and y in the poset. If x<y, return -1. If x=y, return 0. If x>y, return 1. If x and y are not comparable, return None.}}</ref><ref>{{chú thích tạp chí |last1=Chen |first1=Peter |last2=Ding |first2=Guoli |last3=Seiden |first3=Steve |title=On Poset Merging |page=2 |url=https://www.math.lsu.edu/~ding/poset.pdf |access-date=5 January 2022 |quote=A comparison between two elements s, t in S returns one of three distinct values, namely s≤t, s>t or s<nowiki>|</nowiki>t.}}</ref>

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]].<ref>{{chú thích sách |last1=Merrifield |first1=Richard E. |last2=Simmons |first2=Howard E. |author-link2=Howard Ensign Simmons Jr. |title=Topological Methods in Chemistry |year=1989 |publisher=John Wiley & Sons |location=New York |isbn=0-471-83817-9 |url=https://archive.org/details/topologicalmetho00merr/page/28 |access-date=27 July 2012 |pages=[https://archive.org/details/topologicalmetho00merr/page/28 28] |quote=A partially ordered set is conveniently represented by a ''Hasse diagram''... |url-access=registration }}</ref>

== Quan hệ thứ tự một phần ==
{{anchor|Quan hệ thứ tự riêng 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.<ref name=Wallis>{{chú thích sách |last1=Wallis |first1=W. D. |title=A Beginner's Guide to Discrete Mathematics |date=14 March 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3826-1 |page=100 |url=https://www.google.com/books/edition/A_Beginner_s_Guide_to_Discrete_Mathemati/ONgRBwAAQBAJ?hl=en&gbpv=1&dq=%22partial%20order%20relation%22&pg=PA100&printsec=frontcover&bsq=%22partial%20order%20relation%22 |language=en}}</ref> 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'''<ref>{{chú thích sách|title=Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics|author1=Simovici, Dan A.|author2=Djeraba, Chabane|publisher=Springer|year=2008|isbn=9781848002012|chapter=Partially Ordered Sets|name-list-style=amp|chapter-url=https://books.google.com/books?id=6i-F3ZNcub4C&pg=PA127}}</ref> (hoặc '''quan hệ thứ tự một phần yếu''')<ref name=Wallis/> 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 <math>P</math>, nghĩa là với mọi <math>a, b, c \in P,</math> nó phải thỏa mãn:

# [[Quan hệ phản xạ|Tính bắc cầu]]: <math>a \leq a</math>, tức mỗi phần tử có quan hệ với chính nó
# [[Quan hệ phản đối xứng|Tính phản đối xứng]]: nếu <math>a \leq b</math> và <math>b \leq a</math> thì <math>a = b</math>, tức không có hai phần tử phân biệt nào đứng trước cái còn lại
# [[Quan hệ bắc cầu|Tính bắc cầu]]: nếu <math>a \leq b </math> và <math>b \leq c</math> thì <math>a \leq c</math>.

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'''<ref name=Wallis/> (hoặc quan hệ thứ tự một phần mạnh) là quan hệ thuần nhất < 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 <math>a, b, c \in P:</math>

#[[Quan hệ hoàn toàn không phản xạ|Tính hoàn toàn không phản xạ]]: không <math>a < a</math>, tức không có phần tử nào có quan hệ với chính nó
#[[Quan hệ bất đối xứng|Tính bất đối xứng]]: nếu <math>a < b</math> thì không <math>b < a</math>.
#[[Quan hệ bắc cầu|Tính bắc cầu]]: nếu <math>a < b</math> và <math>b < c</math> thì <math>a < c</math>.

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ạ.<ref name="Flaška 2007">{{chú thích tạp chí|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|journal=Acta Universitatis Carolinae. Mathematica et Physica |year=2007|volume=48 |issue=1 |pages=55–69 |publisher=School of Mathematics - Physics Charles University|location=Prague|url=http://dml.cz/dmlcz/142762}} Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".</ref> 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 ===
[[Tập tin:PartialOrders redundencies svg.svg|thumb|upright=1.25|'''Hình 2.''' [[Biểu đồ giao hoán]] về các mối liên hệ giữa quan hệ nghiêm ngặt và không nghiêm ngặt cùng với đối ngẫu của chúng, qua bao đóng phản xạo (''cls''), hạt nhân không phản xạ (''ker''), và quan hệ ngược (''cnv''). Mỗi quan hệ được biểu diễn bằng [[ma trận logic]] của nó cho [[biểu đồ Hasse]] ở trung tâm của hình ảnh.Ví dụ chẳng hạn <math>3 \not\leq 4</math> nên ô ở hàng 3, cột 4 của ma trận góc dưới bên trái được để trống.]]

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 <math>P</math> có quan hệ gần gũi với nhau. Quan hệ thứ tự một phần không nghiêm ngặt <math>\leq</math> 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 <math>a \leq a;</math> tức quan hệ nghiêm ngặt là tập hợp <math>< \; := \ \leq\  \setminus \  \Delta_P</math> trong đó <math>\Delta_P := \{ (p, p) : p \in P \}</math> là [[quan hệ đơn vị]] trên <math>P \times P</math> và <math>\;\setminus\;</math> ký hiệu [[Phần bù|hiệu tập hợp]]. Ngược lại, quan hệ thứ tự một phần nghiêm ngặt < trên <math>P</math> 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à, <math>\leq\; := \;\Delta_P\; \cup \;<\;</math> là quan hệ thứ tự một phần không nghiêm ngặt . Do đó, nếu <math>\leq</math> là quan hệ thứ tự một phần,  thì quan hệ thứ tự một phần nghiêm ngặt < là [[irreflexive kernel|hạt nhân không phản xạ]] được cho bởi
<math display="block">a < b \text{ nếu } a \leq b \text{ và } a \neq b.</math>Ngược lại, nếu < 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 <math>\leq</math> là [[bao đóng phản xạ]] được đưa bởi

<math display="block">a \leq b \text{ nếu } a < b \text{ hoặc } a = b.</math>

=== Quan hệ đối ngẫu ===
{{Main|Đối ngẫu (lý thuyết thứ tự)}}

''Đối ngẫu'' (hoặc ''đối ngược'') <math>R^{\text{op}}</math> của quan hệ thứ tự một phần <math>R</math> được định nghĩa bằng cách đặt <math>R^{\text{op}}</math> là quan hệ ngược của <math>R</math>, tức. <math>x R^{\text{op}} y</math> khi và chỉ khi <math>y R x</math>. Đố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,{{sfnp|Davey|Priestley|2002|pp=[https://www.google.com/books/edition/Introduction_to_Lattices_and_Order/vVVTxeuiyvQC?hl=en&gbpv=1&pg=PA14 14-15]}} 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 <math>(P,\leq,<)</math>,<ref>{{chú thích sách |last1=Avigad |first1=Jeremy |last2=Lewis |first2=Robert Y. |last3=van Doorn |first3=Floris |title=Logic and Proof |date=29 March 2021 |edition=Release 3.18.4 |url=https://leanprover.github.io/logic_and_proof/relations.html#more-on-orderings |access-date=24 July 2021 |chapter=13.2. More on Orderings |quote=So we can think of every partial order as really being a pair, consisting of a weak partial order and an associated strict one. |archive-date=2023-04-03 |archive-url=https://web.archive.org/web/20230403074506/https://leanprover.github.io/logic_and_proof/relations.html#more-on-orderings }}</ref> trong đó <math>\leq</math> là quan hệ thứ tự một phần không nghiêm ngặt trên <math>P</math>, <math> < </math> là quan hệ một phần nghiêm ngặt tương ứng trên <math>P</math> (hạt nhân không phản xạ của của <math>\leq</math>), <math>\geq</math> là đối ngẫu của <math>\leq</math>, và <math> > </math> là đối ngẫu của <math> < </math>.

Bất kỳ một trong bốn quan hệ thứ tự một phần <math>\leq, <, \geq, \text{ và } ></math> 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 <math>(P,\leq)</math> hoặc <math>(P,<)</math> 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 <math>\leq</math>. Một số tác giả dùng ký hiệu khác thay vì <math>\leq</math> ví dụ như <math>\sqsubseteq</math><ref>{{chú thích web |last1=Rounds |first1=William C. |title=Lectures slides |url=http://www.eecs.umich.edu/courses/eecs203-1/203-Mar7.pdf |website=EECS 203: DISCRETE MATHEMATICS |access-date=23 July 2021 |date=7 March 2002}}</ref> hoặt <math>\preceq</math><ref>{{chú thích sách |last1=Kwong |first1=Harris |title=A Spiral Workbook for Discrete Mathematics |date=25 April 2018 |url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/07%3A_Relations/7.04%3A_Partial_and_Total_Ordering |access-date=23 July 2021 |language=en |chapter=7.4: Partial and Total Ordering}}</ref> để 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, <math>\leq</math> không nên được coi là phần bù của <math> > </math>. Quan hệ <math> > </math> là quan hệ ngược của hạt nhân không phản xạ của <math>\leq</math>, hạt nhân này luôn là tập con của phần bù của <math>\leq</math>, nhưng <math> > </math> chỉ bằng với phần bù của <math>\leq</math> [[khi và chỉ khi]] <math>\leq</math> là quan hệ toàn phần.{{efn|Một bài chứng minh có thể được tìm thấy ở [[:File:PartialOrders redundencies.pdf|đây]].}}

== Các ví dụ ==

[[Tập tin:Division relation 4.svg|thumb|alt=Division Relationship Up to 4|'''Hình 3.''' Đồ thị của tính chia hết của các số từ 1 dến 4. Tập hợp này sắp tự một phần nhưng không toàn phần vì có quan hệ từ 1 đến các số còn lại nhưng không có quan hệ nào từ số 2 đến số 3 hay từ số 3 đến số 4.]]

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

* Tập số thực, hoặc tổng quát hơn là bất kỳ tập có thứ tụ toàn phần, có quan hệ thứ tự nhỏ hơn hoặc bằng ≤, là tập sắp thứ tự một phần không nghiêm ngặt.
* Vẫn trên tập số thực <math>\mathbb{R}</math>, quan hệ chuẩn nhỏ hơn < là quan hệ thứ tự một phần nghiêm ngặt. Điều này cũng đúng với quan hệ lớn hơn > trên <math>\R</math>.
* Theo định nghĩa, mọi [[quan hệ thứ tự yếu nghiêm ngặt]] là quan hệ thứ tự một phần nghiêm ngặt.
* Tập các [[tập con]] của tập cho trước ([[tập lũy thừa]]) sắp xếp theo quan hệ [[bao hàm]] trong (xem hình 1). Tương tư như vậy đối với tập các [[Dãy (toán học)|dãy]] sắp xếp theo [[dãy con]] và tập các [[Xâu (khoa học máy tính)|xâu]] sắp thứ tự theo [[xâu con]].
* Tập hợp các số tự nhiên cùng quan hệ chia hết. (xem hình 3 và hình 6)
* Tập đỉnh của [[đồ thị có hướng không chu trình]] xếp thứ tự theo tính chạm được.
* Tập các [[không gian con]] của [[không gian vectơ]] xếp thứ tự theo phép bao hàm.
* Cho tập sắp thứ tự một phần ''P'', [[sequence space|không gian dãy]] chứa tất cá các dãy phần tử của ''P'', trong đó dãy ''a'' đứng trước dãy ''b'' nếu mỗi phần tử trong ''a'' đứng trước phần tử tương ứng trong ''b. Dưới công thức'', <math>\left(a_n\right)_{n \in \N} \leq \left(b_n\right)_{n \in \N}</math> khi và chỉ khi <math>a_n \leq b_n</math> với mọi <math>n \in \N</math>; đây là [[quan hệ thứ tự từng phần]]. 
* Cho tập hợp ''X'' và tập sắp thứ tự một phần ''P'', [[không gian hàm]] chứa mọi hàm từ ''X'' đến ''P'', trong đó ''f'' ≤ ''g'' khi và chỉ khi ''f''(''x'') ≤ ''g''(''x'') với mọi <math>x \in X.</math>
* Trong toán học, [[Rào (toán học)|rào]] là tập hợp sắp thứ tự một phần được định nghĩa bằng dãy thay phiên các quan hệ thứ tự ''a'' < ''b'' > ''c'' < ''d'' ...
* Tập các sự kiện trong [[Thuyết tương đối hẹp|tương đối hẹp]] và trong đa số trường hợp của{{efn|Xem [[Thuyết tương đối rộng#Du hành thời gian]].}} [[Thuyết tương đối rộng|tương đối rộng]], trong đó cho hai sự kiện ''X'' và ''Y'', ''X'' ≤ ''Y'' khi và chỉ khi ''Y'' nằm trong [[nón ánh sáng]] của ''X''. Sự kiện ''Y'' chỉ có thể là hệ quả của ''X'' khi ''X'' ≤ ''Y''.

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ự [[Gia phả học|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===
{{multiple image
| align = right
| dirction = horizontal
| total_width = 550
| image1 = Lexicographic order on pairs of natural numbers.svg
| caption1 = '''Hình 4a.''' Thứ tự từ điển trên <math>\N \times \N</math>
| image2 = N-Quadrat, gedreht.svg|
| caption2 = '''Hình 4b.''' Thứ tự tích trên <math>\N \times \N</math>
| image3 = Strict product order on pairs of natural numbers.svg|
| caption3 = '''Hình 4c.''' Bao đóng phản xạ của thứ tự tích nghiêm ngặt trên <math>\N \times \N.</math> Các phần tử [[#Formal definition|được phủ]] bởi (3, 3) và phủ (3, 3) được tô màu xanh là và đỏ tương ứng.
}}

Đây là ba trong nhiều quan hệ thứ tự một phần được định nghĩa trên [[Tích Descartes|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):
*[[Thứ tự từ điển]]: (''a'', ''b'') ≤ (''c'', ''d'') nếu ''a'' < ''c'' hoặc (''a'' = ''c'' và ''b'' ≤ ''d'');
*[[Thứ tự tích]]: (''a'', ''b'') ≤ (''c'', ''d'') nếu ''a'' ≤ ''c'' và ''b'' ≤ ''d'';
*[[Bao đóng phản xạ]] của tích trực tiếp của hai thứ tự nghiêm ngặt tương ứng: (''a'', ''b'') ≤ (''c'', ''d'') nếu (''a'' < ''c'' và ''b'' < ''d'') hoặc (''a'' = ''c'' và ''b'' = ''d'').

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 (toán học)|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 ===
{{anchor|sum}}
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ự'''<ref>{{citation
 | last1 = Neggers | first1 = J.
 | last2 = Kim | first2 = Hee Sik
 | contribution = 4.2 Product Order and Lexicographic Order
 | isbn = 9789810235895
 | pages = 62–63
 | publisher = World Scientific
 | title = Basic Posets
 | year = 1998}}</ref> (hay còn gọi là '''tổng tuyến tính'''),{{sfnp|Davey|Priestley|2002|pp=[https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA17 17–18]}} ''Z'' = ''X'' ⊕ ''Y'', được định nghĩa trên hợp của hai tập ''X'' và ''Y'' theo quan hệ ''a'' ≤<sub>''Z''</sub> ''b'' khi và chỉ khi:
* ''a'', ''b'' ∈ ''X'' và ''a'' ≤<sub>''X''</sub> ''b'', hoặc
* ''a'', ''b'' ∈ ''Y'' và ''a'' ≤<sub>''Y''</sub> ''b'', hoặc
* ''a'' ∈ ''X và'' ''b'' ∈ ''Y''.

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.<ref>{{chú thích sách|author=P. R. Halmos|title=Naive Set Theory|url=https://archive.org/details/naivesettheory0000halm_r4g0|url-access=registration|year=1974|publisher=Springer |isbn=978-1-4757-1645-0|page=[https://archive.org/details/naivesettheory0000halm_r4g0/page/82 82]}}</ref>

== 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 <math>(\mathcal{P}(\{x, y, z\}),\subseteq)</math> bao gồm tập các tập con của <math>\{x, y, z\},</math> được xếp theo quan hệ bao hàm (xem hình 1).

* ''a có quan hệ với'' ''b'' khi ''a'' ≤ ''b''. Điều này không có nghĩa ''b'' cũng có quan hệ với ''a'', bởi vì quan hệ không cần phải đối xứng. Lấy ví dụ, <math>\{x\}</math> có quan hệ với <math>\{x, y\},</math> nhưng ngược lại thì không.
* ''a'' và ''b'' so sánh được với nhau nếu ''a'' ≤ ''b'' hoặc ''b'' ≤ ''a''. Ngược lại, thì chúng được gọi là không so sánh được với nhau.Ví dụ chẳng hạn, <math>\{x\}</math> và <math>\{x, y, z\}</math> so sánh được với nhau, trong khi <math>\{x\}</math> và <math>\{y\}</math>thì không.
* ''[[Tập sắp thứ tự toàn phần|Quan hệ toàn phần]]'' hoặc ''quan hệ tuyến tính'' là quan hệ thứ tự một phần mà mọi cặp phần tử đều so sánh được với nhau. Ví dụ chẳng hạn như tập số tự nhiên cùng quan hệ thứ tự tự nhiên của nó.
* ''[[Chain (order theory)|Xích]]'' là tập con có thứ tự toàn phần của tập sắp thứ tự một phần. Ví dụ chẳng hạn,, <math>\{ \{\,\}, \{x\}, \{x, y, z\} \}</math> là một xích.
* ''[[antichain|Phản xích]]'' là tập con của tập sắp thứ tự một phần mà trong đó không có hai phần tử phân biệt nào so sánh được với nhau, ví dụ như tập các tập một phần tử <math>\{\{x\}, \{y\}, \{z\}\}.</math>
* Phần tử ''a'' được gọi là ''nhỏ hơn nghiêm ngặt'' với phần tử ''b'', nếu ''a'' ≤ ''b'' và <math>a \neq b.</math> Ví dụ, <math>\{x\}</math> nhỏ hơn nghiêm ngặt với <math>\{x, y\}.</math>
* Phần tử ''a được gọi là phủ bởi phần tử'' ''b'', được viết là ''a'' ⋖ ''b'' (hoặc ''a'' <: ''b''), nếu ''a'' nhỏ hơn nghiêm ngặt với ''b'' và không có phần tử thứ ba ''c'' nằm giữa chúng, nói dưới dạng hình thức: nếu đồng thời ''a'' ≤ ''b'' và <math>a \neq b</math>, và ''a'' ≤ ''c'' ≤ ''b'' là sai với với mọi ''c'' thỏa mãn <math>a \neq c \neq b.</math> Dưới thứ tự nghiêm ngặt <, quan hệ ''a'' ⋖ ''b'' có thể nói như sau "''a'' < ''b'' nhưng không ''a'' < ''c'' < ''b'' cho bất kỳ ''c''". Ví dụ chẳng hạn, <math>\{x\}</math> được phủ bởi <math>\{x, z\},</math> nhưng không được phủ bởi <math>\{x, y, z\}.</math>

=== Cực trị ===
[[Tập tin:Hasse diagram of powerset of 3 no greatest or least.svg|thumb|upright=1.5|'''Hình 5.''' Hình ảnh này là hình số 1 khi bỏ phần tử lớn nhất và nhỏ nhất. Trong tập đã được rút gọn này, hàng trên là của ba [[phần tử cực đại|phần tử tối đại]] còn hàng dưới là của ba [[phần tử cực tiểu|phần tử tối tiểu]]. Tập này không có phần tử lớn nhất hay nhỏ nhất.]]

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 <math>P,</math> nhất là:
* [[Phần tử lớn nhất]] và nhỏ nhất: Phần tử <math>g \in P</math> là {{em|phần tử lớn nhất}} nếu với mọi phần tử <math>a \in P, a \leq g.</math> Phần tử <math>m \in P</math> là ''phần tử nhỏ nhất'' nếu với mọi phần tử <math>a \in P, m \leq a.</math> Tập sắp thứ tự một phần chỉ có một phần tử lớn nhất hoặc nhỏ nhất. Trong ví dụ trước, tập <math>\{x, y, z\}</math> phần tử lớn nhất còn <math>\{\,\}</math> là phần tử nhỏ nhất.
* [[Phần tử tối đại và phần tử tối tiểu|Phần tử tối đại]] và phần tử tối tiểu: Phần tử <math>g \in P</math> là phần tử tối đại nếu không có phần tử <math>a \in P</math> sao cho <math>a > g.</math> Tương tự như vậy, phần tử <math>m \in P</math> là phần tử tối tiểu nếu không có phần tử <math>a \in P</math> sao cho <math>a < m.</math> Nếu tập sắp thứ tự một phần có phần tứ lớn nhất đó thì phần tử đó là phần tử tối đại duy nhất, nhưng nếu không thì có thể có nhiều hơn một phần tử tối đại, và tương tự như vậy cho phần tử nhỏ nhất và phần tử tối tiểu. Ở ví dụ trước, <math>\{x, y, z\}</math> và <math>\{\,\}</math> là phần tử lớn nhất và nhỏ nhất tương ứng. Bỏ hai phần tử này đi thì sẽ có 3 phần tử tối đại và 3 phần tử tối tiểu (xem hình 5).
* [[Cận trên và dưới]]: Cho tập con ''A'' của ''P'', phần tử ''x'' thuộc ''P'' là cận trên của ''A'' nếu ''a''&nbsp;≤&nbsp;''x'', với mỗi phần tử ''a'' thuộc ''A''. Cụ thể hơn, ''x'' không nhất thiết phải nằm trong ''A'' để trở thành cận trên của ''A''. Tương tự như vậy, phần tử ''x'' thuộc ''P'' là cận dưới của ''A'' nếu ''a''&nbsp;≥&nbsp;''x'', với mỗi phần tử ''a'' thuộc ''A''. Phần tử lớn nhất của ''P'' cũng là cận trên của ''P,'' và phần tử nhỏ nhất là cận dưới của ''P''. Trong ví dụ này, tập <math>\{x, y\}</math> là cận trên cho tập các phần tử <math>\{\{x\}, \{y\}\}.</math>

[[Tập tin:Infinite lattice of divisors.svg|thumb|upright|'''Hình 6.''' Các số nguyên không âm được sắp thứ tự theo tính chia hết]]
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 <math>\{2, 3, 5, 10\},</math> 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==
{{multiple image
| align = right
| direction = horizontal
| total_width = 580
| image1 = Monotonic but nonhomomorphic map between lattices.gif
| caption1 = '''Hình 7a.''' Ánh xạ này bảo toàn thứ tự nhưng không phản xạ thứ tự (vì ''f''(''u'') ≼ ''f''(''v''), nhưng không u {{small|<math>\leq</math>}} v).
| image2 = Birkhoff120.svg
| caption2 = '''Hình 7b.''' Đẳng cấu thứ tự giữa các ước số của 120 (sắp thứ tự một phần theo tính chia hết) và tập con của  {{nowrap|{2, 3, 4, 5, 8}}} (sắp thứ tự một phần theo quan hệ bao hàm)
}}

Cho hai tập hợp sắp thứ tự một phần (''S'', ≤) và (''T'', ≼),{{efn|1=Các quan hệ thứ tự một phần {{small|<math>\leq</math>}} và ≼ có thể khác nhau, nhưng không nhất thiết phải.}} hàm <math>f : S \to T</math> được gọi là '''[[bảo toàn thứ tự]]''', '''[[Hàm số đơn điệu|đơn điệu]]''', hoặc '''đẳng điệu''', nếu với mọi <math>x, y \in S,</math> <math>x \leq y</math> 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 <math>f : S \to T</math> và <math>g : T \to U</math> đều bảo toàn thứ tự thì hàm hợp <math>g \circ f : S \to U</math> cũng bảo toàn thứ tự.
Hàm <math>f : S \to T</math> được gọi là '''phản xạ thứ tự''' nếu với mọi <math>x, y \in S,</math> ''f''(''x'') ≼ ''f''(''y'') suy ra <math>x \leq y.</math>
Nếu <math>f</math> 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, <math>f</math> phải là [[đơn ánh]], vì <math>f(x) = f(y)</math> suy ra <math>x \leq y \text{ và } y \leq x</math> và do vậy <math>x = y</math>  theo tính phản đối xứng của <math>\leq.</math> 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ự <math>f : S \to T</math> 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ự <math>f : S \to T</math> và <math>g : T \to U</math> sao cho cả hai <math>g \circ f</math> và <math>f \circ g</math> đề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.{{sfnp|Davey|Priestley|2002|pp=23–24}}

Ví dụ, xét hàm <math>f : \N \to \mathbb{P}(\N)</math> 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 <math>x</math> là ước của <math>y,</math> thì mỗi ước nguyên tố của  <math>x</math> cũng là ước nguyên tố của <math>y.</math> Tuy nhiên, nó không phải đơn ánh (vì nó ánh xạ cả 12 và 6 sang <math>\{2, 3\}</math>) 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 <math>g : \N \to \mathbb{P}(\N)</math> á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 <math>\{4\}</math>), 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 <math>g(\N).</math> Hình 7b minh họa một tập hợp con của <math>\N</math> và ảnh dưới phép đẳng cấu <math>g.</math> 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 [{{fullurl:OEIS:A001035}} A001035] trong [[Bảng tra cứu dãy số nguyên trực tuyến|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ố các quan hệ}}

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, ... {{OEIS|A000112}}.

== Mở rộng tuyến tính ==

Quan hệ thứ tự một phần <math>\leq^*</math> trên tập hợp <math>X</math> được gọi là '''mở rộng''' của thứ tự một phần khác <math>\leq</math> trên <math>X</math> nếu với mọi phần tử <math>x, y \in X,</math> nếu <math>x \leq y,</math> thì cũng <math>x \leq^* y.</math> [[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ự]]).<ref>{{chú thích sách |last=Jech |first=Thomas |author-link=Thomas Jech |title=The Axiom of Choice |year=2008 |orig-year=1973 |publisher=[[Dover Publications]] |isbn=978-0-486-46624-8}}</ref>

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 <math>P</math> làm nútt và mỗi phần tử của <math>\leq</math> 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 [[Tiền thứ tự|tập sắp tiền thứ tự]]) có thể được coi là [[Phạm trù (toán học)|phạm trù]] mà, cho vật <math>x</math> và <math>y,</math> có tối đa một [[cấu xạ]] từ <math>x</math> đến <math>y.</math> 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à <math>(y, z) \circ (x, y) = (x, z).</math> Các phạm trù như vậy đôi khi được gọi là ''[[Phạm trù posetal|posetal]]''.

Các tập sắp thứ tự một phần [[Tương đương phạm trù|tương đương]] với nhau khi và chỉ khi chúng [[Đẳng cấu của phạm trù|đẳ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ô==
{{Main|Không gian sắp thứ tự một phần}}

Nếu <math>P</math> 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 <math>\{ (a,b) : a \le b \}</math> đóng dưới [[không gian tích]] tô pô <math>P \times P.</math> 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 của một dãy|giới hạn]] theo nghĩa sau: nếu <math>\lim_{i \to \infty} a_i = a,</math> và <math>\lim_{i \to \infty} b_i = b,</math> và với mọi <math>i,</math> <math>a_i \leq b_i,</math> thì <math>a \leq b.</math><ref name="ward-1954">{{chú thích tạp chí|first=L. E. Jr|last=Ward|title=Partially Ordered Topological Spaces|journal=Proceedings of the American Mathematical Society|volume=5 |year=1954|pages= 144–161|issue= 1|doi=10.1090/S0002-9939-1954-0063016-5|hdl=10338.dmlcz/101379|doi-access=free}}</ref>

==Khoảng==

''Khoảng'' trong tập hợp sắp thứ tự một phần ''P'' là tập con {{mvar|I}} của ''P'' cùng với tính chất sau: cho bất kỳ ''x'' và ''y'' thuộc {{mvar|I}} và bất kỳ ''z'' thuộc ''P'', nếu ''x'' ≤ ''z'' ≤ ''y'', thì ''z'' cũng thuộc {{mvar|I}}. (Định nghĩa này tổng quát hoá khái niệm ''[[khoảng (toán học)|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 "<", ''khoảng mở'' (''a'', ''b'') là tập các phần tử thoả mãn ''x'' thoả mãn ''a'' < ''x'' < ''b'' (tức ''a'' < ''x'' và ''x'' < ''b''). Khoảng mở có thể rỗng kể cả khi ''a'' < ''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 {{mvar|I}} sao cho {{math|0 < {{var|I}} < 1}}.

''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'' > ''b'', và khi đó thì khoảng đó là khoảng rỗng.

Khoảng {{mvar|I}} được gọi là bị chặn nếu tồn tại các phần tử <math>a, b \in P</math> sao cho {{math|{{var|I}} ⊆ [''a'', ''b'']}}. 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 {{math|1=''P'' = (0, 1) ∪ (1, 2) ∪ (2, 3)}} 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à [[hữu hạn địa phương|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 <math>\N \times \N</math> không hữu hạn địa phương, bởi vì {{math|(1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1)}}.

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 <math>[a, b] = \{a, b\}.</math>

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

== Xem thêm ==

{{div col|colwidth=27em}}
* [[Antimatroid]], hình thức hóa thứ tự trên tập hợp cho phép nhiều họ các thứ tự tổng quát hơn thứ tự một phần 
* [[Tập hệ quả]], cách tiếp cận bằng tập sắp thứ tự một phần cho trọng lực lượng tử
* {{annotated link|Đồ thị so sánh}}
* {{annotated link|Thứ tự một phần đầy đủ}}
* {{annotated link|Tập hợp có hướng}}
* {{annotated link|Tập hợp phân bậc sắp thứ tự một phần}}
* {{annotated link|Đại số liên thuộc}}
* {{annotated link|Dàn (lý thuyết thứ tự)|Dàn}}
* {{annotated link|Tập hợp hữu hạn địa phương sắp thứ tự một phần}}
* {{annotated link|Đại số liên thuộc|Hàm Möbius trên tập sắp thứ tự một phần}}
* [[Tập lồng nhau#Định nghĩa hình thức|Họ các tập lồng nhau]]
* {{annotated link|Order polytope}}
* {{annotated link|Trường có thứ tự}}
* {{annotated link|Nhóm có thứ tự}}
* {{annotated link|Không gian vectơ có thứ tự}}
* [[Tô pô tập sắp thứ tự một phần]], một dạng không gian tô pô có thể được định nghĩa từ bất kỳ tập sắp thứ tự một phần
* [[Tính liên tục Scott]] – tính liên tục của hàm số giữa hai thứ tự một phần
* {{annotated link|Nửa dàn}}
* {{annotated link|Nửa thứ tự}}
* {{annotated link|Thống trị ngẫu nhiên}}
* [[Thứ tự yếu nghiêm ngặt]] – thứ tự một phần nghiêm ngặt "<" trong đó quan hệ{{nowrap|"không ''a'' < ''b''}} {{nowrap|hay ''b'' < ''a''"}} có tính bắc cầu.
* {{annotated link|Thứ tự toàn phần}}
* [[Cây (cấu trúc dữ liệu)|Cây]] – Cấu trúc dữ liệu của quan hệ chứa trong tập hợp 
* {{annotated link|Bổ đề Zorn}}
{{div col end}}

==Ghi chú==

{{notelist}}

==Chú thích==

{{tham khảo}}

==Tham khảo==
* {{chú thích sách |last1=Davey |first1=B. A. |last2=Priestley |first2=H. A. |title=Introduction to Lattices and Order |edition=2nd |location=New York |publisher=Cambridge University Press |year=2002 |isbn=978-0-521-78451-1 |title-link= Introduction to Lattices and Order}}
* {{chú thích tạp chí|first=Jayant V. |last=Deshpande|title=On Continuity of a Partial Order|journal=Proceedings of the American Mathematical Society|volume=19|year=1968|pages=383–386|issue=2 |doi=10.1090/S0002-9939-1968-0236071-7 |doi-access= free}}
* {{chú thích sách|first=Gunther|last=Schmidt|author-link=Gunther Schmidt|year=2010|title=Relational Mathematics |series=Encyclopedia of Mathematics and its Applications|volume= 132|publisher=Cambridge University Press |isbn=978-0-521-76268-7}}
* {{chú thích sách|author=Bernd Schröder|title=Ordered Sets: An Introduction with Connections from Combinatorics to Topology|url=https://books.google.com/books?id=66oqDAAAQBAJ&q=%22Partially+ordered+set%22+OR+poset |date=11 May 2016 |publisher=Birkhäuser|isbn=978-3-319-29788-0}}
* {{chú thích sách|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|title=Enumerative Combinatorics 1 |series=Cambridge Studies in Advanced Mathematics|volume=49|publisher=Cambridge University Press|isbn=0-521-66351-2 |year=1997}}

==Liên kết ngoài==
{{Commons|Hasse diagram}}

* {{OEIS el|1=A001035|2= Number of posets with ''n'' labeled elements|formalname=Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs)}}
* {{OEIS el|1=A000112|2=Number of partially ordered sets ("posets") with n unlabeled elements.}}
{{Lý thuyết thứ tự}}{{Authority control}}

[[Thể loại:Lý thuyết thứ tự]]
[[Thể loại:Quan hệ hai ngôi]]