Lý thuyết thứ tự

Lý thuyết thứ tự là một nhánh trong toán học nghiên cứu thuật ngữ thứ tự bằng cách sử dụng các quan hệ hai ngôi. Nó cho một khung hình thức để có thể mô tả các phát biểu như "cái này nhỏ hơn cái kia" hoặc "cái kia đứng trước cái này". Bài viết này sẽ giới thiệu về nhánh và cho một số định nghĩa cơ bản. Danh sách các thuật ngữ trong lý thuyết thứ tự có thể xem trong các thuật ngữ lý thuyết thứ tự.
Lý do thúc đẩy.
Thứ tự có mặt ở nhiều nơi trong toán học và các ngành liên quan như khoa học máy tính. Thứ tự đầu tiên được dạy và nhắc đến trong tiểu học là các thứ tự chuẩn trên số tự nhiên ("2 nhỏ hơn 3", "7 lớn hơn 4", "Phương có nhiều bánh hơn Nga"). Khái niệm trực quan này sau đó có thể mở rộng cho các tập khác như tập số nguyên và tập số thực. Ý tưởng rằng việc một số lớn hơn hay nhỏ hơn số kia là một trong những trực giác cơ bản của các hệ thống số (so với hệ đếm) trong tổng quát (mặc dù bên cạnh đó, ta cũng có thể quan tâm tới khoảng cách giữa hai số đó, song khoảng cách này không lấy được từ thứ tự). Một ví dụ thường gặp khác là sắp xếp theo thứ tự bảng chữ cái của các từ trong từ điển và tính chất gia phả trong một nhóm người. 
Thuật ngữ thứ tự rất tổng quát, mở rộng trên cả các ngữ cảnh có trực giác trực tiếp về dãy số hay số lượng. Trong các ngữ cảnh khác, thứ tự có thể dùng để nói đến các thuật ngữ chứa trong hay là trường hợp đặc biệt của. Các loại thứ tự đó thường là quan hệ bao hàm, ví dụ như "bác sĩ là nhà khoa học" và "đường tròn là trường hợp đặc biệt của đường elip)"
Một số thứ tự khác, chẳng hạn như "nhỏ hơn" trên các số tự nhiên và thứ tự bảng chữ cái trên các từ, có tính chất đặc biệt sau: mỗi phần tử đều có thể so sánh được với bất kỳ phần tử còn lại (tức là nó chỉ có thể lớn hơn (đứng trước) hoặc nhỏ hơn (đứng sau) hoặc bằng nhau. Tuy nhiên, có nhiều thứ tự khác không có tính chất đó. Xét thứ tự là tập con của trên họ các tập hợp. Mặc dù tập các con cá và tập các con mèo đều là tập con của tập các con vật, tập cá và tập mèo đều không phải là tập con của tập còn lại. Các thứ tự giống với thứ tự "là tập con của" ở chỗ tồn tại một số cặp phần tử không so sánh được thì được gọi là thứ tự riêng phần, thứ tự mà mọi cặp phần tử so sánh được thì được gọi là thứ tự toàn phần.
Lý thuyết thứ tự thường tổng quát hoá các khái niệm thứ tự trong các ví dụ trên thành các khái niệm trừu tượng hơn. Để làm vậy, ta thường buộc ≤ phải là thứ tự trong toán học. Cách làm này giúp ta có thể định nghĩa và tìm ra nhiều định lý rút ra từ đấy mà không phải tập trung vào một thứ tự cụ thể. Các nội dung tìm ra được sau đó có thể áp dụng vào các ứng dụng ít trừu tượng hơn.
Bởi tính hữu dụng của thứ tự, rất nhiều dạng đặc biệt của tập được sắp được định nghĩa thêm vào, và một số trong số đó đã trở thành nhánh toán học của riêng nó. Bên cạnh đó, lý thuyết thứ tự không chỉ giới hạn xét các lớp quan hệ thứ tự mà còn xét cả các hàm giữa chúng. Một ví dụ đơn giản từ lý thuyết thứ tự cho hàm số đến từ các hàm đơn điệu thường gặp trong giải tích.
Định nghĩa cơ bản.
Phần này giới thiệu tập được sắp bằng cách xây dựng trên các khái niệm của lý thuyết tập hợp, số học và quan hệ hai ngôi.
Tập hợp sắp thứ tự riêng phần.
Thứ tự là một quan hệ hai ngôi đặc biệt. Gọi "P" là một tập hợp và ≤ là quan hệ trên tập "P" ('quan hệ "trên" tập hợp' được hiểu là 'quan hệ "giữa" các phần tử của nó'). Quan hệ ≤ được gọi là thứ tự riêng phần khi nó có tính phản xạ, phản đối xứng và bắc cầu, nghĩa là với mọi "a", "b" và "c" thuộc "P", ta có:
Tập hợp đi cùng thứ tự riêng phần được gọi là tập sắp thứ tự riêng phần, poset, hoặc tập được sắp nếu đã rõ ngữ cảnh. Bằng cách kiểm tra các tính chất này, ta sẽ nhận thấy ngay các thứ tự đã biết trên số tự nhiên, số nguyên, số hữu tỉ và số thực đều thuộc cùng loại thứ tự này. Song các ví dụ này có thêm một tính chất nữa là mọi hai phần tử đều so sánh được với nhau, tức là với mọi "a" và "b" thuộc "P", ta có:
Thứ tự riêng phần thêm tính chất này thì được gọi là thứ tự toàn phần. Thứ tự toàn phần cũng được gọi là thứ tự tuyến tính hoặc xích. Có nhiều thứ tự thường gặp là tuyến tính , trong khi đó thứ tự bao hàm trên các tập hợp là một ví dụ về thứ tự riêng phần không phải toàn phần.Một ví dụ khác đến từ quan hệ chia hết formula_1. Cho hai số tự nhiên "n" và "m", ta viết "n" formula_1 "m" nếu không có phần dư khi chia n cho m. Dễ thấy đây là thứ tự riêng phần.
Quan hệ đơn vị = trên bất kỳ tập hợp cũng là thứ tự riêng phần trong đó mỗi hai phần tử phân biệt không so sánh được với nhau, nó cũng là quan hệ duy nhất vừa là thứ tự riêng phần vừa là quan hệ tương đương. Có một số tính chất đặc biệt của poset chỉ giới hạn cho thứ tự phi tuyến tính.
Vẽ biểu đồ.
Biểu đồ Hasse có thể dùng để hiển thị các phần thử và các quan hệ trong thứ tự riêng phần. Đây là đồ thị mà các đỉnh là các phần tử của và các cạnh và hướng của nó là của quan hệ trên tập hợp đó. Thứ tự thường được vẽ từ dưới lên: nếu phần tử "x" nhỏ hơn (đứng trước) "y" thì tồn tại đường đi từ "x" đến "y" và hướng lên trên. 
Có một số thứ tự vô hạn vẫn có thể vẽ biểu đồ được bằng cách vẽ thêm (...) cho thứ tự con hữu hạn. Cách này áp dụng được đối với các số tự nhiên, nhưng không đối với các số thực, bởi không có số kế tiếp này ngay sau 0.
Các phần tử đặc biệt trong thứ tự.
Trong tập hợp sắp thứ tự riêng phần, có một số phần tử đóng vai trò đặc biệt. Ví dụ cơ bản là phần tử nhỏ nhất của poset. Ví dụ chẳng hạn, 1 là phần tử nhỏ nhất trong các số nguyên dương và tập rỗng là tập nhỏ nhất dưới thứ tự tập con. Dưới hình thức, phần tử "m" là phần tử nhỏ nhất nếu:
Ký hiệu 0 thường dùng cho phần tử nhỏ nhất, kể cả khi không có số nào được xét. Tuy nhiên, trên tập các con số, ký hiệu này có thể gây nhầm lẫn và không rõ nghĩa vì số 0 không phải lúc nào cũng cũng là phần tử nhỏ nhất. Một ví dụ đến từ thứ tự là ước của |, trong đó 1 là phần tử nhỏ nhất vì nó là ước của tất cả các số còn lại. Ngược lại, 0 là số chia hết cho mọi số còn lại. Do đó, nó là phần tử lớn nhất của thứ tự. Các tên gọi cho phần tử nhỏ nhất và lớn nhất bao gồm không và đơn vị.
Phần tử lớn nhất và phần tử nhỏ nhất có thể không tồn tại, như ví dụ của các số thực cho thấy. Nhưng nếu chúng tồn tại, thì chúng sẽ là duy nhất. Trái lại, xét quan hệ là ước của | trên tập hợp{2,3,4,5,6}. Mặc dù tập này không có lớn nhất hay nhỏ nhất, các phần tử 2, 3, và 5 không có phần tử nào dưới chúng, trong khi 4, 5 và 6 không có cái nào ở trên. Các phần tử đó được gọi là phần tử tối tiểu và phần tử tối đại. Dưới hình thức, phần tử "m" là phần tử tối tiểu nếu:
Thay ≤ với ≥ ra định nghĩa của phần tử tối đại. Như ví dụ trên đã cho thấy, có thể có vô số phần tử vừa tối đại vừa tối tiểu (ví dụ như 5 trong ví dụ trên). Tuy nhiên, nếu có phần tử nhỏ nhất thì phần tử đó sẽ là phần tử tối tiểu duy nhất. Và, trong các poset vô hạn, các phần tử tối đại chưa chắc đã tồn tại, ví dụ chẳng hạn, tập hợp các tập con "hữu hạn" của một tập vô hạn cho trước, khi sắp xếp theo thứ tự bao hàm sẽ không có phần tử tối đại. Bổ đề Zorn là một công cụ quan trọng đảm bảo sự tồn tại của các phần tử tối đại dưới một số điều kiện. 
Tập con của tập sắp thứ tự riêng phần thừa kế thứ tự của tập hợp đó.Ngay từ ví dụ trên, tập con {2,3,4,5,6} của tập các số tự nhiên đã thừa hưởng thứ tự là ước của. Trong poset, sẽ có một số phần tử đặc biệt tương ứng với một số tập con của thứ tự. Điều này dẫn tới định nghĩa của cận trên. Cho tập con "S" của poset "P", cận trên của "S" là một phần tử "b" thuộc "P" và đứng trên mọi phần tử thuộc "S". Dưới hình thức, có nghĩa là
Cận dưới được định nghĩa bằng cách đảo ngược lại thứ tự. Lấy ví dụ khi xét tập các số tự nhiên là tập con của các số nguyên thì, -5 sẽ là cận dưới của các số tự nhiên. Cho tập của các tập hợp, cận trên của các tập hợp này dưới thứ tự bao hàm là hợp của các tập hợp đó. Hơn nữa, cận trên này còn có một tính chất đặc biệt khác: nó là tập hợp nhỏ nhất chứa tất cả các tập hợp. Người ta gọi cận trên này là cận trên nhỏ nhất (hay cận trên đúng). Khái niệm này còn được gọi là supremum hay nối, và đối với tập hợp "S," ta viết sup("S") hoặc formula_3 cho cận trên nhỏ nhất. Ngược lại, cận dưới lớn nhất (hay còn gọi là cận dưới đúng hoặc infimum hoặc gặp) được ký hiệu là inf("S") hoặc formula_4. Các khái niệm đóng vai trò quan trong nhiều ứng dụng của lý thuyết thứ tự. Cho hai phần tử "x" và "y", ta có thể viết formula_5 và formula_6 cho sup({"x","y"}) và inf({"x","y"}), tương ứng
Ví dụ chẳng hạn, 1 là infimum của các số nguyên dương là tập con của các số nguyên.
Xét lại lần nữa quan hệ "là ước của" trên các số tự nhiên. Cận trên nhỏ nhất của hai số này là số nhỏ nhất chia hết cho cả hai số đó (tức là bội chung nhỏ nhất). Ngược lại, cận dưới lớn nhất sẽ là ước chung lớn nhất.
Đối ngẫu.
Trong các định nghĩa trước, ta nhận thấy rằng một khái niệm mới hoàn toàn có thể thu về được bằng cách đảo ngược lại thứ tự từ định nghĩa trước, chẳng hạn như "lớn nhất" và "nhỏ nhất", "tối tiểu" và "tối đại", "cận trên" và "cận dưới", và tiếp tục như vậy, Đây là một tình huống thường gặp trong lý thuyết thứ tự: một thứ tự cho trước có thể đổi ngược nó đi bằng cách đổi hướng (hình dung bằng cách lật biểu đồ Hasse thành từ trên xuống), thứ tự mới thu được thường được gọi là đối ngẫu, nghịch đảo hay ngược,
Mọi định nghĩa trong lý thuyết thứ tự đều có dạng đối ngẫu của nó: thuật ngữ mới thu được bằng áp dụng định nghĩ cho thứ tự ngược. Bởi mọi khái niệm trong đây đều đối xứng, phép toán này bảo toàn các định lý của các thứ tự riêng phần. Đối với các kết quả toán học, ta chỉ cần đảo ngược lại thứ tự và thay tất cả các định nghĩa có liên quan bằng dạng đối ngẫu của chúng để thu được một định lý hợp lệ khác. Ý nghĩa này quan trọng và hữu dụng bởi ta sẽ thu về được hai định lý từ một kết quả. Xem đối ngẫu trong lý thuyết thứ tự để hiểu rõ hơn
Xây dựng thứ tự mới.
Có nhiều cách để xây dựng thứ tự mới từ thứ tự cho trước. Thứ tự đối ngẫu là một ví dụ trong đó. Một ví dụ quan trọng khác là tích Đề-các của hai tập hợp sắp thứ tự riêng phần đi kèm thứ tự tích.Thứ tự tích được định nghĩa bởi ("a", "x") ≤ ("b", "y") khi (và chỉ khi) "a" ≤ "b" nếu "x" ≤ "y". (Lưu ý cẩn thận rằng có ba ý nghĩa khác nhau cho ký hiệu quan hệ ≤ trong định nghĩa này.) Hợp không giao của hai poset là một ví dụ thường gặp khi xây dựng, trong đó thứ tự mới là hợp (không giao) của hai thứ tự ban đầu.
Mọi thứ tự riêng phần ≤ đều cảm sinh thứ tự ngặt tương ứng &lt;, bằng cách định nghĩa "a" &lt; "b" nếu "a" ≤ "b" và không "b" ≤ "a". Biến đổi này có thể đảo ngược lại thành "a" ≤ "b" nếu "a" &lt; "b" hoặc "a" = "b". Hai khái niệm này tương đương với nhau, song trong một số hoàn cảnh có thể sẽ có cái thuận lợi khi làm việc với nó
Hàm giữa các thứ tự.
Ta cũng cần quan tâm tới các hàm giữa các tập hợp sắp thứ tự riêng phần có các tính chất liên quan đến quan hệ thứ tự giữa hai tập hợp. Một trong điều kiện nền tảng trong ngữ cảnh này là tính đơn điệu. Hàm "f" từ poset "P" sang poset "Q" được gọi là đơn điệu, hay bảo toàn thứ tự, nếu "a" ≤ "b" trong "P thì" "f"("a") ≤ "f"("b") trong "Q" (Lưu ý rằng mặc dù viết chung ký hiệu ≤, hai dấu đó biểu hiện cho hai quan hệ khác nhau bởi chúng thuộc hai tập hợp khác nhau). Ngược với phép suy này là các hàm phản xạ thứ tự, tức là các hàm "f" sao cho nếu "f"("a") ≤ "f"("b") thì "a" ≤ "b". Mặt khác, hàm số có thể được gọi là hàm đảo thứ tự,hay còn gọi phản điệu (antitone) nếu "a" ≤ "b" thì "f"("a") ≥ "f"("b").
Phép nhúng thứ tự là hàm "f" giữa các thứ tự vừa có tính bảo toàn thứ tự và phản xạ thứ tự. Các ví dụ cho định nghĩa này thường dễ tìm thấy, Ví dụ chẳng hạn, dễ thấy hàm ánh xạ số tự nhiên sang số kế tiếp của nó đơn điệu và phản xạ thứ tự tương ứng với thứ tự tự nhiên. Bất cư hàm số đến từ tập rời rạc (tập rời rạc là tập được sắp theo thứ tự đơn vị "=", cũng có tính đơn điệu. Ánh xạ từng số tự nhiên sang số thực tương ứng là ví dụ về phép nhúng thứ tự. Hàm lấy phần bù trên tập luỹ thừa là ví dụ về hàm phản điệu.
Một câu hỏi đặt ra là liệu hai thứ tự có "thực chất như nhau" không, tức là liệu chúng đều có phải là một khi xét về cấu trúc? Đẳng cấu thứ tự được dùng trả lời câu hỏi đó. Đẳng cấu thứ tự là song ánh đơn điệu có nghịch đảo cũng đơn điệu. Đẳng cấu này tương đương với phép nhúng thứ tự mà là toàn ánh. Do đó, ảnh "f"("P") của phép nhúng thứ tự luôn đẳng cấu với "P", và vì thế mới có từ "nhúng".
Một loại hàm khác được sinh ra từ các liên thông Galois. Liên thông Galois đơn điệu có thể xem là dạng tổng quát của các đẳng cấu thứ tự, bởi vì nó sinh ra cặp hai phần tử có hướng ngược nhau, nhưng "chưa chắc" đã là nghịch đảo của nhau, song vẫn có quan hệ gần gũi với nhau.
Một loại hàm khác ánh xạ từ poset lên chính nó là các toán tử bao đóng, các toán tử không những đơn điệu mà còn luỹ đẳng, tức là "f"("x") = "f"("f"("x")), và bao quát ,tức. "x" ≤ "f"("x"). Có nhiều ứng dụng cho nhiều "bao đóng" xuấthh iện trong toán học.
Không những phải tương thích với quan hệ thứ tự, các hàm giữa các poset còn phải thoả mãn một số yêu cầu liên quan tới các phần tử đặc biệt và phương pháp xây dựng. Ví dụ chẳng hạn, khi nói đến các poset có phần tử nhỏ nhất, thì ta cần yêu cầu rằng hàm số giữa các hàm đơn điệu giữa các poset đó phải bảo toàn phần tử này (tức là ánh xạ phần tử nhỏ nhất của tập này sang phần tử nhỏ nhất của tập kia). Nếu phép toán hai ngôi infima ∧ tồn tại, thì cũng có thể yêu cầu thêm rằng "f"("x" ∧ "y") = "f"("x") ∧ "f"("y"), với mọi "x" và "y". Tất cả tính chất này và nhiều tính chất khác đều nằm dưới lớp các hàm bảo toàn giới hạn.
Cuối cùng, ta có thể đổi góc nhìn, từ "hàm của các thứ tự" sang "thứ tự của các hàm". Thật vậy, tập các hàm giữa poset "P" và "Q" có thể sắp bằng thứ tự từng điểm. Cho hai hàm "f" và "g", ta có "f" ≤ "g" nếu "f"("x") ≤ "g"("x") với mọi "x" thuộc "P". Nội dung này xuất hiện trong lý thuyết miền, trong đó các không gian hàm đóng vai trò quan trọng
Các loại quan hệ đặc biệt.
Trong lý thuyết thứ tự, có một số khái niệm quan hệ được để ý tới mặc dù không quan tâm tới thứ tự riêng phần, và một trong những cái thường được nhắc tới phải là khái niệm của tiền thứ tự. Tiền thứ tự là quan hệ hai ngôi có tính phản xạ và đối xứng nhưng không nhất thiết phải phản đối xứng. Mỗi tiền thứ tự đều cảm sinh quan hệ tương đương tương ứng với nó, trong đó "a" tương đương với "b", nếu "a" ≤ "b" và "b" ≤ "a". Tiền thứ tự có thể biến đổi thành thứ tự thật bằng cách xác định tất cả các phần tử tương đương với nhau tương ứng với quan hệ này.
Nhiều loại quan hệ có thể được định nghĩa từ dữ liệu số trên các phần tử trong thứ tự: Thứ tự toàn phần lấy từ việc gán một số thực phân biệt cho mỗi phần tử và dùng số thực đó để so sánh giữa các phần tử; nếu như cho phép một số phần tử phân biệt có cùng một giá trị thì ta sẽ thu được thứ tự yếu nghiêm ngặt. Nếu yêu cầu hai số đó phải cách nhau theo ngưỡng cố định nào đó để chúng có khi so sánh được thì thứ tự đó được gọi là nửa thứ tự, và nếu cho phép ngưỡng đó phụ thuộc vào phần tử đang xét, thì ta thu được thứ tự khoảng.
Một tính chất khác hữu dụng được thêm vào dẫn tới định nghĩa của quan hệ lập tốt là yêu cầu mọi tập con khác rỗng phải có phần tử nhỏ nhất. Và để tổng quát hoá cho các thứ tự tốt từ tuyến tính tới riêng phần, ta gọi một tập hợp là tập sắp thứ tự riêng phần tốt nếu tất cả tập con khác rỗng của nó hữu hạn số phần tử tối tiểu.
Nhiều loại thứ tự khác nảy sinh khi đã đảm bảo trước sự tồn tại của infima và suprema của tập hợp. Tính chất này được gọi là tính đầy đủ của thứ tự, khi tập trung vào tính chất, ta thu được:
Thậm chí, ta có thể đi xa hơn nữa: Nếu tồn tại cận trên cho tập hữu hạn khác rỗng, thì ∧ có thể xem là phép toán hai ngôi theo cách của đại số phổ dụng. Do đó, trong dàn khi thêm hai phép toán ∧ và ∨, ta có thể định nghĩa các tính chất mới bằng các định thức như
Điều kiện này được gọi là tính phân phối và nó nảy sinh ra định nghĩa của dàn phân phối. Có nhiều luật phân phối quan trọng được nhắc trong bài tính phân phối trong lý thuyết thứ tự. Một số cấu trúc thứ tự thêm vào thường được định nghĩa qua các phép toán đại số và các định thức. Một số ví dụ quan trọng bao gồm
trong đó cả hai đều giới thiệu phép phủ ~. Cả hai đều đóng vai trò quan trọng trong logic toán học, và đặc biệt đại số Boole có ứng dụng rộng rãi trong khoa học máy tính.
Ngoài ra, nhiều cấu trúc trong toán học gộp thứ tự với nhiều phép toán đại số khác, ví dụ như cácquantale chẳng hạn, chúng cho phép định nghĩa thêm phép cộng.
Tồn tại nhiều tính chất quan trọng khác của poset. Chẳng hạn như, một poset được gọi là hữu hạn địa phương nếu mọi khoảng đóng ["a", "b"] của nó hữu hạn. Poset hữu hạn địa phương từ đó sẽ nảy sinh thành các đại số liên thuộc, và rồi chính các đại số được dùng để định nghĩa đặc trưng Euler của poset bị chặn hữu hạn.
Tập con của tập được sắp.
Trong tập được sắp, ta có thể định nghĩa nhiều loại tập con đặc biệt dựa trên thứ tự cho sẵn. Một ví dụ đơn giản là khái niệm tập trên: tập trên là tập chứa các phần tử cùng với các phần tử ở trên chúng trong thứ tự. Bao đóng trên của tập hợp "S" trong "poset" "P" được định nghĩa là tập {"x" thuộc "P" | tồn tại "y" thuộc "S" sao cho "y" ≤ "x"}. Tập trên bằng với bao đóng trên của chính nó . Tập dưới được định nghĩa ngược lại.
Lịch sử.
Như đã giải thích ở trên, thứ tự xuất hiện ở nhiều nơi trong toán học. Tuy nhiên lần đầu nhắc tới khái niệm thứ tự riêng phần mới chỉ xuất hiện không lâu trước thế kỷ 19. Vào thời đó, công trình của George Boole có ảnh hưởng lớn. Ngoài ra, Charles Sanders Peirce, Richard Dedekind, và Ernst Schröder cũng có xét đến các khái niệm trong lý thuyết thứ tự.
Những nhà cống hiến cho hình học được sắp được ghi chép lại trong một cuốn giáo trình năm 1961:
"(Dịch: Trong 1882, Pasch chính là người đầu tiên chỉ ra rằng hình học của thứ tự có thể được phát triển thêm mà không cần phải tham chiếu độ đo. Hệ tiên đề của ông sau được dần cải thiện bởi Peano (1889), Hilbert (1899) và Veblen (1904))"
Trong 1901, Bertrand Russell viết "On the notion of order" khám phá nền tảng của ý tưởng này thông qua quá trình sinh quan hệ chuỗi. Ông quay lại chủ đề này trong phần 4 của cuốn "The Principles of Mathematics" (1903).