Quan hệ hai ngôi trên một tập hợp

Quan hệ hai ngôi trên một tập hợp là quan hệ hai ngôi được định nghĩa giữa hai tập hợp giống nhau.

Ví dụ

Quan hệ hai ngôi trên một tập hợp là một loại quan hệ hai ngôi đặc biệt, trong đó hai tập nền trùng nhau. Như vậy quan hệ hai ngôi trên một tập hợp là quan hệ R thoả mãn R ⊆ M × M.

Quan hệ “lớn hơn” là quan hệ hai ngôi trên một tập hợp, vì ở cả hai vị trí đều là các số. Tức là > ⊆ ℝ × ℝ. Quan hệ “bố — số con” không phải quan hệ hai ngôi trên một tập hợp, vì người bố được chọn từ tập hợp tất cả mọi người, còn số con được chọn từ một tập số nào đó.

Các tính chất

Quan hệ hai ngôi R trên tập hợp M có thể có một số tính chất thú vị. Ta nói quan hệ R có tính chất…

• phản xạ nếu với mọi a ∈ M ta có (a; a) ∈ R.
• đối xứng nếu với mọi a, b ∈ M, từ (a; b) ∈ R suy ra (b; a) ∈ R.
• phản đối xứng nếu với mọi a, b ∈ M, từ (a; b) ∈ R và (b; a) ∈ R suy ra a = b.
• bắc cầu nếu với mọi a, b, c ∈ M, từ (a; b) ∈ R và (b; c) ∈ R suy ra (a; c) cũng thuộc R.

Ví dụ về tính phản xạ

Tính phản xạ nghĩa là mỗi phần tử có quan hệ với chính nó. Ví dụ điển hình là quan hệ bằng. Nếu quan hệ bằng được định nghĩa trên tập số tự nhiên thì chắc chắn với mọi phần tử a ta có a = a. Một ví dụ khác là quan hệ chia hết. Ở đây cũng vậy, số a chia hết cho chính nó, tức là cặp (a; a) thuộc quan hệ chia hết (7 chia hết cho 7).

Còn quan hệ nhỏ hơn thì không có tính phản xạ, vì không có a < a: số 7 không thể nhỏ hơn số 7. Quan hệ “là bố của con mình” cũng vậy — không ai là bố của chính mình. Những quan hệ như vậy không có tính phản xạ.

Điều quan trọng là tính phản xạ phải đúng với mọi phần tử, tìm được một vài phần tử thì chưa đủ. Chẳng hạn xét quan hệ “quý ai đó”. Tôi có thể quý một người khác, chẳng hạn nhân viên soát vé, nhưng cũng có thể quý chính mình. Chắc chắn có người quý chính mình. Nhưng cũng có người không quý chính mình. Vì vậy quan hệ này không có tính phản xạ — muốn vậy thì mọi người đều phải quý chính mình.

Ví dụ về tính đối xứng

Với quan hệ đối xứng, nếu một cặp thuộc quan hệ thì cặp ngược của nó cũng thuộc quan hệ. Chẳng hạn quan hệ “là anh chị em ruột”. Nếu Khoa là anh chị em ruột của Lan thì Lan cũng là anh chị em ruột của Khoa. Trong các quan hệ giữa các số, đó có thể là quan hệ “là số đối của nhau”, tức là các cặp như 2 và −2 hay −7 và 7: hai số có tổng bằng 0. Quan hệ này đối xứng vì thứ tự đơn giản là không quan trọng: (2; −2) và (−2; 2) vẫn là hai số đối của nhau và có tổng bằng 0.

Một quan hệ không đối xứng là quan hệ nhỏ hơn (trên tập số thực). Quan hệ này không có cặp đối xứng nào, vì không bao giờ có đồng thời a < b và b < a. Nếu 5 < 15 thì không thể có 15 < 5. Quan hệ “là bố của con trai mình” cũng không đối xứng: bạn có thể là bố của con trai mình, nhưng khi đó con trai không thể là bố của bố mình.

Tính chất này cũng phải đúng trong mọi trường hợp. Muốn quan hệ “quý ai đó” (trên tập hợp tất cả mọi người) đối xứng thì khi tôi quý một ca sĩ nổi tiếng, cô ấy cũng phải quý tôi. Nhưng cô ấy còn không biết tôi, nên tôi không thể nói rằng cô ấy quý tôi – thật đáng tiếc, và quan hệ này không đối xứng. Điều đó cũng thật đáng tiếc.

Ví dụ về tính phản đối xứng

Ví dụ kinh điển về quan hệ phản đối xứng là quan hệ nhỏ hơn hoặc bằng. Tính phản đối xứng nói rằng nếu cả hai cặp (a; b) và (b; a) đều thuộc quan hệ thì chỉ có thể là hai phần tử bằng nhau, a = b. Quan hệ nhỏ hơn hoặc bằng thoả mãn điều này. Khi nào ta có đồng thời a ≤ b và b ≤ a? Chỉ khi a = b. Thử thay số: có đồng thời 3 ≤ 5 và 5 ≤ 3 không? Không. Nhưng có đồng thời 4 ≤ 4 và 4 ≤ 4.

Ví dụ về quan hệ không phản đối xứng là quan hệ giữa hai từ có cùng độ dài, chẳng hạn (bàn; ghế). Quan hệ này không phản đối xứng, vì ta tìm được một cặp từ thuộc quan hệ, cặp ngược của nó cũng thuộc quan hệ, nhưng hai từ lại khác nhau. Đó chính là phần tử (bàn; ghế) vừa nêu và cặp ngược của nó: (ghế; bàn). Cả hai rõ ràng đều thuộc quan hệ của ta, nhưng bàn ≠ ghế, nên quan hệ không phản đối xứng.

Ví dụ về tính bắc cầu

Quan hệ nhỏ hơn có tính bắc cầu. Tính bắc cầu cho biết nếu 3 < 4 và 4 < 5 thì chắc chắn phải có 3 < 5. Với rất nhiều quan hệ, đây là một tính chất khá tự nhiên. Ví dụ về các từ cùng độ dài cũng vậy: nếu (ghế; bàn) thuộc quan hệ và (bàn; cửa) thuộc quan hệ thì cặp từ (ghế; cửa) cũng thuộc quan hệ.

Quan hệ “là bố của con trai mình” không có tính bắc cầu. Nếu Quang là bố của Minh và Minh là bố của Long thì Quang không phải bố của Long mà là ông nội. Quan hệ “quý ai đó” cũng không có tính bắc cầu. Nếu tôi quý một người bạn và người bạn đó quý chồng mình thì không có nghĩa là tôi cũng quý chồng của bạn ấy.

Tính bắc cầu còn được xét với những con xúc xắc thông thường. Giả sử con xúc xắc A có quan hệ “tốt hơn” con xúc xắc B nếu khi gieo, con xúc xắc A ra số lớn hơn con xúc xắc B thường xuyên hơn (với xác suất lớn hơn). Quan hệ này có tính bắc cầu không? Câu trả lời có trong bài xúc xắc không bắc cầu.

Quan hệ tương đương và quan hệ thứ tự

Một số loại quan hệ hai ngôi đặc biệt có tên riêng:

• Quan hệ tương đương là quan hệ có tính phản xạ, đối xứng và bắc cầu.
• Quan hệ thứ tự là quan hệ có tính phản xạ, phản đối xứng và bắc cầu.