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

Quan hệ hai ngôi
Đối xứng Phản đối xứng Toàn phần Lập tốt Có nối Có gặp Quan hệ tương đương ✓ ✗ ✗ ✗ ✗ ✗ Tiền thứ tự (giả thứ tự) ✗ ✗ ✗ ✗ ✗ ✗ Thứ tự riêng phần ✗ ✓ ✗ ✗ ✗ ✗ Tiền thứ tự toàn phần ✗ ✗ ✓ ✗ ✗ ✗ Thứ tự toàn phần ✗ ✓ ✓ ✗ ✗ ✗ Tiền thứ tự tốt ✗ ✗ ✓ ✓ ✗ ✗ Giả thứ tự tốt ✗ ✗ ✗ ✓ ✗ ✗ Thứ tự tốt ✗ ✓ ✓ ✓ ✗ ✗ Dàn ✗ ✓ ✗ ✗ ✓ ✓ Nửa dàn có nối ✗ ✓ ✗ ✗ ✓ ✗ Nửa dàn có gặp ✗ ✓ ✗ ✗ ✗ ✓
Dấu "✓" chỉ tính chất trong cột đó cần phải có trong định nghĩa của hàng đó. Ví dụ, định nghĩa của quan hệ tương đương buộc nó phải có tính đối xứng. Tất cả định nghĩa đều yêu cầu tính bắc cầu và tính phản xạ.

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 thành $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 của 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 một phần tử thuộc X chỉ thuộc đúng một tập thuộc P. Do đó, mỗi tập hợp 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).

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

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

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

Trong cả hai, tập các phần tử trong phân hoạch của X đều được gọi là lớp tương đương của X bởi ~. Do đó, tồn tại song ánh giữa tập các quan hệ tương đương trên X với tập các phân hoạch trên X.

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

Xem thêm: Phân hoạch tập hợp § Mịn hóa phân hoạch

Nếu $\sim$ và $\approx$ là hai quan hệ tương đương trên cùng tập $S$, và $a\sim b$ suy ra $a\approx b$ với mọi $a,b\in S,$ thì quan hệ $\approx$ được gọi là thô hơn quan hệ $\sim$, và quan hệ $\sim$ được gọi là mịn hơn quan hệ $\approx$. Các cách nói tương đương:

• $\sim$ mịn hơn $\approx$ nếu mọi lớp tương đương của $\sim$ là tập con của một lớp tương đương của $\approx$, và do đó mọi lớp tương đương của $\approx$ là hợp của các lớp tương đương của $\sim$.
• $\sim$ mịn hơn $\approx$ nếu phân hoạch từ $\sim$ là kết quả mịn hóa phân hoạch của $\approx$.

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

Xét quan hệ "$\sim$ mịn hơn $\approx$" trên tập các quan hệ tương đương trên cùng một tập nào đó, quan hệ này là quan hệ thứ tự một phần, và do đó tập hợp này là ví dụ về 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 X]$ của các hàm $X\to X$ có thể sinh như sau: Hai hàm số được gọi là tương đương nhau nếu tập các điểm cố định của chúng có cùng số lượng, tương ứng với số xích độ dài một trong hoán vị.
• Quan hệ tương đương $\,\sim \,$ trên $X$ là hạt nhân tương đương của phép chiếu toàn ánh của nó $\pi :X\to X/\sim .$ Ngược lại, bất kỳ toàn ánh sẽ xác định phân hoạch trên miền của nó, cụ thể hơn là các tiền ảnh của các đơn điểm trên miền giá trị. Do vậy, phép chiếu trong đó miền là tập $X,$ có thể dùng để nói về quan hệ tương đương hay phân hoạch trên tập $X,$.
• Giao của bất kỳ họ các quan hệ tương đương X (bản chất quan hệ được coi là tập con của $X\times X$) cũng là quan hệ tương đương. Từ đây nảy sinh cách xây dựng quan hệ tương đương sau: cho bất kỳ quan hệ hai ngôi R trên X, quan hệ tương đương sinh bởi R là giao của 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). Nói cụ thể hơn, R sinh ra quan hệ tương đương

$a\sim b$ nếu tồn tại số tự nhiên $n$ và các phần tử $x_{0},\ldots ,x_{n}\in X$ sao cho $a=x_{0}$, $b=x_{n}$, và $x_{i-1}\mathrel {R} x_{i}$ hoặc $x_{i}\mathrel {R} x_{i-1}$, với $i=1,\ldots ,n.$

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

• Quan hệ tương đương có thể xây dựng không gian mới bằng cách "dính chúng với nhau." Gọi X là ô vuông $[0,1]\times [0,1],$ và ~ là quan hệ tương đương trên X định nghĩa bởi $(a,0)\sim (a,1)$ với mọi $a\in [0,1]$ và $(0,b)\sim (1,b)$ với mọi $b\in [0,1]$ .Không gian thương $X/\sim$ sẽ có đồng phôi với hình xuyến: lấy một ô vuông của một tờ giấy, uốn cong và dính cạnh trên và dưới với nhau để tạo thành hình trụ, uốn tiếp hình trụ đó (dính mặt tròn trên và dưới) thì sẽ thành hình xuyến.

Cấu trúc đại số

Nhiều phần trong toán học quan tâm tới tính tương đương và tính thứ tự, trong đó lý thuyết dàn được dùng để nghiên cứu các quan hệ thứ tự. Mặc dù các quan hệ tương đương phổ biến nhiều trong toán học, cấu trúc đại số của chúng không được nghiên cứu nhiều như trong quan hệ thứ tự. Cấu trúc của quan hệ tương đương thường lấy từ lý thuyết nhóm hơn, và đôi khi từ lý thuyết dàn, phạm trù, và các groupoid.

Lý thuyết nhóm

Giống như quan hệ thứ tự nằm trong tập sắp thứ tự và các tập đóng dưới phép supremum và infimum, thì các quan hệ tương đương được xét trong các tập đã được phân hoạch, tức là các tập đóng dưới các song ánh bảo toàn cấu trúc phân hoạch. Bởi vì mọi song ánh đó đều ánh xạ lớp tương đương tới chính nó, các song ánh còn được gọi là hoán vị hay phép thế dưới bối cảnh lý thuyết nhóm. Nhóm các hoán vị (hay còn gọi là nhóm biến đổi) cùng với 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.

Gọi ~ là quan hệ tương đương trên tập khác rỗng A, (tập A được gọi là tập phổ dụng hay tập nền). Gọi G là tập các song ánh 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 A$ và $g\in G,g(x)\in [x].$ thì ba định lý liên hệ nhau sau được thỏa mãn:

• ~ 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 nhắc ở trên);
• Cho một phân hoạch của A, thì G là nhóm biến đổi dưới phép hợp, có các quỹ đạo là các các lớp của phân hoạch đó;

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

Kết luận lại: cho quan hệ tương đương ~ trên A, tồn tại nhóm biến đổi G trên A có các quỹ đạo là lớp tương đương của A dưới ~.

Nhóm biến đổi này có sự khác biệt nền tảng với cách dàn mô tả quan hệ thứ tự. 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ử của tập nền A. Trong khi đó, tham số của phép hợp và nghịch đảo của nhóm biến đổi là các phần tử của tập các song ánh A → A.

Khi nhắc đến nhóm nói chung, gọi H là nhóm con của G. Gọi ~ là quan hệ tương đương trên G, thỏa mãn $a\sim b{\text{ khi và chỉ khi }}ab^{-1}\in H.$ Các lớp tương đương ~ ;còn được gọi là các quỹ đạo của tác động của H trên G ;là các lớp kề phải của H trong G. Thay a và b sẽ ra các lớp kề trái.

Nội dung này có thể đọc thêm trong Rosen (2008: chương 10).

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