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ó:

: a ≤ a (phản xạ)
: Nếu a ≤ b và b ≤ a thì a = b (phản đối xứng)
: Nếu a ≤ b và b ≤ c thì a ≤ c (bắc cầu).

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ó:

: a ≤ b hoặc b ≤ a.

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 \vdots. Cho hai số tự nhiên n và m, ta viết n \vdots 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 đồ
phải|nhỏ|250x250px|Biểu đồ Hasse của tập các ước của số 60, sắp riêng phần bởi quan hệ là ước của
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:

: m ≤ a,với mọi a trong thứ tự.

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:

: a ≤ m thì a = m, với mọi a trong thứ tự.

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à

: s ≤ b, với mọi s thuộc S.

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 \bigvee S 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 \bigwedge S. 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 x\vee y và x\wedge y 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 sao cho a \leq a^{} \implies a = 0.

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ư

: x&nbsp;∧&nbsp;(y&nbsp;∨&nbsp;z) &nbsp;=&nbsp; (x&nbsp;∧&nbsp;y)&nbsp;∨&nbsp;(x&nbsp;∧&nbsp;z), với mọi x, y, và z.

Đ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

Đại số Heyting và
Đại số Boole,

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

Xem thêm

Thứ tự cyclic
Trật tự
Đại số liên thuộc
Tập hợp nhân quả

Chú thích

Tham khảo






Liên kết ngoài

Orders at ProvenMath partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory.
Nagel, Felix (2013). Set Theory and Topology. An Introduction to the Foundations of Analysis