Quan hệ hai ngôi

Quan hệ hai ngôi là một loại quan hệ đặc biệt có số ngôi bằng 2. Các quan hệ hai ngôi điển hình gồm có nhỏ hơn, bằng, chia hết, lớn hơn, v.v.

Ví dụ

Quan hệ hai ngôi là một trong những loại quan hệ điển hình và hay gặp nhất. Loại quan hệ này cũng có một số tính chất thú vị mà ta sẽ mô tả ở đây.

Ví dụ về quan hệ hai ngôi: quan hệ “bố — con trai”, cặp “phương tiện giao thông — số bánh xe”, hay tổng quát hơn “đối tượng — tính chất của đối tượng”. Đối tượng có thể là một con vật, còn tính chất có thể là số chân, tuổi thọ trung bình, số sợi lông trên đầu, v.v.

Quan hệ hai ngôi R giữa hai tập hợp M₁ và M₂ có thể định nghĩa như sau: R ⊆ M₁ × M₂. Như vậy quan hệ hai ngôi là một tập hợp các cặp, và tập hợp này là tập con của tích Descartes của hai tập hợp mà ta xét quan hệ giữa chúng. Chẳng hạn quan hệ “bố — con trai” có thể là quan hệ giữa tập hợp tất cả mọi người, giữa tập hợp tất cả những người ở châu Âu hay ở Hà Nội. Ta cũng có thể thu hẹp tập hợp theo hướng khác, chẳng hạn định nghĩa quan hệ giữa tập hợp tất cả nam giới chứ không phải mọi người nói chung.

Với quan hệ hai ngôi, ta thường dùng một cách viết riêng. Thay vì viết (a; b) ∈ R, ta có thể viết aRb. Chẳng hạn thay cho (3; 1) ∈ > có thể viết 3 > 1. Với các quan hệ khác cũng tương tự. Như vậy cách viết aSb tương đương với cách viết (a; b) ∈ S.

Quan hệ ngược

Quan hệ ngược là quan hệ theo chiều ngược lại của quan hệ đã cho. (Chú ý, đừng nhầm với quan hệ bù.) Quan hệ ngược của quan hệ nhỏ hơn là gì? Là quan hệ lớn hơn. Nếu quan hệ nhỏ hơn chứa phần tử (4; 7), tức là 4 < 7, thì phần tử ngược sẽ theo chiều ngược lại: 7 > 4, và quan hệ ngược chứa cặp ngược (7; 4).

Cho quan hệ R ⊆ M₁ × M₂. Để xây dựng quan hệ ngược R⁻¹, ta lấy tất cả các phần tử (a; b) ∈ R và đưa vào R⁻¹ các cặp ngược của chúng. Tức là nếu quan hệ R chứa phần tử (a; b) thì quan hệ R⁻¹ phải chứa phần tử (b; a). Điều ngược lại cũng đúng: nếu R⁻¹ chứa phần tử (b; a) thì quan hệ R phải chứa phần tử (a; b).

Viết thành định nghĩa: quan hệ R⁻¹ là quan hệ ngược của R khi và chỉ khi:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a;b)\in R\iff (b;a)\in R^{-1}$$

Chẳng hạn 6 < 8 khi và chỉ khi 8 > 6. Với các cặp khác cũng tương tự.

Hợp thành của các quan hệ

Ta có thể lấy hợp thành của các quan hệ hai ngôi. Cho hai quan hệ: quan hệ thứ nhất R là “là bố của con trai mình”, quan hệ thứ hai S là “là anh trai của em gái mình”. Quan hệ R gồm các cặp (bố; con trai), quan hệ thứ hai gồm các cặp (anh trai; em gái).

Bây giờ ta thử lấy hợp thành của hai quan hệ. Ta được một quan hệ mới, kí hiệu là R ∘ S, chứa phần tử (a; c) khi và chỉ khi (a; b) ∈ R và (b; c) ∈ S. Để ý rằng b có mặt trong cả hai phần tử, một lần ở vị trí thứ hai và một lần ở vị trí thứ nhất của cặp. Đó là phần tử nối của phép hợp thành.

Ví dụ: R = {(Quang; Minh); (Trung; Long)} và S = {(Minh; Lan); (Minh; Linh); (Long; Mai)}. Quang là bố của Minh, Trung là bố của Long. Minh có hai em gái là Lan và Linh, còn Long có em gái Mai.

Bây giờ ta lấy hợp thành R ∘ S. Ta tìm trong R những cặp mà ở vị trí con trai là một người có mặt ở vị trí anh trai trong quan hệ S. Chẳng hạn hai cặp: (Quang; Minh) và (Minh; Lan). Minh là phần tử nối, ta không cần đến nữa, và từ hai tên còn lại ta lập cặp mới: (Quang; Lan). Như vậy quan hệ R ∘ S chứa cặp (Quang; Lan). Minh còn một em gái nữa là Linh, ta cũng thêm vào quan hệ hợp thành: (Quang; Linh). Cuối cùng còn con trai Long, có em gái Mai. Ta có hai cặp: (Trung; Long) và (Long; Mai), từ đó được thêm một phần tử: (Trung; Mai).

Kết quả là quan hệ: R ∘ S = {(Quang; Lan); (Quang; Linh); (Trung; Mai)}. Có thể đặt tên quan hệ này là gì? Có lẽ là “là bố của con gái mình”.

Viết lại toàn bộ định nghĩa:

$$(a;c)\in (R\circ S)\iff \mathrm{\exists }b(a;b)\in R\wedge (b;c)\in S$$

Chú ý: đôi khi người ta dùng cách viết ngược lại, tức là với cùng định nghĩa này lại viết S ∘ R thay cho R ∘ S.