Quan hệ tương đương

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

52 quan hệ tương đương trên tập 5 phần tử được biểu diễn dưới ma trận logic $5\times 5$ (các ô được tô màu biểu diễn số 1, tức là có quan hệ với nhau, ; trường màu trắng là số 0, tức là không quan hệ với nhau.)

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

Ký hiệu

Ký hiệu "$a\sim b$" và "a ≡ b", thường được dùng khi ta không nhắc đến quan hệ $R$ , còn dạng "$a\sim _{R}b$", "a ≡_R b", hay "${a\mathop {R} b}$" khi ta muốn nhắc đến $R$. Khi muốn nói không tương đương ta có thể viết "a ≁ b" hoặc "$a\not \equiv b$".

Định nghĩa

Quan hệ hai ngôi $\,\sim \,$ trên tập $X$ được gọi là quan hệ tương đương khi và chỉ khi nó phản xạ, đối xứng và bắc cầu. Nghĩa là, với mọi $a,b,$ và $c$ thuộc $X:$

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

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

Định nghĩa dùng đại số của các quan hệ

Nếu $R\subseteq X\times Y$ và $S\subseteq Y\times Z$ là 2 hai quan hệ, thì quan hệ hợp $SR\subseteq X\times Z$ được định nghĩa là $x\,SR\,z$ khi chỉ khi tồn tại $y\in Y$ sao cho $x\,R\,y$ và $y\,S\,z$. Định nghĩa này tổng quát định nghĩa của phép hợp hàm. Từ đó, ta có định nghĩa khác tương đương của quan hệ tương đương $R$ trên tập $X$ như sau::

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

Các ví dụ

Ví dụ đơn giản

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

Tập các lớp tương đương cho $R$ là $\{\{a\},\{b,c\}\}.$ Tập này là phân hoạch của tập $X$ với $R$.

Các ví dụ tương đương khác

Các quan hệ sau là các quan hệ tương đương:

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

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

• Quan hệ "≥" trong số thực bắc cầu và phản xạ nhưng không đối xứng. Ví dụ: 7 ≥ 5 nhưng không 5 ≥ 7.
• Quan hệ "có cùng ước lớn hơn 1 với" giữa các số tự nhiên lớn hơn 1, có tính 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 (định nghĩa rằng aRb luôn sai) trên tập X nghiễm nhiên đối xứng và bắc cầu nhưng không phản xạ (trừ phi X 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 các biểu thức đại số, các biến bằng nhau có thể thay cho nhau, còn các biến có quan hệ tương đương nhau thì không thể thay cho nhau được. Các lớp tương đương trong quan hệ có thể thay cho nhau, nhưng các phần tử trong lớp thì không được phép.
• Quan hệ thứ tự bộ phận chặt không phản xạ, bắc cầu và không đối xứng.
• Quan hệ tương đương một phần có tính bắc cầu và đối xứng. Quan hệ có tính phản xạ khi và chỉ khi nó có tính toàn phần, nghĩa là, nếu với mọi $a,$ , tồn tại $b{\text{ sao cho }}a\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 ứng với trường hợp 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ố, thêm vào một số cấu trúc. Tổng quát thì, quan hệ tương đẳng thường đóng vai trò hạt nhân của các đồng cấu, và thương của cấu trúc bởi quan hệ tương đẳng có thể xác định được. 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 (ví dụ 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ệ mà vừa phản xạ vừa là quan hệ Euclid (trái hoặc phải) thì 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 \,$ là quan hệ tương đương trên $X,$ và $P(x)$ là tính chất của các phần tử thuộc $X,$ sao cho bất cứ khi nào $x\sim y,$ thì $P(x)$ đúng khi $P(y)$ đúng, và tính chất $P$ được gọi là xác định hoàn toàn hay bất biến lớp dưới quan hệ $\,\sim .$

Một trường hợp cụ thể thường gặp là khi $f$ là hàm số từ tập $X$ sang tập $Y;$ sao cho nếu $x_{1}\sim x_{2}$ suy ra $f\left(x_{1}\right)=f\left(x_{2}\right)$ thì $f$ được gọi là cấu xạ cho $\,\sim ,$ hay bất biến lớp dưới $\,\sim ,$ hoặc ngắn gọn hơn là bất biến dưới $\,\sim .$ Trường hợp có thể xảy ra trong lý thuyết các ký tự của nhóm hữu hạn.

Tổng quát hơn, một hàm có thể ánh xạ các phần tử tương đương nhau (dưới quan hệ tương đương $\,\sim _{A}$) sang các phần tử tương đương nhau khác (dưới quan hệ tương đương $\,\sim _{B}$). Hàm số có tính chất như vậy được gọi là cấu xạ từ $\,\sim _{A}$ sang $\,\sim _{B}.$

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

Đặt $a,b\in X.$, ta có một số định nghĩa sau:

Lớp tương đương

Bài chi tiết: Lớp tương đương

Tập con Y of X sao cho $a\sim b$ luôn thỏa mãn với mọi a và b thuộc Y, và không bao giờ với a thuộc Y và b ngoài Y, được gọi là lớp tương đương của X bởi ~. $[a]:=\{x\in X:a\sim x\}$ ký hiệu lớp tương đương mà phần tử a thuộc về. Tất cả các phần tử thuộc X mà tương đương với nhau thì đều thuộc chung một lớp tương đương.

Tập thương

Bài chi tiết: Tập hợp thương

Tập các lớp tương đương của X bởi ~, ký hiệu là $X/{\mathord {\sim }}:=\{[x]:x\in X\},$ là tập thương của X bởi ~. Nếu X là không gian tô pô, thì có cách tự nhiên để biến đổi $X/\sim$ thành không gian tô pô; xem không gian thương để biết thêm.

Phép chiếu

Bài chi tiết: Phép chiếu (đại số quan hệ)

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

Định lý trên các phép chiếu: Đặt hàm $f:X\to B$ sao cho nếu $a\sim b$ thì $f(a)=f(b).$ Khi đó tồn tại độc nhất hàm $g:X/\sim \to B$ sao cho $f=g\pi .$ Nếu $f$ là toàn ánh và $a\sim b{\text{ khi và chỉ khi }}f(a)=f(b),$ thì $g$ là song ánh.

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 ~ định nghĩa như sau: $x\sim y{\text{ khi và chỉ khi }}f(x)=f(y).$ Hạt nhân tương đương của đơn ánh là quan hệ đơn vị.

Phân hoạch

Bài chi tiết: Phân hoạch của tập hợp

Phân hoạch của X là tập P chứa các tập con của X, sao cho với mọi phần tử thuộc X chỉ thuộc đúng một tập thuộc P. Do đó, mỗi phần tử thuộc P không giao nhau đôi một và hợp của tất cả các phần tử của P là X.

Đếm số phân hoạch

Gọi X là tập hữu hạn chứa n phần tử. Bởi mỗi quan hệ tương đương trên X tương ứng với một phân hoạch trên X, và ngược lại số quan hệ tương đương trên X bằng với số phân hoạch riêng biệt của X, và bằng với số Bell thứ n, ký hiệu là B_n:

$B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}\quad$ (Công thức Dobinski).

Liên kết ngoài

• Hazewinkel, Michiel biên tập (2001), “Equivalence relation”, Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4
• Bogomolny, A., "Equivalence Relationship" cut-the-knot. Accessed 1 September 2009
• Equivalence relation at PlanetMath
• Bản mẫu:OEIS el