Tiền thứ tự

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

Tên 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 formula_1 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 formula_2, ta có thể nói rằng "b" "a" hoặc "a" "b", hoặc "b" "a". Đôi khi, ký hiệu ← hoặc → hoặc formula_3 được dùng thay vì formula_4

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 formula_1 trên một số tập hợp formula_6 cho trước sao cho theo định nghĩa, formula_1 là một tập con của formula_8 và ký hiệu formula_9 được sử dụng thay cho formula_10 Khi đó, formula_1 được gọi là ' hoặc ' 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ạ: formula_12 với mọi formula_13 và
2. Tính bắc cầu: nếu formula_14 với mọi formula_15

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, trên formula_16 là quan hệ hai ngôi thuần nhất formula_17 trên formula_16 thoả mãn hai điều kiện sau:
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ệ formula_17 được gọi là nếu formula_20 với mọi formula_21 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à formula_9 và formula_23 thì formula_24) 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à formula_9 thì formula_26) thì được gọi là quan hệ tương đương.

Tiền thứ tự có tính toàn phần nếu formula_9 hoặc formula_23 với mọi formula_29

Tập sắp tiền thứ tự formula_16 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 formula_6 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 formula_32. 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 formula_33 khi và chỉ khi "x" nằm trong mọi lân cận của "y".
- Quan hệ định nghĩa bởi formula_33 nếu formula_35 trong đó "f" là hàm theo tiền thứ tự.
- Quan hệ định nghĩa bởi formula_33 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 formula_37 trên tập hợp formula_38 có thể mở rộng thành tiền thứ tự trên formula_38 bằng cách lấy bao đóng bắc cầu và bao đóng phản xạ, formula_40 Bao đóng bắc cầu nghĩa là có quan hệ đường đi formula_41 khi và chỉ khi có formula_37-đường đi từ formula_43 đến formula_44

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 formula_45 phần bù của hợp formula_46 tạo thành một tiền thứ tự được gọi là phần thặng dư trái, trong đó formula_47 là quan hệ ngược của formula_45 và formula_49 ký hiệu quan hệ bù của formula_45 trong khi formula_51 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ự formula_3 trên formula_38, ta có thể định nghĩa quan hệ tương đương trên formula_54 trên formula_38 sao cho 
formula_56 
Quan hệ thu được formula_54 có tính phản xạ bởi formula_3 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 formula_3 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 formula_60, tập thương là tập của tất cả các lớp tương đương của formula_61 Nếu tiền thứ tự được ký hiệu là formula_62 thì formula_63 là tập hợp của các lớp tương đương formula_37-chu trình: 
formula_65 khi và chỉ khi formula_66 hoặc formula_43 nằm trong formula_37-chu trình của formula_69.
Trong bất kỳ trường hợp, có thể định nghĩa trên formula_63 quan hệ formula_71 khi và chỉ khi formula_72 
Đị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 formula_73 và formula_74. 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 formula_75 ta có thể xây dựng tiền thứ tự trên chính formula_38, 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).

Quan hệ formula_85 là tiền thứ tự trên formula_38 bởi formula_87 luôn đúng và bất cứ khi nào formula_88 và formula_89 đều đúng thì cũng formula_90 
HƠn nữa, cho bất kỳ formula_91 formula_92 khi và chỉ khi formula_93; tức là, hai câu tương đương với nhau tương ứng với quan hệ formula_85 khi và chỉ khi chúng tương đương logic với nhau. Quan hệ tương đương cụ thể này formula_92 thường được ký hiệu bằng ký hiệu riêng của nó formula_96 và do vậy, ký hiệu formula_97có thể dùng thay formula_61 Lớp tương đương của câu formula_99 được ký hiệu bởi formula_100 bao gồm tất cả các câu formula_84 tương đương logic với formula_102 (tức là, tất cả các câu formula_84 sao cho formula_104). 
Quan hệ thứ tự riêng phần trên formula_63 cảm sinh bởi formula_106 sẽ được ký hiệu cùng ký hiệu formula_106 định nghĩa như sau: formula_108 khi và chỉ khi formula_109 trong đó điều kiện vế phải không phụ thuộc lựa chọn đại diện câu formula_110 và formula_111 của các lớp tương đương. 
Tất cả những gì đã nói về formula_85 có thể áp dụng tương tự cho quan hệ ngượcformula_113 
Tập sắp tiền thứ tự formula_114 là tập có hướng bởi nếu formula_115 và nếu formula_116 ký hiệu câu được lập bởi phép logic hội formula_117 thì formula_118 và formula_89 khi formula_120 Do vậy, theo hệ quả, tập formula_121 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ự formula_122 một quan hệ mới formula_17 có thể định nghĩa theo formula_124 khi và chỉ khi formula_125 
Sử dụng quan hệ tương đương formula_54 giới thiệu ở trên, formula_124 khi và chỉ khi formula_128 
do đó thoả mãn mệnh đề sau
formula_129
Quan hệ formula_17 là quan hệ thứ tự riêng phần nghiêm ngặt và thứ tự riêng phần nghiêm ngặt đều có thể xây dựng theo cách này. 
formula_136
Quan trọng hơn, điều kiện mới này được dùng (hay tương đương với) định nghĩa chung của quan hệ formula_17 (tức là, formula_17 được định nghĩa: formula_124 khi và chỉ khi formula_140) bởi vì nếu tiền thứ tự formula_3 không phản đối xứng thì quan hệ thu được formula_17 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 "formula_143" thay vì dấu "nhỏ hơn hoặc bằng formula_144", bởi dấu sau có thể gây nhầm lẫn do gợi ý rằng formula_9 tức formula_146

==Số tiền thứ tự==
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:

==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,