Mối quan hệ tương đương

Trong toán học, mối quan hệ tương đương là một loại quan hệ hai ngôi có tính chất phản xạ, đối xứng và bắc cầu.

Mỗi quan hệ đối xứng phân chia tập hợp thành các lớp tương đương không giao nhau. Hai phần tử được coi là tương đương nếu và chỉ nếu chúng thuộc cùng một lớp tương đương.

Ký hiệu

Ký hiệu '$a\sim <!--\; \sim \; -->b$' và 'a ≡ b', thường được sử dụng khi không đề cập đến quan hệ $R$. Trong khi đó, dạng '$a{\sim <!--\; \sim \; -->}_{R}b$', 'a ≡_R b', hay '$aR<!--\; \; -->b$' được dùng khi cần chỉ rõ quan hệ $R$. Khi muốn diễn tả không tương đương, ta có thể viết 'a ≁ b' hoặc '$a\not\equiv b$'.

Khái niệm

Một quan hệ hai ngôi $\sim <!--\; \sim \; -->$ trên tập $X$ được gọi là mối quan hệ tương đương khi và chỉ khi nó có tính phản xạ, đối xứng và bắc cầu. Điều này có nghĩa là, với mọi $a,b,$ và $c$ thuộc $X:$

• $a\sim <!--\; \sim \; -->a$ (phản xạ).
• $a\sim <!--\; \sim \; -->b$ khi và chỉ khi $b\sim <!--\; \sim \; -->a$ (đối xứng).
• Nếu $a\sim <!--\; \sim \; -->b$ và $b\sim <!--\; \sim \; -->c$ thì $a\sim <!--\; \sim \; -->c$ (bắc cầu).

$X$ cùng với mối quan hệ tương đương $\sim <!--\; \sim \; -->$ được gọi là một setoid. Lớp tương đương của $a$ dưới $\sim <!--\; \sim \; -->,$ được ký hiệu là $\left[a\right],$ và được định nghĩa bởi $\left[a\right]=\{x\in <!--\; \in \; -->X:x\sim <!--\; \sim \; -->a\}.$

Định nghĩa trong đại số các quan hệ

Giả sử $R\subseteq <!--\; \subseteq \; -->X\times <!--\; \times \; -->Y$ và $S\subseteq <!--\; \subseteq \; -->Y\times <!--\; \times \; -->Z$ là hai quan hệ, thì hợp thành của quan hệ $SR\subseteq <!--\; \subseteq \; -->X\times <!--\; \times \; -->Z$ được xác định khi $xSRz$ nếu và chỉ nếu tồn tại $y\in <!--\; \in \; -->Y$ sao cho $xRy$ và $ySz$. Đây là định nghĩa tổng quát của phép hợp hàm. Từ đây, chúng ta có định nghĩa tương đương của quan hệ tương đương $R$ trên tập $X$ như sau:

• $\mathrm{id}\subseteq <!--\; \subseteq \; -->R$ (phản xạ). (Ở đây, $\mathrm{id}$ là ký hiệu của hàm đồng nhất trên $X$.)
• $R=R^{-<!--\; -\; -->1}$ (đối xứng).
• $RR\subseteq <!--\; \subseteq \; -->R$ (bắc cầu).

Ví dụ minh họa

Ví dụ đơn giản

Trên tập $X=\{a,b,c\}$, quan hệ $R=\left\{\right(a,a),(b,b),(c,c),(b,c),(c,b\left)\right\}$ là quan hệ tương đương. Các lớp tương đương của quan hệ này là: $\left[a\right]=\left\{a\right\},\left[b\right]=\left[c\right]=\{b,c\}.$

Các lớp tương đương của quan hệ $R$ là $\left\{\right\{a\},\{b,c\left\}\right\}.$ Đây là phân hoạch của tập $X$ theo quan hệ $R$.

Ví dụ về các quan hệ tương đương khác

Các quan hệ sau đây là các ví dụ về quan hệ tương đương:

• 'Bằng nhau' trên tập số. Ví dụ như $\frac{1}{2}$ tương đương với $\frac{4}{8}.$
• 'Có cùng ngày sinh' trên tập con người.
• 'Đồng dạng' trên tập tất cả các tam giác.
• 'Tương đẳng' trên tập tất cả các tam giác.
• Cho số nguyên
  $n$, 'Đồng dư với $n$' trên tập số nguyên.
• 'Có cùng giá trị tuyệt đối' trên tập số thực.
• 'Có cùng giá trị cos' trên tập các góc.

Ví dụ về các quan hệ không phải là tương đương

• Quan hệ '≥' trong tập số thực là bắc cầu và phản xạ nhưng không đối xứng. Ví dụ: 7 ≥ 5 nhưng không phải 5 ≥ 7.
• Quan hệ 'có cùng ước số lớn hơn 1 với' giữa các số tự nhiên lớn hơn 1 là phản xạ và đối xứng nhưng không bắc cầu. Ví dụ: 5 và 10 có ước chung lớn hơn 1, 10 và 4 cũng có ước chung lớn hơn 1 nhưng 5 và 4 không có ước chung lớn hơn 1.
• Quan hệ rỗng R (nghĩa là aRb luôn sai) trên tập X thì tự động là đối xứng và bắc cầu nhưng không phản xạ (trừ khi X là tập rỗng).

Liên hệ với các loại quan hệ khác

• Quan hệ thứ tự bộ phận là quan hệ phản xạ, phản xứng, và bắc cầu.
• Đẳng thức vừa là quan hệ tương đương vừa là quan hệ thứ tự bộ phận. Đẳng thức cũng là quan hệ duy nhất trên tập mà có tính phản xạ, phản xứng và đối xứng. Trong đại số, các biến bằng nhau có thể thay cho nhau, trong khi các biến có quan hệ tương đương thì không thể thay thế nhau. Các lớp tương đương có thể thay cho nhau, nhưng các phần tử trong lớp thì không.
• Quan hệ thứ tự bộ phận chặt chẽ là phản xạ, bắc cầu nhưng không đối xứng.
• Quan hệ tương đương một phần là bắc cầu và đối xứng. Quan hệ có tính phản xạ khi và chỉ khi nó là quan hệ toàn phần, tức là, với mọi $a,$, tồn tại $b\text{ sao cho }a\sim <!--\; \sim \; -->b.$. Do đó, quan hệ tương đương có thể định nghĩa là quan hệ đối xứng, bắc cầu và toàn phần.
• Quan hệ tương đương tam ngôi là quan hệ tương đương trong ba ngôi tương tự như quan hệ hai ngôi.
• Quan hệ phản xạ và đối xứng là quan hệ phụ thuộc (nếu hữu hạn) và là quan hệ dung sai nếu vô hạn.
• Tiền thứ tự có tính phản xạ và bắc cầu.
• Quan hệ tương đẳng là quan hệ tương đương mà tập $X$ làm tập nền cho cấu trúc đại số, và mở rộng một số cấu trúc. Thường thì, quan hệ tương đẳng đóng vai trò là hạt nhân của các đồng cấu, và thương của cấu trúc qua quan hệ tương đẳng có thể được xác định. Trong nhiều trường hợp quan trọng, quan hệ tương đẳng còn được coi là các cấu trúc con của cấu trúc mà chúng được định nghĩa trên (chẳng hạn như quan hệ tương đẳng trên các nhóm tương ứng với các nhóm con chuẩn tắc).
• Các quan hệ vừa phản xạ vừa là quan hệ Euclid (trái hoặc phải) cũng là quan hệ tương đương.

Xác định hoàn toàn dưới quan hệ tương đương

Nếu $\sim <!--\; \sim \; -->$ là quan hệ tương đương trên $X,$ và $P\left(x\right)$ là thuộc tính của các phần tử trong $X,$ sao cho nếu $x\sim <!--\; \sim \; -->y,$ thì $P\left(x\right)$ đúng khi và chỉ khi $P\left(y\right)$ cũng đúng, thì thuộc tính $P$ được gọi là xác định hoàn toàn hay bất biến lớp theo quan hệ $\sim <!--\; \sim \; -->.$

Một ví dụ cụ thể là khi $f$ là một hàm từ tập $X$ sang tập $Y;$ sao cho nếu $x_1\sim <!--\; \sim \; -->x_2$ thì $f\left(x_1\right)=f\left(x_2\right)$ thì hàm $f$ được gọi là cấu xạ đối với $\sim <!--\; \sim \; -->,$ hay bất biến lớp dưới $\sim <!--\; \sim \; -->,$ hoặc ngắn gọn là bất biến dưới $\sim <!--\; \sim \; -->.$. Trường hợp này thường xuất hiện trong lý thuyết nhóm hữu hạn.

Một hàm có thể ánh xạ các phần tử tương đương trong một quan hệ tương đương ${\sim <!--\; \sim \; -->}_A$ thành các phần tử tương đương trong một quan hệ tương đương khác ${\sim <!--\; \sim \; -->}_B$. Hàm như vậy được gọi là cấu xạ từ ${\sim <!--\; \sim \; -->}_A$ sang ${\sim <!--\; \sim \; -->}_B.$

Lớp tương đương, tập thương và phân hoạch

Giả sử $a,b\in <!--\; \in \; -->X.$, ta có thể đưa ra một số định nghĩa sau:

Lớp tương đương

Tập con Y của X sao cho với mọi phần tử a và b trong Y, điều kiện $a\sim <!--\; \sim \; -->b$ luôn được thỏa mãn, và điều này không xảy ra nếu a thuộc Y còn b nằm ngoài Y, thì gọi là lớp tương đương của X theo quan hệ ~. Ký hiệu lớp tương đương cho phần tử a là $\left[a\right]:=\{x\in <!--\; \in \; -->X:a\sim <!--\; \sim \; -->x\}$. Tất cả các phần tử trong X tương đương với nhau đều thuộc cùng một lớp tương đương.

Tập thương

Tập hợp tất cả các lớp tương đương của X theo quan hệ ~, ký hiệu là $X/\sim <!--\; \sim \; -->:=\left\{\right[x]:x\in <!--\; \in \; -->X\},$ là tập thương của X theo ~. Nếu X là không gian tô pô, thì có thể chuyển đổi $X/\sim <!--\; \sim \; -->$ thành một không gian tô pô; tham khảo không gian thương để biết thêm chi tiết.

Phép chiếu

Phép chiếu của $\sim <!--\; \sim \; -->$ là một hàm $\mathrm{\pi <!--\; \pi \; -->}:X\to <!--\; \to \; -->X/\sim <!--\; \sim \; -->$ được định nghĩa bởi $\mathrm{\pi <!--\; \pi \; -->}\left(x\right)=\left[x\right]$, ánh xạ các phần tử của $X$ tới lớp tương đương tương ứng của chúng theo $\sim <!--\; \sim \; -->.$

Định lý về các phép chiếu: Cho hàm $f:X\to <!--\; \to \; -->B$ sao cho nếu $a\sim <!--\; \sim \; -->b$ thì $f\left(a\right)=f\left(b\right).$ thì tồn tại một hàm duy nhất $g:X/\sim <!--\; \sim \; -->\to <!--\; \to \; -->B$ sao cho $f=g\mathrm{\pi <!--\; \pi \; -->}.$. Nếu $f$ là toàn ánh và $a\sim <!--\; \sim \; -->b\text{ khi và chỉ khi }f\left(a\right)=f\left(b\right),$ thì $g$ là một phép đồng nhất.

Hạt nhân tương đương

Hạt nhân tương đương của hàm $f$ là quan hệ tương đương ~ được định nghĩa như sau: $x\sim <!--\; \sim \; -->y\text{ khi và chỉ khi }f\left(x\right)=f\left(y\right).$. Hạt nhân tương đương của một hàm đơn ánh chính là quan hệ đồng nhất.

Phân hoạch

Phân hoạch của X là một tập P gồm các tập con của X, sao cho mỗi phần tử của X thuộc duy nhất một tập con trong P. Vì vậy, các tập con trong P không có phần tử chung và hợp của tất cả các tập con trong P là X.

Xét X là một tập hữu hạn với n phần tử. Mỗi quan hệ tương đương trên X tương ứng với một phân hoạch của X, và ngược lại, số lượng quan hệ tương đương trên X chính là số lượng phân hoạch khác nhau của X, được ký hiệu là số Bell thứ n, hoặc Bn:

(Công thức Dobinski).

Định lý cơ bản về các quan hệ tương đương

Có hai mối liên hệ quan trọng giữa quan hệ tương đương và phân hoạch trong một tập hợp:

• Quan hệ tương đương ~ trên tập X sẽ tạo ra một phân hoạch cho X.
• Ngược lại, mỗi phân hoạch trên X tương ứng với một quan hệ tương đương ~ trên X.

Trong cả hai trường hợp, các tập con trong phân hoạch của X được gọi là lớp tương đương của X theo quan hệ ~. Vì vậy, giữa tập hợp các quan hệ tương đương trên X và tập hợp các phân hoạch của X tồn tại một sự tương ứng song ánh.

So sánh các quan hệ tương đương

Nếu $\sim <!--\; \sim \; -->$ và $\approx <!--\; \approx \; -->$ là hai quan hệ tương đương trên cùng một tập $S$, và nếu $a\sim <!--\; \sim \; -->b$ dẫn đến $a\approx <!--\; \approx \; -->b$ với mọi $a,b\in <!--\; \in \; -->S,$, thì quan hệ $\approx <!--\; \approx \; -->$ được gọi là thô hơn quan hệ $\sim <!--\; \sim \; -->$, trong khi quan hệ $\sim <!--\; \sim \; -->$ được coi là mịn hơn quan hệ $\approx <!--\; \approx \; -->$. Các cách diễn đạt tương đương:

• $\sim <!--\; \sim \; -->$ được coi là mịn hơn $\approx <!--\; \approx \; -->$ nếu tất cả các lớp tương đương của $\sim <!--\; \sim \; -->$ đều là tập con của lớp tương đương của $\approx <!--\; \approx \; -->$, và ngược lại, mỗi lớp tương đương của $\approx <!--\; \approx \; -->$ là hợp của các lớp tương đương của $\sim <!--\; \sim \; -->$.
• $\sim <!--\; \sim \; -->$ được coi là mịn hơn $\approx <!--\; \approx \; -->$ nếu phân hoạch của $\sim <!--\; \sim \; -->$ chính là kết quả của việc mịn hóa phân hoạch của $\approx <!--\; \approx \; -->$.

Quan hệ bằng nhau là quan hệ mịn nhất có thể trên bất kỳ tập hợp nào. Ngược lại, quan hệ phổ dụng (trong đó mọi cặp phần tử đều có quan hệ với nhau) là quan hệ thô nhất.

Khi xét quan hệ '$\sim <!--\; \sim \; -->$ mịn hơn $\approx <!--\; \approx \; -->$' trên tập các quan hệ tương đương trên cùng một tập, đây là một quan hệ thứ tự một phần và vì vậy, tập hợp này chính là ví dụ của dàn hình học.

Xây dựng quan hệ tương đương

• Cho bất kỳ $X,$ quan hệ tương đương $[X\to <!--\; \to \; -->X]$ của các hàm $X\to <!--\; \to \; -->X$ có thể được xây dựng như sau: Hai hàm được coi là tương đương nếu số lượng điểm cố định của chúng là như nhau, tương ứng với số xích độ dài một trong hoán vị.
• Quan hệ tương đương $\sim <!--\; \sim \; -->$ trên $X$ chính là hạt nhân tương đương của phép chiếu toàn ánh $\mathrm{\pi <!--\; \pi \; -->}:X\to <!--\; \to \; -->X/\sim <!--\; \sim \; -->.$. Ngược lại, mỗi toàn ánh xác định một phân hoạch trên miền của nó, cụ thể là các tiền ảnh của các điểm đơn trên miền giá trị. Vì vậy, phép chiếu với miền là tập $X,$ có thể được sử dụng để mô tả quan hệ tương đương hoặc phân hoạch trên tập $X,$.
• Giao của bất kỳ tập hợp các quan hệ tương đương trên X (được coi là các quan hệ trong $X\times <!--\; \times \; -->X$) cũng là quan hệ tương đương. Do đó, một cách xây dựng quan hệ tương đương là: cho bất kỳ quan hệ hai ngôi R trên X, quan hệ tương đương sinh bởi R chính là giao của tất cả các quan hệ tương đương chứa R (hay còn gọi là quan hệ tương đương nhỏ nhất chứa R). Cụ thể hơn, R sinh ra quan hệ tương đương.

$a\sim <!--\; \sim \; -->b$ nếu tồn tại một số nguyên dương $n$ và các phần tử $x_0,\dots <!--\; \dots \; -->,x_n\in <!--\; \in \; -->X$ sao cho $a=x_0$, $b=x_n$, và $x_{i-<!--\; -\; -->1}R{x}_i$ hoặc $x_{i}R{x}_{i-<!--\; -\; -->1}$, với $i=1,\dots <!--\; \dots \; -->,n.$

Đôi khi, quan hệ tương đương tạo ra theo cách này có thể rất đơn giản. Ví dụ, quan hệ tương đương sinh ra từ bất kỳ thứ tự toàn phần trên tập X chỉ có một lớp tương đương duy nhất là chính tập X.

• Quan hệ tương đương có thể tạo ra các không gian mới bằng cách 'dính chúng lại với nhau.' Xét X là hình chữ nhật $[0,1]\times <!--\; \times \; -->[0,1],$ và ~ là quan hệ tương đương trên X được định nghĩa bởi $(a,0)\sim <!--\; \sim \; -->(a,1)$ với mọi $a\in <!--\; \in \; -->[0,1]$ và $(0,b)\sim <!--\; \sim \; -->(1,b)$ với mọi $b\in <!--\; \in \; -->[0,1]$. Không gian thương $X/\sim <!--\; \sim \; -->$ sẽ đồng phôi với hình xuyến: gấp một tờ giấy thành hình chữ nhật, uốn cong và dính hai cạnh đối diện để tạo thành hình trụ, sau đó dính hai mặt tròn của hình trụ lại để tạo thành hình xuyến.

Cấu trúc đại số

Nhiều lĩnh vực trong toán học tập trung vào tính tương đương và tính thứ tự, trong đó lý thuyết dàn được sử dụng để nghiên cứu các quan hệ thứ tự. Mặc dù các quan hệ tương đương rất phổ biến trong toán học, cấu trúc đại số của chúng ít được nghiên cứu hơn so với các quan hệ thứ tự. Cấu trúc của quan hệ tương đương thường được dựa trên lý thuyết nhóm, đôi khi kết hợp với lý thuyết dàn, phạm trù và các groupoid.

Lý thuyết nhóm

Tương tự như cách mà các quan hệ thứ tự được nghiên cứu trong các tập hợp sắp thứ tự và các tập đóng dưới phép supremum và infimum, các quan hệ tương đương cũng được phân tích trong các tập đã được phân hoạch. Tức là, chúng nằm trong các tập hợp được đóng dưới các phép ánh xạ bảo toàn cấu trúc phân hoạch. Do mọi phép ánh xạ đó đều ánh xạ lớp tương đương về chính nó, chúng cũng được gọi là hoán vị hay phép thế trong lý thuyết nhóm. Nhóm các hoán vị (hay còn gọi là nhóm biến đổi) và khái niệm quỹ đạo giúp phân tích cấu trúc toán học của các quan hệ tương đương.

Xét ~ là một quan hệ tương đương trên một tập không rỗng A, mà A được gọi là tập nền. Gọi G là tập hợp các phép ánh xạ trên A bảo toàn cấu trúc phân hoạch của A, nghĩa là với mọi $x\in <!--\; \in \; -->A$ và $g\in <!--\; \in \; -->G,g\left(x\right)\in <!--\; \in \; -->\left[x\right].$, thì ba định lý liên quan sau đây được áp dụng:

• ~ phân hoạch A thành các lớp tương đương. (Đây là Định lý nền tảng của các quan hệ tương đương, đã được đề cập trước đó);
• Với một phân hoạch của A, tập G là một nhóm biến đổi dưới phép hợp, với các quỹ đạo tương ứng là các lớp của phân hoạch đó;

• Đối với nhóm biến đổi G trên A, tồn tại một quan hệ tương đương ~ trên A sao cho các lớp tương đương của nó tương ứng với các quỹ đạo của G.

Tóm lại, với một quan hệ tương đương ~ trên A, có thể tìm một nhóm biến đổi G trên A mà các quỹ đạo của nó chính là các lớp tương đương của A theo ~.

Nhóm biến đổi có sự khác biệt cơ bản so với cách mô tả quan hệ thứ tự trong lý thuyết dàn. Tham số của phép nối và phép gặp trong lý thuyết dàn là các phần tử thuộc tập nền A. Trong khi đó, tham số của phép hợp và phép nghịch đảo trong nhóm biến đổi là các phần tử của tập các phép ánh xạ A → A.

Xét một nhóm H là nhóm con của G. Nếu ~ là một quan hệ tương đương trên G sao cho $a\sim <!--\; \sim \; -->b\text{ khi và chỉ khi }a{b}^{-<!--\; -\; -->1}\in <!--\; \in \; -->H.$, thì các lớp tương đương ~ của H trên G được gọi là các lớp kề bên phải của H trong G. Thay đổi a và b sẽ tạo ra các lớp kề bên trái.

Nội dung chi tiết có thể tham khảo thêm trong Rosen (2008: chương 10).

Lý thuyết phạm trù và các groupoid

Liên kết ngoài

• Hazewinkel, Michiel (biên tập) (2001), “Quan hệ tương đương”, Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4
• Bogomolny, A., 'Quan hệ Tương đương' cut-the-knot. Truy cập ngày 1 tháng 9 năm 2009
• Quan hệ tương đương tại PlanetMath
• Bản mẫuel