Quan hệ thứ tự

Quan hệ thứ tự là quan hệ hai ngôi trên một tập hợp có tính phản xạ, phản đối xứng và bắc cầu.

Vì sao cần quan hệ thứ tự

Sắp thứ tự là việc quen thuộc cả trong đời sống hằng ngày. Rất nhiều thứ có thể sắp xếp theo một cách nào đó — các từ theo bảng chữ cái, học sinh trong trường theo chiều cao, hàng hoá theo giá. Tất cả những điều này được mô tả bằng quan hệ thứ tự, thường kí hiệu là ≤. Các kí hiệu liên quan là <, >, ≥, ý nghĩa của chúng thì đã rõ.

Ta mong đợi gì ở một quan hệ như vậy? Ngay từ kí hiệu đã thấy quan hệ thứ tự chứa cả những cặp phần tử bằng nhau — ta muốn định nghĩa các tính chất của quan hệ nhỏ hơn hoặc bằng. Vì vậy quan hệ này phải có tính phản xạ: phải có a ≤ a.

Tiếp theo thì sao? Chắc chắn không có tính đối xứng — khi sắp xếp theo giá, nếu ô tô rẻ hơn bánh mì thì chắc chắn bánh mì không đồng thời rẻ hơn ô tô. Nói chung, nếu xảy ra a ≤ b và đồng thời b ≤ a thì ta mong đợi điều gì? Điều đó có bao giờ hợp lí không? Có, nếu a = b. Trường hợp duy nhất mà thứ tự các phần tử trong cặp không quan trọng là khi hai phần tử bằng nhau — vậy quan hệ thứ tự có tính phản đối xứng.

Cuối cùng, nếu biết ô tô đắt hơn bánh mì và máy bay còn đắt hơn ô tô thì ta mong rằng máy bay chắc chắn đắt hơn bánh mì. Điều này được mô tả bằng tính bắc cầu.

Thứ tự bộ phận

Thứ ta vừa định nghĩa thực ra chỉ là thứ tự bộ phận, chưa phải thứ tự toàn phần. Vì sao? Hãy thử định nghĩa một thứ tự trên các tập hợp. So sánh hai tập hợp bằng cách nào?

Ta nói tập hợp A nhỏ hơn hoặc bằng tập hợp B nếu A ⊆ B, tức là A là tập con của B. Điều này hợp lí: với A = {1; 2} và B = {1; 2; 3}, có thể nói A nhỏ hơn — B chứa mọi phần tử của A và còn thêm số 3. Chẳng hạn ta có:

• {a; c} ≤ {a; b; c; d}
• ∅ ≤ {5; n; x}
• {x; e; s} ≤ {x; e; s}

Khó khăn xuất hiện khi ta muốn so sánh hai tập hợp A = {a; b} và B = {a; c}. Tập nào nhỏ hơn, tập nào lớn hơn? Cả hai đều chứa phần tử a, nhưng phần tử thứ hai lại khác nhau. Không tập nào là tập con của tập kia, nên không có A ≤ B mà cũng không có B ≤ A. Với thứ tự của ta, hai tập hợp này là không so sánh được.

Vì vậy ta định nghĩa tập sắp thứ tự toàn phần, còn gọi là xích: đó là tập hợp mà hai phần tử bất kì đều so sánh được. Chẳng hạn các tập số với thứ tự thông thường là những tập như vậy. Với hai số thực bất kì a, b, ta luôn xác định được a ≤ b hay b ≤ a.

Ví dụ đời thường

Một ví dụ mà không so sánh thì tốt hơn là sắp thứ tự theo vẻ đẹp: quan hệ < có nghĩa là “xấu hơn”. Có lẽ nên định nghĩa ngược lại, > là “đẹp hơn”, cho lịch sự hơn :-). So sánh hai người phụ nữ với nhau thì có lẽ có ý nghĩa, chẳng hạn “Hoa” < “Mai” theo nghĩa Mai đẹp hơn Hoa. Hay hai người đàn ông: “Hùng” < “Dũng” theo nghĩa Dũng đẹp hơn Hùng.

Vấn đề là khó mà so sánh vẻ đẹp của một người đàn ông với một người phụ nữ. Mai đẹp hơn hay Dũng đẹp hơn? Hoa xấu hơn hay Hùng xấu hơn? Tốt nhất là đừng tìm hiểu…

Nếu trong ví dụ trên ta chỉ xét những người phụ nữ thì có thể nói ta có một tập sắp thứ tự toàn phần, vì ta so sánh được vẻ đẹp của mọi người phụ nữ.

Phần tử cực tiểu và cực đại, phần tử nhỏ nhất và lớn nhất

Cho tập sắp thứ tự M. Phần tử min ∈ M gọi là phần tử cực tiểu nếu không tồn tại x ∈ M sao cho x < min. Tức là ta không tìm được phần tử nào nhỏ hơn phần tử min.

Phần tử max ∈ M gọi là phần tử cực đại nếu không tồn tại x ∈ M sao cho x > max. Tức là ta không tìm được phần tử nào lớn hơn.

Hai khái niệm trên khác với các khái niệm phần tử nhỏ nhất và lớn nhất.

Phần tử a ∈ M gọi là phần tử nhỏ nhất nếu với mọi x ∈ M ta có a ≤ x. Tức là phần tử nhỏ nhất a nhỏ hơn hoặc bằng mọi phần tử khác của tập hợp M.

Phần tử b ∈ M gọi là phần tử lớn nhất nếu với mọi x ∈ M ta có b ≥ x. Phần tử lớn nhất b lớn hơn hoặc bằng mọi phần tử khác của tập hợp M.

Phần tử lớn nhất và phần tử cực đại khác nhau ở chỗ nào? Có thể có nhiều phần tử cực đại, vì tập hợp không nhất thiết được sắp thứ tự toàn phần. Trở lại ví dụ so sánh người theo vẻ ngoài: giả sử Lan là người phụ nữ đẹp nhất và Tuấn là người đàn ông đẹp nhất. Nhưng hai người này thì ta không so sánh được với nhau, không biết Lan hay Tuấn đẹp hơn.

Vì vậy cả hai đều là phần tử cực đại. Ta không tìm được ai đẹp hơn Tuấn — Tuấn đẹp hơn mọi người đàn ông khác, còn với phụ nữ thì không so sánh được. Lan cũng vậy — cô đẹp hơn mọi người phụ nữ, còn với đàn ông thì không so sánh được.

Nhưng không ai trong hai người là phần tử lớn nhất, theo nghĩa ở đây là đẹp nhất. Muốn Tuấn là người đẹp nhất/phần tử lớn nhất thì Tuấn phải đẹp hơn tất cả mọi người, kể cả mọi người phụ nữ. Nhưng như đã nói, không so sánh được Tuấn với phụ nữ, nên Tuấn không thể là người đẹp nhất, mà theo thuật ngữ của lí thuyết thứ tự chỉ là phần tử cực đại.

Dễ thấy rằng nếu tập hợp có phần tử lớn nhất thì phần tử đó cũng là phần tử cực đại. Nếu phần tử a lớn hơn mọi phần tử khác của tập hợp (định nghĩa phần tử lớn nhất) thì chắc chắn không tìm được phần tử nào lớn hơn nó nữa (định nghĩa phần tử cực đại).

Một ví dụ về tập hợp có phần tử lớn nhất và phần tử nhỏ nhất là đoạn [0; 1]. Nếu thay bằng khoảng (0; 1) thì tập hợp không có phần tử lớn nhất, cũng không có phần tử nhỏ nhất.

Nếu muốn có vô hạn phần tử cực tiểu, ta có thể định nghĩa thứ tự R như sau. Trước hết định nghĩa các tập hợp phụ M_x có dạng: với mọi x thuộc khoảng (0; 1), đặt M_x = {y ∣ y = x + n}, trong đó n là số nguyên không âm. Chẳng hạn ta được các tập hợp sau:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Trên mỗi tập hợp M_x ta định nghĩa thứ tự thông thường, kí hiệu là R_x. Cuối cùng chỉ cần lấy hợp của các thứ tự này: R = ∪ R_x. Trong thứ tự này, ta chỉ so sánh được các phần tử thuộc cùng một xích ban đầu. Ta biết được có 0,5 ≤ 2,5 hay không, nhưng không biết được có 0,5 ≤ 2,7 hay không, vì hai số này không thuộc cùng một tập M_x nên quan hệ giữa chúng không được định nghĩa.

Trong quan hệ thứ tự này, mọi phần tử của khoảng (0; 1) đều là phần tử cực tiểu.

Biểu đồ Hasse

Tập sắp thứ tự có thể biểu diễn bằng biểu đồ Hasse. Đó là một đồ thị, trong đó các đỉnh biểu diễn các phần tử của tập hợp, còn cạnh nối hai đỉnh (a; b) cho biết a < b và không tồn tại c sao cho a < c < b. Tức là giữa hai phần tử a và b không còn phần tử nào khác. Ngoài ra, trên hình vẽ đỉnh a phải nằm thấp hơn đỉnh b. Ví dụ về biểu đồ Hasse:

Biểu đồ Hasse này biểu diễn tập sắp thứ tự {A; B; C; D; E; F}. Ở đây A < B, B < E, và tất nhiên A < E, nhưng giữa hai đỉnh này không có cạnh, vì có đỉnh B thoả mãn A < B < E. Hai phần tử E và D không so sánh được, vì không phần tử nào nằm trên hay dưới phần tử kia.

Biểu đồ Hasse thường được vẽ thẳng hàng gọn gàng như vậy, nhưng điều đó không bắt buộc. Biểu đồ Hasse ở trên cũng có thể trông như sau:

Một ví dụ khác là tập hợp A = {1; 2; 3; 4; 5; 6; 10; 12; 15; 20; 30; 60}, gồm các ước dương của 60. Thứ tự theo quan hệ chia hết có thể biểu diễn như sau:

Thứ tự theo quan hệ chia hết nghĩa là (a; b) ∈ R khi và chỉ khi a là ước của b. Trên biểu đồ ta thấy phía trên mỗi số là các số chia hết cho nó. Chẳng hạn phía trên số 6 có các số 12, 30 và 60. Phía trên số 4 có các số 12, 20 và 60, v.v. Ngược lại, phía trên số 3 không có số 10, vì 10 không chia hết cho 3 — chú ý, trên hình số 10 nằm cao hơn số 3, nhưng không có đường nào đi “từ dưới lên” từ số 3 đến số 10. Nếu từ số 3 chỉ đi lên, ta có thể đến các số 15 và 6, rồi từ đó đến số 30. Đến số 10 thì chỉ có thể bằng cách đi xuống, mà điều đó không được phép.