Xem mã nguồn của Quan hệ tương đương

{{Short description|So sánh hai phần tử toán học}}
<!--{{stack|{{Binary relations}}}}-->
[[Tập tin:Set partitions 5; matrices.svg|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]] <math>5 \times 5</math> (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 [[quan hệ phản xạ|phản xạ]], [[quan hệ đối xứng|đối xứng]] và [[quan hệ bắc cầu|bắc cầu]].

Mỗi quan hệ đối xứng [[Phân hoạch tập hợp|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}}
Ký hiệu "<math>a \sim b</math>" và "{{math|''a'' ≡ ''b''}}", thường được dùng khi ta không nhắc đến quan hệ <math>R</math> , còn dạng "<math>a \sim_R b</math>", "{{math|''a'' ≡<sub>''R''</sub> ''b''}}", hay "<math>{a\mathop{R}b}</math>" khi ta muốn nhắc đến <math>R</math>. Khi muốn nói không tương đương ta có thể viết "{{math|''a'' ≁ ''b''}}" hoặc "<math>a \not\equiv b</math>".

== Định nghĩa ==
[[Quan hệ hai ngôi]] <math>\,\sim\,</math> trên tập <math>X</math> đượ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 <math>a, b,</math> và <math>c</math> thuộc <math>X:</math>
* <math>a \sim a</math> ([[quan hệ phản xạ|phản xạ]]).
* <math>a \sim b</math> khi và chỉ khi <math>b \sim a</math> ([[quan hệ đối xứng|đối xứng]]).
* Nếu <math>a \sim b</math> và <math>b \sim c</math> thì <math>a \sim c</math> ([[quan hệ bắc cầu|bắc cầu]]).

<math>X</math> cùng với quan hệ tương đương <math>\,\sim\,</math> được gọi là [[setoid]]. [[Lớp tương đương]] của <math>a</math> dưới <math>\,\sim,</math> được ký hiệu <math>[a],</math> định nghĩa bởi <math>[a] = \{x \in X : x \sim a\}.</math><ref>{{Chú thích web|last=Weisstein|first=Eric W.|title=Equivalence Class|url=https://mathworld.wolfram.com/EquivalenceClass.html|access-date=2020-08-30|website=mathworld.wolfram.com|language=en}}</ref><ref name=":0">{{Chú thích web|date=2017-09-20|title=7.3: Equivalence Classes|url=https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Book%3A_Mathematical_Reasoning__Writing_and_Proof_(Sundstrom)/7%3A_Equivalence_Relations/7.3%3A_Equivalence_Classes|access-date=2020-08-30|website=Mathematics LibreTexts|language=en}}</ref>

=== Định nghĩa dùng đại số của các quan hệ ===
Nếu <math>R\subseteq X\times Y</math> và <math>S\subseteq Y\times Z</math> là 2 hai quan hệ, thì [[Hợp thành quan hệ|quan hệ hợp thành]] <math>SR\subseteq X\times Z</math> được định nghĩa là <math>x \, SR \, z</math> khi chỉ khi tồn tại <math>y\in Y</math> sao cho <math>x \, R \, y</math> và <math>y \, S \, z</math>.<ref group="note">Đôi khi phép hợp <math>SR\subseteq X\times Z</math> được viết là <math>R;S</math>, hoặc là <math>RS</math>; trong cả hai trường hợp đó, <math>R</math> là quan hệ đầu tiên được áp dụng. Xem [[Hợp của quan hệ]] để biết thêm.</ref> Định nghĩa này tổng quát định nghĩa của phép [[hàm hợp|hợp hàm]]. Từ đó, ta có định nghĩa khác tương đương của quan hệ tương đương <math>R</math> trên tập <math>X</math> như sau::

* <math>\operatorname{id} \subseteq R</math>. ([[Quan hệ phản xạ|phản xạ]]). (Ở đây, <math>\operatorname{id}</math> ký hiệu [[hàm đồng nhất]] trên <math>X</math>.)
* <math>R=R^{-1}</math> ([[Quan hệ đối xứng|đối xứng]]).
* <math>RR\subseteq R</math> ([[Quan hệ bắc cầu|bắc cầu]]).<ref>{{Chú thích sách |last=Halmos |first=Paul Richard |title=Naive Set Theory |publisher=Springer |year=1914 |isbn=978-0-387-90104-6 |location=New York |pages=41 |language=en}}</ref>

== Các ví dụ ==
=== Ví dụ đơn giản ===
Trên tập <math>X = \{a, b, c\}</math>, quan hệ <math>R = \{(a, a), (b, b), (c, c), (b, c), (c, b)\}</math> 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:
<math>[a] = \{a\}, ~~~~ [b] = [c] = \{b, c\}.</math>

Tập các lớp tương đương cho <math>R</math> là <math>\{\{a\}, \{b, c\}\}.</math> Tập này là [[Phân hoạch tập hợp|phân hoạch]] của tập <math>X</math> với <math>R</math>.

=== 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ụ <math>\tfrac{1}{2}</math> bằng với <math>\tfrac{4}{8}.</math><ref name=":0" />
* "Có cùng sinh nhật" trên tập con người.
* "[[đồng dạng|đồng dạng với]]" trên tập tất cả [[tam giác]].
* "[[tương đẳng|tương đẳng với]]" trên tập tất cả [[tam giác]].
* Cho số tự nhiên <math>n</math>, "[[đồng dư]] với <math>n</math>" trên tập [[số nguyên]].<ref name=":0" />
* "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 số|ướ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ạ, {{em|[[Quan hệ phản xứng|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ể [[phép thay (đại số)|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ự một phần nghiêm ngặt|Quan hệ thứ tự bộ phận chặt]] không phản xạ, bắc cầu và [[Quan hệ bất đối xứng|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 [[quan hệ toàn phần|toàn phần]], nghĩa là, nếu với mọi <math>a,</math> , tồn tại <math>b \text{ sao cho } a \sim b.</math><ref group="proof">''Xuôi:'' Cho <math>a,</math> bởi <math>a \sim b</math> do tính toàn phần, nên <math>b \sim a</math> theo tính đối xứng, do đó <math>a \sim a</math> theo tính bắc cầu. &mdash; ''Ngược:'' Cho <math>a,</math> , chọn <math>b = a,</math> ,khi đó <math>a \sim b</math> theo tính phản xạ.</ref> 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 <math>X</math> 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 (đại số)|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 <math>\,\sim\,</math> là quan hệ tương đương trên <math>X,</math> và <math>P(x)</math> là tính chất của các phần tử thuộc <math>X,</math> sao cho bất cứ khi nào <math>x \sim y,</math> thì <math>P(x)</math> đúng khi <math>P(y)</math> đúng, và tính chất <math>P</math> được gọi là [[xác định hoàn toàn]] hay {{em|bất biến lớp}} dưới quan hệ <math>\,\sim.</math>

Một trường hợp cụ thể thường gặp là khi <math>f</math> là hàm số từ tập <math>X</math> sang tập <math>Y;</math> sao cho nếu <math>x_1 \sim x_2</math> suy ra <math>f\left(x_1\right) = f\left(x_2\right)</math> thì <math>f</math> được gọi là {{em|cấu xạ}} cho <math>\,\sim,</math> hay {{em|bất biến lớp dưới}} <math>\,\sim,</math> hoặc ngắn gọn hơn là {{em|bất biến dưới}} <math>\,\sim.</math> 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 <math>\,\sim_A</math>) sang các phần tử tương đương nhau khác (dưới quan hệ tương đương <math>\,\sim_B</math>).  Hàm số có tính chất như vậy được gọi là cấu xạ từ <math>\,\sim_A</math> sang <math>\,\sim_B.</math>

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

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

=== Lớp tương đương ===
{{main|Lớp tương đương}}
Tập con ''Y'' của ''X'' sao cho <math>a \sim b</math> 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 ~. <math>[a] := \{x \in X : a \sim x\}</math> 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 ===
{{main|Tập hợp thương}}
Tập các lớp tương đương của ''X'' bởi ~, ký hiệu là <math>X / \mathord{\sim} := \{[x] : x \in X\},</math> 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 <math>X / \sim</math> thành không gian tô pô; xem [[Không gian thương (tô pô)|không gian thương]] để biết thêm.

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

:'''Định lý''' trên các [[Phép chiếu (lý thuyết tập hợp)|phép chiếu]]:<ref>[[Garrett Birkhoff]] và [[Saunders Mac Lane]], 1999 (1967). ''Algebra'', 3rd ed. p.&nbsp;35, Th. 19. Chelsea.</ref>  Đặt hàm <math>f : X \to B</math> sao cho nếu <math>a \sim b</math> thì <math>f(a) = f(b).</math> Khi đó tồn tại độc nhất hàm <math>g : X / \sim \to B</math> sao cho <math>f = g \pi.</math> Nếu <math>f</math> là [[toàn ánh]] và <math>a \sim b \text{ khi và chỉ khi } f(a) = f(b),</math> thì <math>g</math> là [[song ánh]].

=== Hạt nhân tương đương ===
'''Hạt nhân tương đương''' của hàm <math>f</math> là quan hệ tương đương ~ định nghĩa như sau: <math>x \sim y \text{ khi và chỉ khi } f(x) = f(y).</math> Hạt nhân tương đương của [[đơn ánh]] là [[quan hệ đơn vị]].

=== Phân hoạch ===
{{main|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à [[Phép hợp|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<sub>n</sub>'':
:<math>B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!} \quad</math> ([[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:<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. p.&nbsp;31, Th. 8. Springer-Verlag.</ref><ref>Dummit, D. S., and Foote, R. M., 2004. ''Abstract Algebra'', 3rd ed. p.&nbsp;3, Prop. 2. John Wiley & Sons.</ref><ref>[[Karel Hrbacek]] & [[Thomas Jech]] (1999) ''Introduction to Set Theory'', 3rd edition, pages 29–32, [[Marcel Dekker]]</ref>
* 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==
{{See also|Phân hoạch tập hợp#Mịn hóa phân hoạch}}
Nếu <math>\sim</math> và <math>\approx</math> là hai quan hệ tương đương trên cùng tập <math>S</math>, và <math>a \sim b</math> suy ra <math>a \approx b</math> với mọi <math>a, b \in S,</math> thì quan hệ <math>\approx</math> được gọi là '''thô''' hơn quan hệ <math>\sim</math>, và quan hệ <math>\sim</math> được gọi là '''mịn''' hơn quan hệ <math>\approx</math>. Các cách nói tương đương:
* <math>\sim</math> mịn hơn <math>\approx</math> nếu mọi lớp tương đương của <math>\sim</math> là tập con của một lớp tương đương của <math>\approx</math>, và do đó mọi lớp tương đương của <math>\approx</math> là hợp của các lớp tương đương của <math>\sim</math>.
* <math>\sim</math> mịn hơn <math>\approx</math> nếu phân hoạch từ <math>\sim</math> là kết quả mịn hóa phân hoạch của <math>\approx</math>.

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ệ "<math>\sim</math> mịn hơn <math>\approx</math>" 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]].<ref>{{citation|title=Lattice Theory|volume=25|series=Colloquium Publications|publisher=American Mathematical Society|first=Garrett|last=Birkhoff|author-link=Garrett Birkhoff|edition=3rd|year=1995|isbn=9780821810255}}. Sect. IV.9, Theorem 12, page 95</ref>

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

* Cho bất kỳ <math>X,</math> quan hệ tương đương <math>[X \to X]</math> của các hàm <math>X \to X</math> 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 (toán học)|điểm cố định]] của chúng có cùng [[lực lượng (toán học)|số lượng]], tương ứng với số xích độ dài một trong [[hoán vị]].
* Quan hệ tương đương <math>\,\sim\,</math> trên <math>X</math> là [[Quan hệ tương đương#Hạt nhân tương đương|hạt nhân tương đương]] của [[Quan hệ tương đương#Phép chiếu|phép chiếu]] [[toàn ánh]] của nó <math>\pi : X \to X / \sim.</math><ref>[[Garrett Birkhoff]] và [[Saunders Mac Lane]], 1999 (1967). ''Algebra'', 3rd ed. p.&nbsp;33, Th. 18. Chelsea.</ref> 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 (toán học)|đơn điểm]] trên [[miền giá trị]]. Do vậy, phép chiếu trong đó miền là tập <math>X,</math> có thể dùng để nói về quan hệ tương đương hay phân hoạch trên tập <math>X,</math>.
* 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 <math>X \times X</math>) 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 {{em|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
::<math>a \sim b</math> nếu tồn tại [[số tự nhiên]] <math>n</math> và các phần tử <math>x_0, \ldots, x_n \in X</math> sao cho <math>a = x_0</math>, <math>b = x_n</math>, và <math>x_{i-1} \mathrel{R} x_i</math> hoặc <math>x_i \mathrel{R} x_{i-1}</math>, với <math>i = 1, \ldots, n.</math>
:Đô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à [[Tích Descartes|ô vuông]] <math>[0, 1] \times [0, 1],</math> và ~ là quan hệ tương đương trên ''X'' định nghĩa bởi <math>(a, 0) \sim (a, 1)</math> với mọi <math>a \in [0, 1]</math> và <math>(0, b) \sim (1, b)</math> với mọi <math>b \in [0, 1]</math> .[[Không gian thương]] <math>X / \sim</math> 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à [[quan hệ thứ tự|tính thứ tự]], trong đó [[Dàn (thứ tự)|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, [[lý thuyết phạm trù|phạm trù]], và các [[groupoid]].

===Lý thuyết nhóm===

Giống như [[quan hệ thứ tự]] nằm trong [[quan hệ thứ tự một phần|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 [[phân hoạch tập hợ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 hoán vị|Nhóm các hoán vị]] (hay còn gọi là [[tác động nhóm|nhóm biến đổi]]) cùng với khái niệm [[quỹ đạo (lý thuyết nhó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 <math>x \in A</math> và <math>g \in G, g(x) \in [x].</math> thì ba định lý liên hệ nhau sau được thỏa mãn:<ref>Rosen (2008), pp.&nbsp;243–45. Khó đọc hơn là phần §10.3 của [[Bas van Fraassen]], 1989. ''Laws and Symmetry''. Oxford Univ. Press.</ref>
* ~ phân hoạch ''A'' thành các lớp tương đương. (Đây là {{em|Đị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 [[phân hoạch tập hợp|các lớp]] của phân hoạch đó;{{#tag:ref|
''Chứng minh''.<ref>Bas van Fraassen, 1989. ''Laws and Symmetry''. Oxford Univ. Press: 246.</ref> Gọi [[hàm hợp|phép hợp]] là phép nhân trong nhóm, và hàm ngược là nghịch đảo trong nhóm. Thì ''G'' là một nhóm đóng dưới phép hợp, tức là cho <math>x \in A</math> và <math>g \in G, [g(x)] = [x],</math> bởi vì ''G'' thỏa mãn bốn điều kiện sau:
* ''G đóng dưới phép hợp''. Tồn tại hợp của bất kỳ hai phần tử thuộc ''G'', vì miền gốc và miền đích của bất kỳ phần tử thuộc ''G'' đều là ''A''. Hơn nữa hợp của hai song ánh cũng là song ánh;<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 22, Th. 6.</ref>
* ''Tồn tại [[phần tử đơn vị]]''. Ở đây, dễ thấy [[hàm đồng nhất]], ''I''(''x'') = ''x'', là phần tử đơn vị của ''G'';
* ''Tồn tại [[Nghịch đảo (toán học)|giá trị nghịch đảo]]''. Mọi [[song ánh]] ''g'' đều có nghịch đảo (tức [[hàm ngược]]) ''g''<sup>&minus;1</sup>, sao cho ''gg''<sup>−1</sup> = ''I'';
* ''[[Tính kết hợp]]''. ''f''(''gh'') = (''fg'')''h''. Đúng cho mọi miền.<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''.  Springer-Verlag: 24, Th. 7.</ref>
Gọi ''f'' và ''g'' là hai phần tử bất kỳ thuộc ''G''. Từ định nghĩa của ''G'', [''g''(''f''(''x''))] = [''f''(''x'')] và [''f''(''x'')] = [''x''], nên [''g''(''f''(''x''))] = [''x'']. Do đó ''G'' còn là nhóm biến đổi  (và là [[nhóm tự đẳng cấu]]) bởi vì phép hợp hàm bảo toàn phân hoạch của <math>A. \blacksquare</math>}}

* 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''.<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 202, Th. 6.</ref><ref>Dummit, D. S., and Foote, R. M., 2004. ''Abstract Algebra'', 3rd ed. John Wiley & Sons: 114, Prop. 2.</ref>

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 (thứ tự)|dàn]] mô tả quan hệ thứ tự. Tham số của [[nối và gặp|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 [[hàm hợp|phép hợp]] và [[hàm ngược|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 <math>a \sim b \text{ khi và chỉ khi } a b^{-1} \in H.</math> Các lớp tương đương ~ ;còn được gọi là các quỹ đạo của [[tác động nhóm|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===
== Tham khảo ==
{{Tham khảo|group=note}}
{{Tham khảo|group=proof}}
{{Tham khảo}}

== Liên kết ngoài ==
* {{springer|title=Equivalence relation|id=p/e036030}}
* [[Alexander Bogomolny|Bogomolny, A.]], "[http://www.cut-the-knot.org/blue/equi.shtml Equivalence Relationship]" [[cut-the-knot]]. Accessed 1 September 2009
* [https://web.archive.org/web/20130509233055/http://planetmath.org/equivalencerelation Equivalence relation] at PlanetMath
* {{OEIS el|1=A231428|2=Binary matrices representing equivalence relations}}
{{Lý thuyết thứ tự}}
{{Logic toán}}
{{Lý thuyết tập hợp}}
{{Đại số}}
{{Kiểm soát tính nhất quán}}

[[Thể loại:Quan hệ hai ngôi]]