Quan hệ tương đương

Bách khoa toàn thư mở Wikipedia
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 (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 đươngquan hệ hai ngôi có tính phản xạ, đối xứngbắ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[sửa | sửa mã nguồn]

Ký hiệu "" và "ab", thường được dùng khi ta không nhắc đến quan hệ , còn dạng "", "aR b", hay "" khi ta muốn nhắc đến . Khi muốn nói không tương đương ta có thể viết "ab" hoặc "".

Định nghĩa[sửa | sửa mã nguồn]

Quan hệ hai ngôi trên tập đượ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 thuộc

  • (phản xạ).
  • khi và chỉ khi (đối xứng).
  • Nếu thì (bắc cầu).

cùng với quan hệ tương đương được gọi là setoid. Lớp tương đương của dưới được ký hiệu định nghĩa bởi [1][2]

Định nghĩa dùng đại số của các quan hệ[sửa | sửa mã nguồn]

Nếu là 2 hai quan hệ, thì quan hệ hợp được định nghĩa là khi chỉ khi tồn tại sao cho .[note 1] Đị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 trên tập như sau::

  • . (phản xạ). (Ở đây, ký hiệu hàm đồng nhất trên .)
  • (đối xứng).
  • (bắc cầu).[3]

Các ví dụ[sửa | sửa mã nguồn]

Ví dụ đơn giản[sửa | sửa mã nguồn]

Trên tập , quan hệ 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 Tập này là phân hoạch của tập với .

Các ví dụ tương đương khác[sửa | sửa mã nguồn]

Các quan hệ sau là các quan hệ tương đương:

  • "Bằng với" trên tập số. Ví dụ bằng với [2]
  • "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 , "đồng dư với " trên tập số nguyên.[2]
  • "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[sửa | sửa mã nguồn]

  • 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[sửa | sửa mã nguồn]

  • 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 , tồn tại [proof 1] 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ệ chịu đựng 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 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[sửa | sửa mã nguồn]

Nếu là quan hệ tương đương trên là tính chất của các phần tử thuộc sao cho bất cứ khi nào thì đúng khi đúng, và tính chất được gọi là xác định hoàn toàn hay bất biến lớp dưới quan hệ

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

Lớp tương đương, tập thương và phân hoạch[sửa | sửa mã nguồn]

Đặt , ta có một số định nghĩa sau:

Lớp tương đương[sửa | sửa mã nguồn]

Tập con Y of X sao cho luôn thỏa mãn với mọi ab thuộc Y, và không bao giờ với a thuộc Yb ngoài Y, được gọi là lớp tương đương của X bởi ~. 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[sửa | sửa mã nguồn]

Tập các lớp tương đương của X bởi ~, ký hiệu là tập thương của X bởi ~. Nếu Xkhông gian tô pô, thì có cách tự nhiên để biến đổi thành không gian tô pô; xem không gian thương để biết thêm.

Phép chiếu[sửa | sửa mã nguồn]

Phép chiếu của là hàm định nghĩa bởi ánh xạ các phần tử của sang lớp tương đương tương ứng của chúng theo

Định lý trên các phép chiếu:[4] Đặt hàm sao cho nếu thì Khi đó tồn tại độc nhất hàm sao cho Nếu toàn ánh thì song ánh.

Hạt nhân tương đương[sửa | sửa mã nguồn]

Hạt nhân tương đương của hàm là quan hệ tương đương ~ định nghĩa như sau: Hạt nhân tương đương của đơn ánhquan hệ đơn vị.

Phân hoạch[sửa | sửa mã nguồn]

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 PX.

Đếm số phân hoạch[sửa | sửa mã nguồn]

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:

(Công thức Dobinski).

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Đôi khi phép hợp được viết là , hoặc là ; trong cả hai trường hợp đó, là quan hệ đầu tiên được áp dụng. Xem Hợp của quan hệ để biết thêm.
  1. ^ Xuôi: Cho bởi do tính toàn phần, nên theo tính đối xứng, do đó theo tính bắc cầu. — Ngược: Cho , chọn ,khi đó theo tính phản xạ.
  1. ^ Weisstein, Eric W. “Equivalence Class”. mathworld.wolfram.com (bằng tiếng Anh). Truy cập ngày 30 tháng 8 năm 2020.
  2. ^ a b c “7.3: Equivalence Classes”. Mathematics LibreTexts (bằng tiếng Anh). 20 tháng 9 năm 2017. Truy cập ngày 30 tháng 8 năm 2020.
  3. ^ Halmos, Paul Richard (1914). Naive Set Theory (bằng tiếng English). New York: Springer. tr. 41. ISBN 978-0-387-90104-6.Quản lý CS1: ngôn ngữ không rõ (liên kết)
  4. ^ Garrett BirkhoffSaunders Mac Lane, 1999 (1967). Algebra, 3rd ed. p. 35, Th. 19. Chelsea.

Liên kết ngoài[sửa | sửa mã nguồn]