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.

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 "formula_1" và "", thường được dùng khi ta không nhắc đến quan hệ formula_2 , còn dạng "formula_3", "", hay "formula_4" khi ta muốn nhắc đến formula_2. Khi muốn nói không tương đương ta có thể viết "" hoặc "formula_6".

== Định nghĩa ==
Quan hệ hai ngôi formula_7 trên tập formula_8 đượ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 formula_9 và formula_10 thuộc formula_11
- formula_12 (phản xạ).
- formula_1 khi và chỉ khi formula_14 (đối xứng).
- Nếu formula_1 và formula_16 thì formula_17 (bắc cầu).

formula_8 cùng với quan hệ tương đương formula_7 được gọi là setoid. Lớp tương đương của formula_20 dưới formula_21 được ký hiệu formula_22 định nghĩa bởi formula_23

=== Định nghĩa dùng đại số của các quan hệ ===
Nếu formula_24 và formula_25 là 2 hai quan hệ, thì quan hệ hợp thành formula_26 được định nghĩa là formula_27 khi chỉ khi tồn tại formula_28 sao cho formula_29 và formula_30. Đị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 formula_2 trên tập formula_8 như sau::

- formula_33. (phản xạ). (Ở đây, formula_34 ký hiệu hàm đồng nhất trên formula_8.)
- formula_36 (đối xứng).
- formula_37 (bắc cầu).

== Các ví dụ ==
=== Ví dụ đơn giản ===
Trên tập formula_38, quan hệ formula_39 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:
formula_40

Tập các lớp tương đương cho formula_2 là formula_42 Tập này là phân hoạch của tập formula_8 với formula_2.

=== 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ụ formula_45 bằng với formula_46
- "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 formula_47, "đồng dư với formula_47" 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ạ, , 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 formula_49 , tồn tại formula_50 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 formula_8 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 formula_7 là quan hệ tương đương trên formula_53 và formula_54 là tính chất của các phần tử thuộc formula_53 sao cho bất cứ khi nào formula_56 thì formula_54 đúng khi formula_58 đúng, và tính chất formula_59 được gọi là xác định hoàn toàn hay dưới quan hệ formula_60

Một trường hợp cụ thể thường gặp là khi formula_61 là hàm số từ tập formula_8 sang tập formula_63 sao cho nếu formula_64 suy ra formula_65 thì formula_61 được gọi là cho formula_21 hay formula_21 hoặc ngắn gọn hơn là formula_60 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 formula_70) sang các phần tử tương đương nhau khác (dưới quan hệ tương đương formula_71). Hàm số có tính chất như vậy được gọi là cấu xạ từ formula_70 sang formula_73

== Lớp tương đương, tập thương và phân hoạch ==
Đặt formula_74, ta có một số định nghĩa sau:

=== Lớp tương đương ===
Tập con "Y" của "X" sao cho formula_1 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 ~. formula_76 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à formula_77 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 formula_78 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 formula_7 là hàm formula_80 định nghĩa bởi formula_81 ánh xạ các phần tử của formula_8 sang lớp tương đương tương ứng của chúng theo formula_60

=== Hạt nhân tương đương ===
Hạt nhân tương đương của hàm formula_61 là quan hệ tương đương ~ định nghĩa như sau: formula_93 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":

== Đị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 formula_95 và formula_96 là hai quan hệ tương đương trên cùng tập formula_97, và formula_1 suy ra formula_99 với mọi formula_100 thì quan hệ formula_96 được gọi là thô hơn quan hệ formula_95, và quan hệ formula_95 được gọi là mịn hơn quan hệ formula_96. Các cách nói tương đương:
- formula_95 mịn hơn formula_96 nếu mọi lớp tương đương của formula_95 là tập con của một lớp tương đương của formula_96, và do đó mọi lớp tương đương của formula_96 là hợp của các lớp tương đương của formula_95.
- formula_95 mịn hơn formula_96 nếu phân hoạch từ formula_95 là kết quả mịn hóa phân hoạch của formula_96.

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ệ "formula_95 mịn hơn formula_96" 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ỳ formula_53 quan hệ tương đương formula_118 của các hàm formula_119 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 formula_7 trên formula_8 là hạt nhân tương đương của phép chiếu toàn ánh của nó formula_122 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 formula_53 có thể dùng để nói về quan hệ tương đương hay phân hoạch trên tập formula_53.
- 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 formula_125) 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
- 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 formula_134 và ~ là quan hệ tương đương trên "X" định nghĩa bởi formula_135 với mọi formula_136 và formula_137 với mọi formula_138 .Không gian thương formula_78 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 formula_140 và formula_141 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 formula_142 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 ==
- Bogomolny, A., "Equivalence Relationship" cut-the-knot. Accessed 1 September 2009
- Equivalence relation at PlanetMath