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_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::
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:
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" of "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 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à "Bn":