✨Quan hệ tương đương

right|thumb|[[Số Bell|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\; \backslash 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.)]]

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.

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\; \backslash sim\; b$" và "", thường được dùng khi ta không nhắc đến quan hệ $R$ , còn dạng "$a\; \backslash sim\_R\; b$", "", hay "$\{a\backslash 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 "" hoặc "$a\; \backslash not\backslash equiv\; b$".

Định nghĩa

Quan hệ hai ngôi $\backslash ,\backslash sim\backslash ,$ 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\; \backslash sim\; a$ (phản xạ).
• $a\; \backslash sim\; b$ khi và chỉ khi $b\; \backslash sim\; a$ (đối xứng).
• Nếu $a\; \backslash sim\; b$ và $b\; \backslash sim\; c$ thì $a\; \backslash sim\; c$ (bắc cầu).

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

Nếu $R\backslash subseteq\; X\backslash times\; Y$ và $S\backslash subseteq\; Y\backslash times\; Z$ là 2 hai quan hệ, thì quan hệ hợp thành $SR\backslash subseteq\; X\backslash times\; Z$ được định nghĩa là $x\; \backslash ,\; SR\; \backslash ,\; z$ khi chỉ khi tồn tại $y\backslash in\; Y$ sao cho $x\; \backslash ,\; R\; \backslash ,\; y$ và $y\; \backslash ,\; S\; \backslash ,\; 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::

• $\backslash operatorname\{id\}\; \backslash subseteq\; R$. (phản xạ). (Ở đây, $\backslash operatorname\{id\}$ ký hiệu hàm đồng nhất trên $X$.)
• $R=R^\{-1\}$ (đối xứng).
• $RR\backslash 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:

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ụ $\backslash tfrac\{1\}\{2\}$ bằng với $\backslash tfrac\{4\}\{8\}.$ 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 $\backslash ,\backslash sim\backslash ,$ 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\; \backslash 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 dưới quan hệ $\backslash ,\backslash 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\; \backslash sim\; x\_2$ suy ra $f\backslash left(x\_1\backslash right)\; =\; f\backslash left(x\_2\backslash right)$ thì $f$ được gọi là cho $\backslash ,\backslash sim,$ hay $\backslash ,\backslash sim,$ hoặc ngắn gọn hơn là $\backslash ,\backslash 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 $\backslash ,\backslash sim\_A$) sang các phần tử tương đương nhau khác (dưới quan hệ tương đương $\backslash ,\backslash sim\_B$). Hàm số có tính chất như vậy được gọi là cấu xạ từ $\backslash ,\backslash sim\_A$ sang $\backslash ,\backslash sim\_B.$

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

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

Lớp tương đương

Tập con Y của X sao cho $a\; \backslash 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\; \backslash in\; X\; :\; a\; \backslash 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

Tập các lớp tương đương của X bởi ~, ký hiệu là $X\; /\; \backslash mathord\{\backslash sim\}\; :=\; \{[x]\; :\; x\; \backslash 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\; /\; \backslash sim$ thành không gian tô pô; xem không gian thương để biết thêm.

Phép chiếu

Phép chiếu của $\backslash ,\backslash sim\backslash ,$ là hàm $\backslash pi\; :\; X\; \backslash to\; X/\backslash mathord\{\backslash sim\}$ định nghĩa bởi $\backslash 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 $\backslash ,\backslash sim.$

:Định lý trên các phép chiếu: Đặt hàm $f\; :\; X\; \backslash to\; B$ sao cho nếu $a\; \backslash sim\; b$ thì $f(a)\; =\; f(b).$ Khi đó tồn tại độc nhất hàm $g\; :\; X\; /\; \backslash sim\; \backslash to\; B$ sao cho $f\; =\; g\; \backslash pi.$ Nếu $f$ là toàn ánh và $a\; \backslash sim\; b\; \backslash 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\; \backslash sim\; y\; \backslash 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

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

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

• $\backslash sim$ mịn hơn $\backslash approx$ nếu mọi lớp tương đương của $\backslash sim$ là tập con của một lớp tương đương của $\backslash approx$, và do đó mọi lớp tương đương của $\backslash approx$ là hợp của các lớp tương đương của $\backslash sim$.
• $\backslash sim$ mịn hơn $\backslash approx$ nếu phân hoạch từ $\backslash sim$ là kết quả mịn hóa phân hoạch của $\backslash 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ệ "$\backslash sim$ mịn hơn $\backslash 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\; \backslash to\; X]$ của các hàm $X\; \backslash 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 $\backslash ,\backslash sim\backslash ,$ trên $X$ là hạt nhân tương đương của phép chiếu toàn ánh của nó $\backslash pi\; :\; X\; \backslash to\; X\; /\; \backslash 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\; \backslash 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 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\; \backslash sim\; b$ nếu tồn tại số tự nhiên $n$ và các phần tử $x\_0,\; \backslash ldots,\; x\_n\; \backslash 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,\; \backslash 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]\; \backslash times\; [0,\; 1],$ và ~ là quan hệ tương đương trên X định nghĩa bởi $(a,\; 0)\; \backslash sim\; (a,\; 1)$ với mọi $a\; \backslash in\; [0,\; 1]$ và $(0,\; b)\; \backslash sim\; (1,\; b)$ với mọi $b\; \backslash in\; [0,\; 1]$ .Không gian thương $X\; /\; \backslash 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\; \backslash in\; A$ và $g\; \backslash in\; G,\; g(x)\; \backslash 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à , đượ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\; \backslash sim\; b\; \backslash text\{\; khi\; và\; chỉ\; khi\; \}\; a\; b^\{-1\}\; \backslash 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).

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