Quan hệ tương đương

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

Vì sao cần quan hệ tương đương

Quan hệ tương đương là một dạng “nới lỏng” của quan hệ bằng. Ta luôn xác định được hai phần tử của một tập hợp có bằng nhau hay không, tức là có a = b hay không. Nhưng đôi khi ta muốn biết hai phần tử có giống nhau hay không, chứ không nhất thiết bằng nhau. Nói cách khác, hai phần tử có chung một tính chất quan trọng nào đó hay không. Chẳng hạn có thể coi hai cuốn sách là giống nhau nếu chúng cùng thể loại — hay nói bằng ngôn ngữ tương đương: hai cuốn sách tương đương nếu chúng cùng thể loại.

Ta mong đợi gì ở một quan hệ tương đương như vậy? Lấy một ví dụ khác: hai từ là giống nhau/tương đương nếu chúng có cùng độ dài.

Hẳn ta mong rằng khi so sánh một từ với chính nó thì kết quả là chúng giống nhau. Tức là mọi từ đều phải giống/tương đương với chính nó. Nói theo ngôn ngữ quan hệ: quan hệ tương đương phải có tính phản xạ.

Tiếp theo, nếu từ “sông” giống/tương đương với từ “biển” thì chắc chắn ta mong từ “biển” cũng tương đương với từ “sông”. Nói cách khác, thứ tự không quan trọng. Nói theo ngôn ngữ quan hệ: quan hệ tương đương phải có tính đối xứng.

Cuối cùng, nếu từ “hoa” giống/tương đương với từ “cây” và từ “cây” tương đương với từ “núi” thì ta mong rằng cặp từ “hoa” và “núi” cũng tương đương. Như vậy quan hệ tương đương còn phải có tính bắc cầu.

Ngoài ra ta không đòi hỏi gì thêm ở quan hệ tương đương.

Ví dụ

Thêm một số ví dụ về quan hệ tương đương:

• Sống cùng một thành phố. Minh chắc chắn sống cùng thành phố với Minh (phản xạ). Nếu Minh sống cùng thành phố với Hùng thì Hùng cũng sống cùng thành phố với Minh (đối xứng). Và nếu Hùng sống cùng thành phố với Tuấn thì Minh cũng sống cùng thành phố với Tuấn (bắc cầu).
• Các bài hát có cùng tác giả. Bài hát X chắc chắn có cùng tác giả với bài hát X (phản xạ). Nếu hai bài hát X và Y có cùng tác giả thì Y và X cũng có cùng tác giả (đối xứng). Và nếu Y và Z có cùng tác giả thì X và Z cũng có cùng tác giả (bắc cầu).
• (a; b) ∈ R khi và chỉ khi a − b là số chẵn, với a, b là các số nguyên. Phản xạ: a − a = 0, mà 0 là số chẵn. Đối xứng: đặt c = a − b. Khi đó b − a = −(a − b) = −c. Nếu c chẵn thì −c cũng phải chẵn. Bắc cầu: đặt p = a − b và q = b − c. Ta biết p và q đều là số chẵn. Cần chứng minh a − c là số chẵn. Thay c = b − q vào biểu thức này: a − (b − q), bằng a − b + q. Theo giả thiết, a − b là số chẵn. Cộng một số chẵn với một số chẵn q nữa, ta lại được số chẵn.
• Quan hệ bằng. Quan hệ bằng là một quan hệ tương đương, đồng thời là quan hệ tương đương nhỏ nhất trên một tập hợp M bất kì.

Quan hệ tương đương tầm thường

Cho tập hợp khác rỗng M. Quan hệ tương đương nhỏ nhất có thể R trên tập hợp M là gì? Tập con nhỏ nhất có thể của tích Descartes M × M là tập rỗng ∅. Tập rỗng có thoả mãn các điều kiện của quan hệ tương đương không?

Chắc chắn tập rỗng có tính đối xứng: vì quan hệ R không có phần tử nào nên điều kiện đối xứng hiển nhiên được thoả mãn. Tính bắc cầu cũng vậy. Vấn đề nằm ở tính phản xạ. Định nghĩa nói rằng với mọi phần tử x của tập hợp M ta có (x; x) ∈ R. Điều này có thoả mãn không? Tập hợp M khác rỗng nên chứa một phần tử nào đó, chẳng hạn q. Cặp (q; q) có thuộc quan hệ R không? Không. Vì vậy quan hệ R không có tính phản xạ.

Quan hệ nhỏ nhất có tính phản xạ là gì? Đó là quan hệ bằng. Quan hệ R phải chứa ít nhất các cặp (x; x) với mọi phần tử của M, và đó chính là quan hệ đồng nhất. Quan hệ này có đối xứng không? Dễ thấy là có. Cũng dễ thấy nó có tính bắc cầu. Vậy quan hệ tương đương nhỏ nhất trên tập hợp M là quan hệ đồng nhất, kí hiệu là id_M, gồm các cặp (x; x) với mọi x ∈ M.

Quan hệ tương đương lớn nhất có thể trên tập hợp M là gì? Tập con lớn nhất là toàn bộ tập hợp M × M. Nó có thoả mãn các điều kiện của quan hệ tương đương không? Có lẽ hiển nhiên là có.

Lớp tương đương

Mỗi quan hệ tương đương chia tập hợp M thành một họ các tập hợp rời nhau, gọi là các lớp tương đương.

Cho M là tập hợp tất cả các từ và R là quan hệ tương đương “từ có cùng độ dài”, tức là (a; b) ∈ R khi và chỉ khi hai từ a và b có cùng độ dài. Quan hệ tương đương này chia tập hợp các từ thành một số tập hợp nhỏ hơn, mỗi tập chỉ chứa những từ có cùng độ dài. Ta có thể phân biệt các lớp tương đương bằng chỉ số dưới, đồng thời chỉ số này cho biết độ dài của các từ trong tập hợp đó:

• M₁ = {à; ồ; ừ; ở; …}
• M₂ = {ba; cá; đi; về; mẹ; …}
• M₃ = {cây; hoa; núi; mưa; …}
• M₄ = {sông; biển; trời; xanh; …}
• …

Để ý hai điều: 1) các tập hợp này đôi một rời nhau, không có phần tử chung. 2) mọi phần tử trong mỗi tập hợp đều tương đương với nhau. Mọi từ trong tập hợp M₃ đều tương đương với nhau, vì chúng đều có độ dài 3, tức là cùng độ dài, đúng như điều kiện của quan hệ tương đương.

Hơn nữa, mỗi phần tử xác định duy nhất lớp tương đương của nó. Điều này thường được viết bằng kí hiệu M[x], với x ∈ M. Nếu viết M[cây] thì ta xác định duy nhất lớp tương đương mà ta đã kí hiệu là M₃.

Vậy khi biết một phần tử x ∈ M, làm thế nào tìm lớp tương đương của nó? Ta duyệt qua mọi phần tử của M và xem những phần tử nào tương đương với x. Đó chính là tất cả các phần tử thuộc lớp tương đương M[x].

Với M[cây], ta duyệt qua mọi từ trong M và giữ lại trong M₃ những từ có độ dài 3.

Định nghĩa và tính chất của lớp tương đương

Ta có thể định nghĩa lớp tương đương như sau. Cho tập hợp M và quan hệ tương đương R trên đó. Lớp tương đương chứa phần tử x ∈ M là:

$$M[x]=\{y\in M\mid (x;y)\in R\}$$

Định nghĩa nói rằng đó là tất cả các phần tử y tương đương với phần tử x đã cho. Vì quan hệ tương đương có tính phản xạ nên bản thân phần tử x cũng thuộc lớp này — vì x tương đương với chính nó.

Phân hoạch ứng với quan hệ tương đương là tập hợp tất cả các lớp tương đương. Như vậy phân hoạch của tập hợp tất cả các từ là tập hợp {M₁; M₂; M₃; …}.

Các tính chất cơ bản của lớp tương đương:

• (a; b) ∈ R khi và chỉ khi M[a] = M[b]. Nếu hai phần tử a, b tương đương thì các lớp tương đương của chúng phải bằng nhau.
• Ngược lại, nếu không có (a; b) ∈ R thì M[a] ≠ M[b], chính xác hơn là M[a] ∩ M[b] = ∅. Nếu hai phần tử không tương đương thì các lớp tương đương của chúng rời nhau.
• Hợp của tất cả các lớp tương đương phải bằng tập hợp ban đầu M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Cách viết trên chỉ dành cho trường hợp có hữu hạn lớp tương đương, nhưng nói chung có thể có vô hạn lớp.)

Ví dụ về phân hoạch theo quan hệ tương đương

Ví dụ thứ nhất, số lẻ và số chẵn:

Xét một quan hệ tương đương đơn giản R trên tập số nguyên dương N: (a; b) ∈ R khi và chỉ khi a và b cùng lẻ hoặc a và b cùng chẵn. Ví dụ về các phần tử: (1; 7), (13; 9), (4; 6), (8; 136). Ta tìm phân hoạch ứng với quan hệ tương đương này, tức là các lớp tương đương.

Ta làm lần lượt. Lớp N[1] bằng gì? Cần tìm tất cả các số tương đương với số 1. Theo điều kiện của quan hệ tương đương, đó là tất cả các số lẻ, nên N[1] = {1; 3; 5; 7; 9; …}.

Lớp N[2] bằng gì? Ta tìm tất cả các số tương đương với số 2. Đó là tất cả các số chẵn: N[2] = {2; 4; 6; 8; 10; …}.

Tiếp theo là N[3]. Những số nào tương đương với số 3? Tất cả các số lẻ. Nhưng như vậy ta lại được tập hợp N[1] đã tìm ở trên. Với N[4] cũng vậy, ta lại được tập hợp các số chẵn.

Ta thấy từ đây trở đi chỉ lặp lại hai tập hợp này. Điều đó cũng thấy được từ chỗ: lấy bất kì số nguyên dương n nào thì cũng có n ∈ N[1] hoặc n ∈ N[2]. Ngoài số lẻ và số chẵn không còn số nguyên dương nào khác, nên hai tập hợp này tạo thành phân hoạch ứng với quan hệ tương đương.

Điều này giống như khi xét quan hệ tương đương trên tập hợp mọi người: a và b cùng là nam hoặc a và b cùng là nữ. Khi đó phân hoạch gồm tập hợp những người nữ và tập hợp những người nam.

Ví dụ thứ hai, giá trị tuyệt đối:

Xét quan hệ tương đương R trên tập số nguyên Z định nghĩa như sau: (a; b) ∈ R khi và chỉ khi |a| = |b|. (Hai vạch thẳng đứng là kí hiệu giá trị tuyệt đối.) Ta lại làm lần lượt:

• Z[0] = {0}. Số 0 chỉ có quan hệ với số 0.
• Z[1] = {−1; 1}. Số 1 có quan hệ với số 1 và số −1, vì |1| = |−1|.
• Z[2] = {−2; 2}. Số 2 có quan hệ với số 2 và số −2.
• Z[3] = {−3; 3}.
• …

Có lẽ đã rõ quy luật tiếp theo. Toàn bộ phân hoạch là tập hợp các lớp:

$$\{\{a;-a\}\mid a\in {\mathbb{Z}}_0^{+}\}$$

(Tức là tất cả các cặp a, −a, trong đó a là số nguyên không âm.) Như vậy có vô hạn lớp tương đương.