Quan hệ tương đương

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.

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

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ệuSửa đổi

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ĩaSửa đổi

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 đổi

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 đổi

Ví dụ đơn giảnSửa đổi

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ácSửa đổi

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 đươngSửa đổi

  • 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ácSửa đổi

  • 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 đươngSửa đổi

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ạchSửa đổi

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

Lớp tương đươngSửa đổi

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ươngSửa đổi

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ếuSửa đổi

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 đươngSửa đổi

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ạchSửa đổi

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ạchSửa đổi

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ảoSửa đổi

  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àiSửa đổi