Tiền thứ tự

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

Trong toán học, đặc biệt là trong lý thuyết thứ tự, tiền thứ tự hoặc tựa thứ tự là quan hệ hai ngôi có tính phản xạ và bắc cầu. Tiền thứ tự tổng quát hơn quan hệ tương đương và quan hệ thứ tự riêng phần (không nghiêm ngặt), cả hai quan hệ này đều là trường hợp đặc biệt của tiền thứ tự: quan hệ thứ tự riêng phần là tiền thứ tự thêm tính phản xứng, còn quan hệ tương đương là tiền thứ tự thêm tính đối xứng

Sơ đồ Hasse của tiền thứ tự x R y định nghĩa bởi x//4≤y//4 trên các số tự nhiên. Bởi các chu trình, R không phản xứng. Nếu tất cả các số trong chu trình được coi là bằng nhau thì ta sẽ thu được quan hệ thứ tự riêng phần (và tuyến tính)

Tên tiền thứ tự lấy từ ý tưởng rằng tiền thứ tự 'sắp thành' quan hệ thứ tự (riêng phần), nhưng chưa tới được; các quan hệ này không nhất thiết phải không phản đối xứng hay không bất đối xứng. Bởi tiền thứ tự là quan hệ hai ngôi, ký hiệu $\,\leq \,$ có thể dùng cho tiền thứ tự bởi chúng không nhất thiết phải phản xứng.

Trong văn bản, khi $a\leq b,$, ta có thể nói rằng b phủ a hoặc a đứng trước b, hoặc b rút về a. Đôi khi, ký hiệu ← hoặc → hoặc $\,\lesssim \,$ được dùng thay vì $\,\leq .$

Mọi tiền thứ tự đều có đồ thị có hướng tương ứng với nó. Đồ thị này có các đỉnh tương ứng với các phần tử trong tập và các cạnh có hướng là tiền thứ tự giữa hai phần tử trong tập hợp. Song ngược lại không đúng:Hầu như mọi đồ thị có hướng đều không phản xạ hoặc bắc cầu. Nhìn chung thì, các đồ thị tương ứng với quan hệ có thể chứa các chu trình. Tiền thứ tự mà phản xứng thì sẽ không có chu trình, thay vì đó nó sẽ là quan hệ thứ tự riêng phần và đồ thị tương ứng của nó là đồ thị có hướng không chu trình. Tiền thứ tự có tính đối xứng là quan hệ tương đương, và đồ thị tương ứng của nó là đồ thị vô hướng. Trong tổng quát, đồ thị tương ứng của tiền thứ tự có thể có nhiều hơn một thành phần liên thông.

Định nghĩa

Xét quan hệ thuần nhất $\,\leq \,$ trên một số tập hợp $P,$ cho trước sao cho theo định nghĩa, $\,\leq \,$ là một tập con của $P\times P$ và ký hiệu $a\leq b$ được sử dụng thay cho $(a,b)\in \,\leq .$ Khi đó, $\,\leq \,$ được gọi là tiền thứ tự hoặc tựa thứ tự nếu nó vừa phản xạ vừa bắc cầu. Nghĩa là, quan hệ đó thoả mãn hai điều kiện sau:

1. Tính phản xạ: $a\leq a$ với mọi $a\in P,$ và
2. Tính bắc cầu: nếu $a\leq b{\text{ và }}b\leq c{\text{ thì }}a\leq c$ với mọi $a,b,c\in P.$

Tập đi kèm quan hệ tiền thứ tự được gọi là tập sắp tiền thứ tự (hoặc proset). Để nhấn mạnh sự khác biệt với tiền thứ tự nghiêm ngặt, tiền thứ tự cũng có thể được gọi là tiền thứ tự không nghiêm ngặt.

Nếu tính phản xạ được thay bởi không phản xạ (vẫn giữa tính bắc cầu) thì kết quả thu được được gọi là tiền thứ tự nghiêm ngặt; Nói rõ ra, tiền thứ tự nghiêm ngặt trên $P$ là quan hệ hai ngôi thuần nhất $\,<\,$ trên $P$ thoả mãn hai điều kiện sau:

1. Tính hoàn toàn không phản xạ: không $a<a$ với mọi $a\in P;$ tức là $\,a<a$ là sai với mọi $a\in P,$ và
2. Tính bắc cầu: nếu $a<b{\text{ và }}b<c{\text{ thì }}a<c$ với mọi $a,b,c\in P.$

Quan hệ hai ngôi P là tiền thứ tự nghiêm ngặt khi và chỉ khi nó là quan hệ thứ tự riêng phần nghiêm ngặt. Theo định nghĩa, quan hệ thứ tự riêng phần nghiêm ngặt là tiền thứ tự nghiêm ngặt không đối xứng (quan hệ $\,<\,$ được gọi là không đối xứng nếu $a<b{\text{ thì }}{\textit {not}}\ b<a$ với mọi $a,b.$ Ngược lại mọi tiền thứ tự nghiêm ngặt là quan hệ thứ tự riêng phần nghiêm ngặt riêng phần vì mọi quan hệ bắc cầu nhưng không phản xạ thì sẽ không đối xứng.

Mặc dù hai tên gọi tương đương nhau, thuật ngữ "thứ tự riêng phần nghiêm ngặt" được dùng nhiều hơn "tiền thứ tự nghiêm ngặt". Ngược với tiền thứ tự nghiêm ngặt, có rất nhiều tiền thứ tự không nghiêm ngặt.

Các định nghĩa có liên quan

Nếu tiền thứ tự có thêm tính phản đối xứng (tức là $a\leq b$ và $b\leq a$ thì $a=b,$) thì được gọi là quan hệ thứ tự riêng phần.

Mặt khác, nếu tiền thứ tự có thêm tính đối xứng (tức là $a\leq b$ thì $b\leq a,$) thì được gọi là quan hệ tương đương.

Tiền thứ tự có tính toàn phần nếu $a\leq b$ hoặc $b\leq a$ với mọi $a,b\in P.$

Tập sắp tiền thứ tự $P$ có thể được viết thành công thức bằng phạm trù mỏng trong lý thuyết phạm trù; nghĩa là một phạm trù có tối đa một cấu xạ giữa vật này sang vật khác. Ở đây vật tương ứng các phần tử thuộc $P,$ và có một cấu xạ giữa hai phần tử có quan hệ với nhau và không có nếu ngược lại.

Lớp sắp tiền thứ tự là lớp đi kèm với tiền thứ tự. Mọi tập hợp đều là lớp và do đó mọi tập sắp tiền thứ tự là lớp sắp tiền thứ tự.

Các ví dụ

Lý thuyết đồ thị

• Quan hệ "Có đường đi từ a đến b" trong bất kỳ đồ thị có hướng (có thể có chu trình) là tiền thứ tự.

Khoa học máy tính

Trong khoa học máy tính, ta thường thấy các ví dụ sau.

• Thứ tự tiệm cận là tiền thứ tự trên các hàm $f:\mathbb {N} \to \mathbb {N}$. Quan hệ tương đương tương ứng được gọi là tương đương tiệm cận.
• Rút gọn thời gian đa thức, Rút gọn nhiều-một và rút gọn Turing là các tiền thứ tự trên lớp độ phức tạp tính toán.
• Các quan hệ kiểu dữ liệu con thường là tiền thứ tự.
• Tiền thứ tự mô phỏng.
• Các quan hệ rút gọn trong các hệ thống viết lại trừu tượng.

Các ví dụ khác

• Mọi không gian tô pô hữu hạn đều có tiền thứ tự trên các điểm của nó bằng cách định nghĩa $x\leq y$ khi và chỉ khi x nằm trong mọi lân cận của y.
• Quan hệ định nghĩa bởi $x\leq y$ nếu $f(x)\leq f(y),$ trong đó f là hàm theo tiền thứ tự.
• Quan hệ định nghĩa bởi $x\leq y$ nếu tồn tại đơn ánh từ x đến y. Đơn ánh có thể đổi thành toàn ánh hoặc bất cứ hàm nào bảo toàn cấu trúc, ví dụ như đồng cấu vành hoặc phép thế.
• Các quan hệ nhúng cho các tiền thứ tự toàn phần đếm được.

Ứng dụng

Tiền thứ tự đóng vai trò quan trọng trong các tình huống sau:

• Mọi tiền thứ tự đều có tô pô của riêng nó, tô pô Alexandrov; hơn nữa, mọi tiền thứ tự trên một tập hợp đều tương ứng một-một với tô pô Alexandrov trên tập đó.
• Tiền thứ tự có thể dùng để định nghĩa các đại số trong.
• Tiền thứ tự được dùng trong kỹ thuật buộc trong lý thuyết tập hợp để chứng minh tính nhất quán và tính độc lập (logic) của kết quả toán học.

Xây dựng

Mọi quan hệ hai ngôi $R$ trên tập hợp $S$ có thể mở rộng thành tiền thứ tự trên $S$ bằng cách lấy bao đóng bắc cầu và bao đóng phản xạ, $R^{+=}.$ Bao đóng bắc cầu nghĩa là có quan hệ đường đi $R:xR^{+}y$ khi và chỉ khi có $R$-đường đi từ $x$ đến $y.$

Tiền thứ tự thặng dư trái cảm sinh bởi quan hệ hai ngôi

Cho quan hệ hai ngôi $R,$ phần bù của hợp $R\backslash R={\overline {R^{\textsf {T}}\circ {\overline {R}}}}$ tạo thành một tiền thứ tự được gọi là phần thặng dư trái, trong đó $R^{\textsf {T}}$ là quan hệ ngược của $R,$ và ${\overline {R}}$ ký hiệu quan hệ bù của $R,$ trong khi $\circ$ là phép hợp thành quan hệ.

Tiền thứ tự và thứ tự riêng phần trên phân hoạch tập hợp

Cho tiền thứ tự $\,\lesssim \,$ trên $S$, ta có thể định nghĩa quan hệ tương đương trên $\,\sim \,$ trên $S$ sao cho

$$a\sim b\quad {\text{ khi và chỉ khi }}\quad a\lesssim b\;{\text{ và }}\;b\lesssim a.$$

Quan hệ thu được $\,\sim \,$ có tính phản xạ bởi $\,\lesssim \,$ phản xạ; có tính bắc cầu bằng cách áp dụng tính bắc cầu của $\,\lesssim \,$ hai lần; và có tính đối xứng theo định nghĩa.

Dùng quan hệ này, ta có thể xây quan hệ thứ tự riêng phần trên tập thương của quan hệ tương đương $S/\sim ,$, tập thương là tập của tất cả các lớp tương đương của $\,\sim .$ Nếu tiền thứ tự được ký hiệu là $R^{+=},$ thì $S/\sim$ là tập hợp của các lớp tương đương $R$-chu trình: $x\in [y]$ khi và chỉ khi $x=y$ hoặc $x$ nằm trong $R$-chu trình của $y$. Trong bất kỳ trường hợp, có thể định nghĩa trên $S/\sim$ quan hệ $[x]\leq [y]$ khi và chỉ khi $x\lesssim y.$ Định nghĩa này hoàn toàn xác định bởi điều kiện định nghĩa của nó không phụ thuộc vào lựa chọn đại diện của $[x]$ và $[y]$. Ta có thể kiểm chứng tập hợp này là tập sắp thứ tự riêng phần.

Ngược lại, từ bất kỳ quan hệ thứ tự riêng phần trên $S,$ ta có thể xây dựng tiền thứ tự trên chính $S$, bởi có tương ứng một-một giữa tập tiền thứ tự và các cặp (phân hoạch, thứ tự riêng phần).

Ví dụ: Cho $S$ là lý thuyết hình thức, tức là tập của các câu có tính chất đặc biệt (nội dung này có thể xem thêm trong bài viết về chủ đề đó). Chẳng hạn như, $S$ có thể là lý thuyết bậc nhất (ví dụ lý thuyết tập hợp Zermelo–Fraenkel) hoặc đơn giản hơn là lý thuyết bậc không. Một trong rất nhiều tính chất của $S$ là nó phải đóng dưới các hệ quả logic, ví dụ chẳng hạn, câu $A\in S$ theo logic suy ra câu $B,$ sẽ được viết là $A\Rightarrow B$ hoặc cũng được viết là $B\Leftarrow A,$ do đó phải $B\in S$ (theo modus ponens).

Quan hệ $\,\Leftarrow \,$ là tiền thứ tự trên $S$ bởi $A\Leftarrow A$ luôn đúng và bất cứ khi nào $A\Leftarrow B$ và $B\Leftarrow C$ đều đúng thì cũng $A\Leftarrow C.$ HƠn nữa, cho bất kỳ $A,B\in S,$ $A\sim B$ khi và chỉ khi $A\Leftarrow B{\text{ và }}B\Leftarrow A$; tức là, hai câu tương đương với nhau tương ứng với quan hệ $\,\Leftarrow \,$ khi và chỉ khi chúng tương đương logic với nhau. Quan hệ tương đương cụ thể này $A\sim B$ thường được ký hiệu bằng ký hiệu riêng của nó $A\iff B,$ và do vậy, ký hiệu $\,\iff \,$có thể dùng thay $\,\sim .$ Lớp tương đương của câu $A,$ được ký hiệu bởi $[A],$ bao gồm tất cả các câu $B\in S$ tương đương logic với $A$ (tức là, tất cả các câu $B\in S$ sao cho $A\iff B$). Quan hệ thứ tự riêng phần trên $S/\sim$ cảm sinh bởi $\,\Leftarrow ,\,$ sẽ được ký hiệu cùng ký hiệu $\,\Leftarrow ,\,$ định nghĩa như sau: $[A]\Leftarrow [B]$ khi và chỉ khi $A\Leftarrow B,$ trong đó điều kiện vế phải không phụ thuộc lựa chọn đại diện câu $A\in [A]$ và $B\in [B]$ của các lớp tương đương. Tất cả những gì đã nói về $\,\Leftarrow \,$ có thể áp dụng tương tự cho quan hệ ngược$\,\Rightarrow .\,$ Tập sắp tiền thứ tự $(S,\Leftarrow )$ là tập có hướng bởi nếu $A,B\in S$ và nếu $C:=A\wedge B$ ký hiệu câu được lập bởi phép logic hội $\,\wedge ,\,$ thì $A\Leftarrow C$ và $B\Leftarrow C$ khi $C\in S.$ Do vậy, theo hệ quả, tập $\left(S/\sim ,\Leftarrow \right)$ cũng là tập có hướng. Xem đại số Lindenbaum–Tarski để thêm ví dụ.

Tiền thứ tự nghiêm ngặt

Tiền thứ tự nghiêm ngặt cảm sinh bởi tiền thứ tự

Cho tiền thứ tự $\,\lesssim ,$ một quan hệ mới $\,<\,$ có thể định nghĩa theo $a<b$ khi và chỉ khi $a\lesssim b{\text{ và không }}b\lesssim a.$ Sử dụng quan hệ tương đương $\,\sim \,$ giới thiệu ở trên, $a<b$ khi và chỉ khi $a\lesssim b{\text{ và không }}a\sim b;$ do đó thoả mãn mệnh đề sau

$$a\lesssim b\quad {\text{ khi và chỉ khi }}\quad a<b\;{\text{ hoặc }}\;a\sim b.$$

Quan hệ $\,<\,$ là quan hệ thứ tự riêng phần nghiêm ngặt và mọi thứ tự riêng phần nghiêm ngặt đều có thể xây dựng theo cách này. Nếu tiền thứ tự $\,\lesssim \,$ phản đối xứng (và do đó là quan hệ thứ tự riêng phần) thì quan hệ tương đương $\,\sim \,$ là quan hệ bằng nhau (tức là, $a\sim b$ khi và chỉ khi $a=b$), do vậy trong trường hợp này, định nghĩa của $\,<\,$ có thể phát biểu lại thành:

$$a<b\quad {\text{ khi và chỉ khi }}\quad a\leq b\;{\text{ và }}\;a\neq b\quad \quad ({\text{giả định rằng }}\lesssim {\text{ phản đối xứng}}).$$

Quan trọng hơn, điều kiện mới này không được dùng (hay tương đương với) định nghĩa chung của quan hệ $\,<\,$ (tức là, $\,<\,$ không được định nghĩa: $a<b$ khi và chỉ khi $a\lesssim b{\text{ và }}a\neq b$) bởi vì nếu tiền thứ tự $\,\lesssim \,$ không phản đối xứng thì quan hệ thu được $\,<\,$ sẽ không có tính bắc cầu (xét quan hệ của các phần tử không bằng nhau). Đây cũng là lý do dùng "$\lesssim$" thay vì dấu "nhỏ hơn hoặc bằng $\leq$", bởi dấu sau có thể gây nhầm lẫn do gợi ý rằng $a\leq b$ tức $a<b{\text{ hoặc }}a=b.$

Số tiền thứ tự

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	2n2		2n2−n	2n(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ó tương ứng một-một giữa các tiền thứ tự và các cặp (phân hoạch của thứ tự riêng phần). Do đó số tiền thứ tự bằng với tổng của số các quan hệ thứ tự riêng phần trên mọi phân hoạch. Ví dụ như sau:

• Với $n=3:$
  • 1 phân hoạch của 3, có 1 tiền thứ tự
  • 3 phân hoạch của 2 + 1, cho $3\times 3=9$ tiền thứ tự
  • 1 phân hoạch của 1 + 1 + 1, cho 19 tiền thứ tự.
  Tính tổng lại ta được 29 tiền thứ tự
• Với $n=4:$
  • 1 phân hoạch của 4, cho 1 tiền thứ tự
  • 7 phân hoạch của hai lớp (4 của 3 + 1 và 3 của 2 + 2), cho $7\times 3=21$ tiền thứ tự
  • 6 phân hoạch của 2 + 1 + 1, cho $6\times 19=114$ tiền thứ tự
  • 1 phân hoạch của 1 + 1 + 1 + 1, cho 219 tiền thứ tự
  Tính tổng lại ta được 355 tiền thứ tự

Xem thêm

• Quan hệ thứ tự riêng phần – tiền thứ tự có tính phản xứng
• Quan hệ tương đương – tiền thứ tự có tính đối xứng
• Tiền thứ tự toàn phần – tiền thứ tự có tính toàn phần
• Thứ tự toàn phần – tiền thứ tự phản xứng và toàn phần
• Tập có hướng
• Phạm trù các tập sắp tiền thứ tự
• Tiền thứ tự tốt
• Tựa thứ tự tốt

Tham khảo

• Schmidt, Gunther, "Relational Mathematics", Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press, 2011, ISBN 978-0-521-76268-7
• Schröder, Bernd S. W. (2002), Ordered Sets: An Introduction, Boston: Birkhäuser, ISBN 0-8176-4128-9